如何保持二叉搜索树的平衡？

Question

如何保持二叉搜索树的平衡？

algorithmdata-structurestreebig-obinary-search-tree

3

大多数二叉搜索树操作的运行时间取决于树的高度。如果树平衡良好，则插入、删除、查找、后继、前驱、最小值或最大值查询的成本为O(log n)。然而，如果树不平衡，这些操作的成本可能会高达O(n)。

如何在插入和删除元素时保持二叉搜索树平衡呢？

- templatetypedef

2个回答

0

将普通二叉搜索树转换为平衡二叉搜索树的代码，请调用给定的函数。


struct Node* solve(int s, int e, vector<int>& inorder) {
    if (s > e) return NULL;

    int mid = (s + e) / 2;
    struct Node* node = new Node(inorder[mid]);
    node->left = solve(s, mid - 1, inorder);
    node->right = solve(mid + 1, e, inorder);

    return node;
}

class Solution {
public:
    Node* buildBalancedTree(Node* root) {
        vector<int> inorder;
        stack<Node*> st;
        Node* node = root;

        while (true) {
            if (node != NULL) {
                st.push(node);
                node = node->left;
            } else {
                if (st.empty()==true) break;

                node = st.top();
                st.pop();
                inorder.push_back(node->data);
                node=node->right;
               
            }
        }

        int n = inorder.size();
       // for(int i=0;i<n;i++) cout<<inorder[i]<<" ";
        Node* head = NULL;
        head = solve(0, n - 1, inorder);
        return head;
    }
};

- AYUSH PATEL

感谢您为Stack Overflow社区做出的贡献。这可能是一个正确的答案，但如果您能提供代码的额外解释，让开发人员能够理解您的推理过程，那将非常有帮助。对于那些对语法不太熟悉或者难以理解概念的新开发人员来说，这尤其有用。您是否可以编辑您的答案，以包含额外的细节，以造福社区？ - undefined

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

有很多，非常多的方法可以保持二叉搜索树的平衡，每种方法都会引入不同的权衡。一般来说，平衡二叉搜索树可以分为以下几类：

平衡树：试图保持树的不同部分之间高度差异相对较小的树。

秩平衡树：是最近发展起来的一种平衡树的推广，其中每个节点被赋予一个“秩”，并且节点尽量保持与其父节点的秩差较小。

权重平衡树：试图保持树的不同区域中节点数量相对均衡的树。

随机化树：通过随机化形状，试图保持整体高度较低的树。

静态树：设计成具有特定形状，适用于特定查询集的树。

自适应树：根据访问情况重新调整形状，以降低查找成本的树。

以下是这些不同策略的简要介绍，以及每种类型的不同树的一些示例。

高度平衡树

高度平衡树直观地通过施加结构约束来确保某些子树的高度不能相差太多，对于“太多”的定义而言。它们通过确保只有在存在大量节点时，树才能增长到一定高度，从而保持整体树高较低。其中几种最常用的树属于这个类别。例如：

AVL树

AVL树是以其发明者的首字母命名的原始平衡二叉搜索树数据结构，于1962年发明。AVL树是二叉树，遵循以下结构约束：每个节点的两个子树的高度差最多为1。这是一个严格的结构约束：任何高度为h的AVL树都有F_h+2到2^h之间的节点数量，其中F_n是第n个斐波那契数。

为了满足这个要求，AVL树在插入或删除操作创建一个左右子树高度差为±2的子树时，会执行树旋转。

由于结构上的严格限制，AVL树相对于节点数量来说往往具有非常低的高度。然而，这也意味着单个插入或删除操作可能会导致许多节点子树的相对高度发生变化，从而需要执行大量的旋转操作。

现代AVL树有几种变体。RAVL树（放松AVL树）通过允许在删除操作后出现更大程度的不平衡，减少了每次插入或删除操作所需的工作量。

红黑树

红黑树是二叉搜索树，每个节点根据一组严格的规则被赋予红色或黑色：

根节点为黑色。
没有红色节点有红色子节点。
从树的根开始并沿树向下移动的任何路径通过相同数量的黑色节点。

最后一个规则是最微妙的。这意味着如果您从根节点开始向左或向右移动，无论您作出哪些左/右选择，在离开树的那一点，访问的黑色节点数始终相同。

这些规则确保最深的叶节点的深度最多大约是最浅叶节点的两倍。直观地说，极端情况是有一个叶节点只能通过由纯黑节点组成的路径到达，而另一个叶节点可以通过交替的黑/红/黑/红/...路径到达，因为红色节点不能有红色子节点。更详细的分析表明，树的高度保证为O(log n)。

红黑树的插入和删除是通过进行普通的插入或删除操作，然后进行一系列的旋转和颜色变换来确保满足上述规则。与AVL树不同，红黑树通常进行较少的旋转，并在插入或删除后做很少的“修复”工作。具体而言，每次插入或删除所需的修复工作的摊销量为O(1)，因此大多数插入和删除将执行常规的O(log n)树操作加上非常少量的额外工作。因此，虽然红黑树往往比AVL树更高，但在具有大量插入和删除的工作流中，它们稍微更快一些。

AA树是一种与红黑树密切相关的高度平衡树的风格。

红黑树和AA树都与一类称为B-树的平衡多路搜索树相关。直观地说，B-树是一种多路树，其中每个节点可以存储大约b到2b个键，其中b是某个外部参数。它们通过将插入操作执行在叶节点上，然后在超过大小限制时拆分较大的叶子并将键“提升”到更高层的树中工作。

红黑树可以被视为——实际上是由此演化而来——在一个B树中建模，其中每个节点保存1、2或3个键（一个2-3-4树）。其思想是，红黑树中的每个黑色节点对应于2-3-4树中的一个节点，而红色节点代表被“提升”到其上方的黑色节点的键。另一方面，AA树是基于B树建模的，每个节点有1或2个键（一个2-3树），使用类似的技术。AA树还强制执行一个规则，即“红色”节点必须位于其被提升到的黑色节点的左侧。这减少了在插入或删除期间需要检查的情况数量，但也增加了可能需要执行的旋转次数。

左倾红黑树

红黑树和AA树之间的“混合”是左倾红黑树。这种树结构，像红黑树一样，将2-3-4树编码为二叉搜索树。正如名称所暗示的那样，在黑色节点正好有一个红色子节点的情况下，该红色子节点必须悬挂在其黑色父节点的左侧。

这减少了插入或删除中可能出现的情况数量，但与AA树一样，在树编辑期间增加了必须执行的旋转次数。

平衡秩树

平衡秩树为每个节点分配一个称为秩的数字，并强制执行一组规则，以确保节点与其子节点之间的秩差不会“太大”。关于平衡秩树的原始论文表明，这类树包括AVL树和（经过微小修改后）也包括红黑树。

WAVL树

WAVL树（weak AVL树）是最著名的平衡秩树之一。它通过为节点分配秩数，使得每个节点的秩数最多比其子节点的秩数大两个单位。当树中从不删除元素时，WAVL树与AVL树完全相同，并且始终可以按照红黑规则进行着色，因此在高度/形状上永远不会比红黑树更差。与AVL树不同但类似于红黑树，WAVL树在每次插入或删除时需要执行的旋转操作最多只需常数次。

平衡树

平衡树旨在通过确保每个节点的左子树和右子树中节点数量之间存在某种“良好”关系，从而使整个树的高度保持较低。基本思想是，如果每个节点将剩余节点分成一些良好的比例（例如，75% / 25%），那么树的每一步下降都会导致当前子树的大小几何级数地减小，从而确保树具有对数高度。

BB[α]树

BB[α]树（有界平衡树，参数α）是二叉搜索树，其中每个节点的子树的“权重”始终至少是其父节点“权重”的α分数。（在BB[α]树中，节点的权重由其子树中的节点总数加一给出。）随着α越来越接近1/2，左右子树的相对大小必须越来越接近。这意味着需要更多的工作来维护树的形状，但整体树高度较低。当α变小时，左右子树的相对大小受到的限制较少，这意味着插入或删除元素时需要做更少的工作，但树的高度会变得越来越大。

与上述所有树一样，BB[α]树使用树旋转来在插入或删除后重新排列节点以保持平衡条件。最初版本的BB[α]树对α的选择有一个上限约为0.25，这意味着树中的每一步都可以确保至少有25%的剩余节点不再位于当前搜索的子树中。

替罪羊树

替罪羊树是一种介于平衡权重树和平衡高度树之间的混合树。该树本身是一棵平衡权重树，其中有一个参数α（与BB[α]树中的α参数无关），使得每个节点的两个子树的大小最多等于节点自身大小的α倍。这里，节点的"大小"是其子树中节点的数量。

与前面提到的平衡树类型不同，替罪羊树不直接使用旋转来进行重新平衡。相反，当插入操作使树的高度"过高"以至于无法保持平衡时，它会沿着插入路径向后搜索，寻找一个未正确平衡的节点，然后重新构建整个子树以实现完美平衡。从这个意义上讲，虽然树的形状是平衡权重树，但重新平衡的策略是通过查找高度平衡违规来实现的。

这种方法不能保证在插入或删除时的最坏情况下具有O(log n)的性能，因为重新平衡违规子树的成本很高。然而，它确实提供了每次插入或删除的摊销O(log n)的成本，因为很少需要进行大规模重建，并且在完成大规模重建后，树会变得完美平衡。

通过使用一组巧妙的树旋转，可以在线性时间内使用仅O(1)的辅助存储空间来重建糟糕的子树的实际逻辑，这是通过Day-Stout-Warren算法实现的，该算法可以将BST优化地重建为完美平衡。

在无法通过旋转进行重新平衡的更大数据结构中，经常使用替罪羊树作为构建模块。例如，替罪羊树可以与k-d树结合使用，形成动态k-d树，因为在k-d树中不允许使用普通的BST旋转。

随机树

随机树通过选择符合特定规则的随机树形状来工作。由于大多数随机选择的二叉搜索树形状高度较低（很不可能得到一个长链节点），这些树具有很高的平衡概率。

树堆

树堆，顾名思义，是二叉搜索树和二叉堆（或者更准确地说，是二叉搜索树和笛卡尔树）之间的混合体。树堆中的每个节点都带有均匀随机的权重（例如，一个随机的32位整数，或者一个介于0和1之间的随机实数），并且节点的排列满足以下条件：

节点按照树堆中的键形成二叉搜索树。
每个节点的权重小于或等于其子节点的权重。

这两个属性唯一确定了Treap的形状；事实上，对于任何一组（不同的）键和权重，都有一个唯一的Treap来保存这些键和权重。

理解Treap的一个有用视角是想象在树中存储的键上运行随机快速排序。在快速排序的第一轮中，我们选择一个随机的枢轴（可以想象选择具有最低权重的键），然后重新排列元素，使较小的元素移到枢轴的左侧（进入左子树），较大的元素移到枢轴的右侧（进入右子树）。然后我们递归地对这些元素进行排序（递归地构建树的其余部分）。因此，通过与显示随机快速排序的总成本为期望O(n log n)的分析相同，Treap中任何节点的期望深度为O(log n)。

向Treap中插入和删除元素可以使用非常简单的树旋转来完成。插入操作通常是先按照常规方式插入，然后将节点与其父节点进行旋转，直到其权重超过其父节点的权重。删除操作可以通过将节点与其较低权重的子节点进行旋转，直到节点变为叶子节点，然后删除该节点。

Zip Trees

Zip trees是一种替代treaps的方法，每个节点需要更少的随机位。与treaps类似，每个节点被分配一个随机权重，但这次是从几何分布而不是均匀分布中选择。规则是每个节点的权重必须大于其子节点的权重，但如果排名相同，则绑定的节点必须是其左子节点。这些规则，就像treaps一样，在插入或删除节点时通过执行旋转来保持，或者执行称为zipping或unzipping的等效操作来模拟旋转而不实际执行它们。

Zip trees被发明作为将skiplist编码为随机化二叉搜索树的一种方式。它们在期望上比treaps稍微高一些，但由于使用几何分布而不是均匀分布的随机变量，每个节点需要更少的随机位（treaps每个节点大约需要O(log n)位；zip trees每个节点大约需要O(log log n)位）。

Zip-Zip Trees（快速树）

快速树可以被看作是快速树和Treap的混合体。与快速树类似，快速树中的每个节点都有一个从几何分布中抽取的关联权重，并且像快速树一样，每个节点的权重大于其左子节点的权重，小于或等于其右子节点的权重。然而，每个节点还被分配了一个在一个小范围内均匀随机的第二个权重值，当比较权重时，如果两个节点具有相同的主要权重，则它们的次要权重被视为决胜者。这样做的效果是将具有相同权重的长序列节点重新塑造成漂亮的树形结构。因此，快速树每个节点只使用O(log log n)个随机位，但具有与Treap相同的高度保证 - 几乎是两全其美！

静态树

静态二叉搜索树是一种不允许插入或删除操作的二叉搜索树。它们通常用于已知或可以预估每个节点访问概率的情况下。

静态最优二叉搜索树

静态最优二叉搜索树是专门构建的二叉搜索树，旨在最小化查找树中的期望成本，假设每个节点的访问概率事先已知。例如，如果您正在构建一个用于存储电话中联系人信息的二叉搜索树，并且知道哪些人最有可能被查找，您可以将经常被呼叫的人放在树的较高位置，而较少被呼叫的人放在树的较低位置。

Don Knuth发现了一个O(n^2)时间复杂度的算法，用于根据每个节点的访问概率构建最优二叉搜索树。该算法是一种巧妙的动态规划解决方案，基于以下洞察力进行工作。首先，某个节点 - 我们不确定是哪个 - 必须成为根节点。然后，在选择根节点之后，我们将为左子树和右子树构建最优二叉搜索树，分别对应小于根节点和大于根节点的元素。这意味着只有O(n^2)个可能的子问题需要考虑，对应于要存储在树中的每个连续子范围。从简单的角度来看，确定任何一个子问题的解决方案将需要O(n)的时间，因为在每个子范围内都有O(n)个节点可以尝试作为根节点。然而，Knuth证明了这些枢轴选择方式存在一些巧妙的结构，使得整体评估复杂度为O(n^2)。

后来证明，在这样一棵树中查找的成本是O(1 + H)，其中H是键的概率分布的香农熵。这个数量H的范围从零（所有访问都是对一个键）到log n（所有键被查找的机会相等），取决于分布的偏斜程度。

权重均衡树

权重均衡树，有时也被误称为权重平衡树，是一种根据简单规则构建的静态树。选择根节点时，左右子树的访问概率之和尽可能接近，并且这些子树以相同的方式递归构建。

上述规则说“尽量使左右子树的权重相等”，因此并不奇怪以这种方式构建的树在每个子树的总概率质量方面是平衡的。具体来说，你可以证明每个子树的概率质量最多是其父树的2/3。通过一点数学推导，你还可以证明这些树的查找成本为O(1 + H)，与Knuth的最优树的预期查找成本相差一个常数因子。

天真地说，构建一个权重平衡的树需要O(n^2)的时间复杂度：你可以尝试将每个节点作为潜在的树根，并递归地构建左右子树的权重平衡树。然而，对于一组未排序的键，可以通过对键进行排序并使用巧妙的二分搜索来找到最佳根节点，从而将构建时间加速到O(n log n)。后续的研究表明，甚至可以通过使用非常巧妙的双边指数搜索，将构建时间进一步提高到O(n)，前提是使用一组已排序的键。

自调整树

自调整树试图以一种不同的方式实现良好的运行时间 - 通过根据查询动态地重新组织自身。通过适应对其进行的查询，它们通常可以在查询具有某种良好结构的情况下，在实际或理论上优于标准平衡树。

伸展树伸展树是最著名的自调整搜索树之一。伸展树是一种带有一个扭曲操作的普通二叉搜索树 - 每当插入、删除或查找一个节点时，该节点通过称为伸展的过程被移动到根节点。通过重复查看节点、其父节点和祖父节点，然后决定一系列旋转操作将根节点移动到更接近目标节点的位置来执行伸展操作。这些情况被称为zig、zig-zag和zig-zig，并且在实现上相当简单。

除了这个规则之外，伸展树对其形状没有任何限制。这意味着伸展树在传统意义上可能会变得非常不平衡。然而，伸展操作具有一些令人惊讶的特性，使得伸展树在摊还意义上非常快速。具体来说：

查找元素的摊销成本为O(log n)。
查找元素的摊销成本为O(1 + H)，其中H是节点访问分布的香农熵。换句话说，伸展树可以用作静态树的替代。
查找元素的摊销成本为O(log t)，其中t是自上次查询该项以来已访问的不同项数。换句话说，如果在每个时间点上树中有一组“热门”项，则查找的成本仅取决于热门项的数量，而不是树中存在的项数。
查找元素的摊销成本为O(log Δ)，其中Δ是查询项与上次查询项之间的秩差。也就是说，如果你想象树存储了一个排序数组的元素，查找的成本只取决于你在数组中距离上次查询项有多少步，而不是总共有多少项。

据推测，但尚未证明，伸展树在任何足够长的访问序列上都是动态最优的，也就是说没有其他自适应二叉搜索树能够超过伸展树的性能。

然而，每个操作执行旋转的开销，以及伸展树与并发不兼容且仅在摊还意义上保证，意味着伸展树不常用作“标准”二叉搜索树的实现。

Tango树

Tango树是一种二叉搜索树，由多个不同的红黑树串联在一起，其排列方式会随着访问而变化。Tango树通过一种非常不同的方式追求效率：它们被构建为保证在Tango树上执行的任何操作序列的成本最多为O(log log n · c*)，其中c*是对于任何平衡二叉搜索树结构执行该操作序列的最佳可能成本。

更具体地说，探戈树通过设想一个参考二叉树（实际上没有在任何地方构建），树的内容作为叶子节点。树中的每个节点都有一个首选子节点，这将使树的边缘分开成称为“首选路径”的路径。Tango树将每个路径存储为红黑树，并使用非首选边将每个红黑树链接到子红黑树。在查找时，更改参考树中的首选子节点，以使查找的键位于从根节点向下的首选路径上，并重新调整红黑树以匹配结果路径。

通过在探戈树中使用伸展树而不是红黑树，我们得到了多重伸展树，它在时间复杂度为O(log log n · c*)内执行其操作，但还保证每次查找的摊还时间为O(log n)，同时具有其他几个良好的性质（例如，在多重伸展树中按顺序查找每个项的成本为O(n)）。

如何保持二叉搜索树的平衡？

红黑树

平衡秩树

WAVL树

平衡树

BB[α]树

替罪羊树

随机树

树堆

Zip Trees

Zip-Zip Trees（快速树）

静态树

静态最优二叉搜索树

权重均衡树

Tango树

更多探索