tem*_*def 3 algorithm tree big-o binary-search-tree data-structures
二叉搜索树上大多数操作的运行时间取决于树的高度。如果树很好地平衡，插入、删除、查找、后继、前趋、最小或最大查询的成本是 O(log n)。但是，如果树不平衡，这些操作的成本可能会上升到 O(n)。
如何在插入和删除元素时保持二叉搜索树的平衡？
有很多很多方法可以保持二叉搜索树的平衡，每种方法都会引入不同的权衡。一般来说，平衡二叉搜索树属于以下类别之一：
高度平衡树：试图使树的不同部分之间的高度差保持一定程度的树。
Rank-Balanced Trees：最近开发的高度平衡树的概括，其中每个节点都被赋予一个rank，并且节点试图将它们自己和它们的父节点之间的等级差异保持在较低的水平。
权重平衡树：尝试使树的不同区域中的节点数量保持一定程度的树。
随机树：随机化其形状并试图从而保持较低的整体高度的树。
静态树：树设计为具有适合特定查询集的特定形状。
Self-Adjusting Trees : 为响应访问而重塑自身以保持低查找成本的树。
以下是这些不同策略的简要概述，以及每种类型不同树的一些示例。
高度平衡的树，直观地，通过施加结构约束来工作，以确保某些子树的高度不能相差“太多”，对于“太多”的某些定义。它们通过确保树只能在存在大量节点的情况下增长到特定高度来保持树的整体高度较低。一些最常用的树属于这一类。例如：
AVL树，它们的发明者的首字母命名的，是原来的平衡二叉搜索树的数据结构，在1962年AVL树发明是遵守下列结构约束二叉树：每个节点的两个子树可以最多一个有高度差. 这是一个严格的结构约束：任何高度为 h 的 AVL 树都在 F h+2和 2 h 之间，其中 F n是第 n 个斐波那契数。
为了维持这个要求，每当插入或删除创建一个左子树和右子树的高度差为 ±2 的子树时，AVL 树都会执行树旋转。
由于严格的结构约束，AVL 树相对于节点数量往往具有非常低的高度。然而，这也意味着对插入或删除执行的旋转次数可能很高，因为单个插入或删除可以改变许多节点子树的相对高度。
AVL 树有几种现代变体。所述RAVL树（ř elaxed AVL树）通过允许在删除后更大程度的不平衡，减少工作的每个插入或删除操作期间所需的量概括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树中的一个节点，而红/黑树中的每个红色节点代表一个key，被“拉”到上面的黑色节点中它。另一方面，AA 树以 B 树为模型，其中每个节点具有 1 或 2 个键（2-3 树），使用类似的一组技术。AA 树还强制执行一条规则，即“红色”节点必须挂在它们被拉入的黑色节点的左侧。这减少了在插入或删除过程中要检查的案例数量，但也增加了可能需要执行的旋转次数。
经典红/黑树和 AA 树之间的“混合”是左倾红/黑树。这种树结构与红/黑树一样，将 2-3-4 树编码为二叉搜索树。但是，顾名思义，在黑色节点只有一个红色子节点的情况下，该红色子节点必须悬挂在其黑色父节点的左侧。
这减少了插入或删除中可能出现的情况的数量，但与 AA 树一样，增加了在树编辑期间必须执行的旋转次数。
等级平衡树为每个节点分配一个称为等级的数字，然后执行一组规则以确保节点及其子节点之间的等级差异不会“太大”。关于秩平衡树的原始论文表明，该树家族包括 AVL 树，并且（经过少量编辑）还包括红/黑树。
该WAVL树（w ^ EAK AVL树）是最有名的秩平衡树。它通过分配节点等级来工作，这样每个节点的等级最多可以比其子节点的等级大两倍。当元素永远不会从树中删除时，WAVL 树与 AVL 树相同，并且总是可以根据红/黑规则着色，因此在高度/形状上永远不会比红/黑树差。与红/黑树类似但与 AVL 树不同的是，WAVL 树最多需要在每次插入或删除时执行恒定次数的旋转。
权重平衡树旨在通过确保每个节点的左子树和右子树中的节点数之间的某种“良好”关系来保持树的整体高度较低。基本思想是，如果每个节点将剩余的节点分成一些不错的部分（比如 75% / 25%），那么树的每一步都会导致当前子树的大小几何衰减，确保树具有对数高度.
BB [？]树（树b ounded b alance，参数ω）二叉搜索树，其中每个节点的子树具有“重量”，即总是至少一个？父母“体重”的一小部分。（在 BB[?] 树中，节点的权重由其子树中的节点总数加一给出。）如 ? 越来越接近1/2，左右子树的相对大小必须越来越接近。这意味着必须做更多的工作来保持树的形状，但整体树的高度会变低。作为 ？变小，左右子树的相对大小约束较少，这意味着插入或删除元素的工作更少，但树的高度变得越来越大。
像上面提到的所有树一样，BB[?] 树在插入或删除后使用树旋转来重新排列节点以保持其平衡条件。BB[?] 树的原始版本在 ? 大约 0.25，这意味着树中的每一步都将保证至少 25% 的剩余节点不再位于当前搜索的子树中。
替罪羊树是重量平衡树和高度平衡树的混合体。树本身是一棵权重平衡的树，因为有一个参数 ? （与来自 BB[?] 树的 ? 参数无关）使得每个节点的两个子树的大小最多为? 乘以节点本身的大小。这里，节点的“大小”是其子树中的节点数。
与上述平衡树类型不同，替罪羊树不（直接）使用旋转来执行重新平衡。相反，每当执行使树“太高”而无法进行权重平衡的插入时，它会沿着插入路径向后搜索以找到权重未正确平衡的节点，然后重建整个子树以使其完美-均衡。从这个意义上说，虽然树的形状是重量平衡树的形状，但重新平衡的策略是通过寻找高度平衡违规来工作的。
由于最佳地重新平衡违规子树的成本，这种方法不能保证插入或删除的最坏情况 O(log n) 性能。但是，它确实给出了每次插入或删除的摊销O(log n) 成本，因为很少需要进行大型重建，并且在完成大型重建后，树最终会完美平衡。
重建坏子树的实际逻辑可以通过Day-Stout-Warren 算法仅使用 O(1) 辅助存储空间在线性时间内完成，该算法使用一组巧妙的树旋转优化重建 BST 以达到完美平衡。
替罪羊树通常用作较大数据结构中的构建块，其中通过旋转重新平衡不是一种选择。例如，替罪羊树可以与kd 树结合形成动态 kd 树，因为不允许在 kd 树中进行正常的 BST 旋转。
随机树的工作原理是根据某些规则选择随机树的形状。因为大多数随机选择的二叉搜索树形状的高度都很低（你不太可能得到很长的节点链），所以这些树很可能是平衡的。
Treaps是，顾名思义，二叉查找树和一之间的混合二元堆（或者，更准确地说，二叉查找树和一个之间笛卡尔树）。treap 中的每个节点都用均匀随机的权重（例如，一个随机的 32 位整数，或一个介于 0 和 1 之间的随机实数）进行注释，并且节点的排列使得
这两个属性唯一地决定了垃圾的形状；事实上，对于任何一组（不同的）键和权重，只有一个 treap 持有这些键和权重。
理解陷阱的一个有用的观点是想象对存储在树中的键运行随机快速排序。在第一轮快速排序中，我们选择一个随机主元（假设选择权重最低的键），然后对元素重新排序，使较小的元素位于主元的左侧（进入左子树），较大的元素进入主元的左侧枢轴的右侧（进入右子树）。然后我们递归地对这些元素进行排序（递归地构建树的其余部分）。结果，通过显示随机快速排序的总成本预期为 O(n log n) 的相同分析，treap 中任何节点的预期深度为 O(log n)。
可以使用非常简单的树旋转来执行对 treap 的插入和删除操作。插入是通过像往常一样插入来完成的，然后将节点与其父节点一起旋转，直到其重量超过其父节点的重量。删除可以通过旋转节点及其较低权重的子节点直到节点成为叶节点，然后删除节点来完成。
Zip 树是 treaps 的替代方案，每个节点需要较少的随机位。像 treaps 一样，每个节点都被分配了一个随机权重，尽管这次来自几何分布而不是均匀分布。规则是每个节点的权重必须大于其子节点的权重，但如果排名相同，则绑定节点必须是其左子节点。这些规则，就像陷阱一样，通过在插入或删除节点时执行旋转来保留，或者执行称为压缩或解压缩的等效操作，模拟旋转而不实际执行它们。
Zip 树是作为一种将跳过列表编码为随机二叉搜索树的方法而发明的。它们在预期上往往比 treaps 略高，但由于使用几何而不是均匀随机变量，每个节点需要更少的随机位（treaps 每个节点需要大约 O(log n) 位；zip 树需要大约 O(log log n) 每个节点的位数。）
静态二叉搜索树是根本不允许插入或删除的二叉搜索树。它们通常用于每个节点的访问概率已知或可以提前估计的情况。
静态最优 BST是专门构建的二叉搜索树，以最小化树中查找的预期成本，假设每个节点的访问概率是预先知道的。例如，如果您正在构建一个 BST 来存储手机内的联系信息，并且知道哪些人最有可能被查找，那么您可以构建 BST，将通常被称为的人放在树中的位置更高，频率更低——叫人倒在树下。
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)。
自调整树试图以不同的方式实现良好的运行时——通过动态地重构自己以响应查询。通过适应由它们构成的查询，它们通常可以在实际或理论上在查询有一些很好的结构的情况下胜过标准的平衡树。
Splay 树是最著名的自调整搜索树。splay 树是一种常规二叉搜索树，有一个转折——每当插入、删除或查找节点时，该节点都会通过称为splaying的过程向上移动到根节点。展开操作是通过反复查看节点、其父节点和祖父节点来执行的，然后决定将根移近根的一系列旋转。这些案例称为zig、zig-zag和zig-zig并且实施起来相当简单。
除了这条规则，张开的树对其形状没有任何限制。这意味着张开的树在传统意义上会变得高度不平衡。然而，splay 操作有一些惊人的特性，使得 splay 树在摊销的意义上非常快。具体来说：
有人怀疑，但没有证明，伸展树是动态最优的，因为没有其他自调整 BST 可以在任何足够长的访问序列上胜过伸展树。
然而，每个操作执行轮换的开销，加上张开树不能很好地处理并发以及它们的保证仅在摊销的意义上，意味着张开树并不常用作“标准”BST 实现。
探戈树是一种二叉搜索树，它由几个不同的红/黑树组成，它们以每次访问的方式变化。探戈树以一种与这里的其他树非常不同的方式来提高效率：它们的构建是为了保证探戈树上的任何操作序列的成本最多为 O(log log n · c*)，其中 c*是在任何平衡的 BST 结构上执行该操作序列的最佳可能成本。
更具体地说，探戈树的工作原理是将树的内容作为叶子的参考二叉树（实际上并未在任何地方构建）。树中的每个节点都有一个首选子节点，这会导致树将边拆分为称为“首选路径”的路径。探戈树将这些路径中的每一条存储为红/黑树，使用非首选边将每个红/黑树链接到子红/黑树。在查找时，参考树中的首选子树被更改，以便查找的键位于从根向下的首选路径上，并且红/黑树被重组以匹配结果路径。
通过在探戈树中使用张开树而不是红/黑树，我们得到了多张树，它也按 O(log log n · c*) 执行操作，但也保证了每次查找的分摊时间为 O(log n)以及其他几个不错的属性（例如，在多重播放树中顺序查找每个项目的成本是 O(n)）。
还有许多其他漂亮的数据结构，我没有时间在这里详细介绍。这是其他值得查找的示例：
B 树广泛用于数据库和文件系统，以及其他数据结构中的灵感和构建块。红/黑树和 AA 树都被设计为特定 B 树作为二叉搜索树的编码。
Skiplist是平衡 BST 的替代方案，它通过在项目集合中运行多个分层链表来工作。原始的跳过列表数据结构是随机的，并保证 O(log n) 预期时间操作（这个结构，适应 BST，给出了 zip 树）。后来的工作产生了确定性跳过列表，它通过对 2-3-4 树进行建模来工作，使它们与红/黑树基本相同，只是具有完全不同的表示形式。
Iacono 的工作集结构使用一组平衡的 BST 来存储项目，以保证对最近查询的项目的查找比对旧项目的查找运行得更快。它是 Iacono统一结构中的一个构建块，这使得查找最近查询项目（从技术意义上）附近的项目的成本比正常情况快得多。
Geometric Greedy的实际名称对于 Stack Overflow 来说有点过于花哨了，它是一种 BST，据推测它对二叉搜索树来说是“尽其所能”。它是一个自我调整的树，它查看过去的访问模式来重构树，以最小化每次查找触及的节点数。这是否真的是最佳 BST 还有待观察。
手指搜索树是围绕一个称为手指的公共接入点重组的 BST，对靠近手指的项目的查询比对远离手指的项目的查询运行得快得多。
希望这可以帮助！