BST二叉搜索树

先解释两个树中常用的概念：

• 深度：我们将节点的深度定义为它距离根节点的距离。为了保持一致性，我们说根节点的深度为 0。
• 高度：我们将树的高度定义为最深节点的深度。

如果树的高度接近 N，我们称其为“细长”的；如果树的高度接近 logN，我们称其为“茂密”的。对于获取节点的操作，我们希望高度尽可能小，因此更倾向于“茂密”的 BST。

树的高度决定了最坏情况下的运行时间，因为在最坏情况下，我们要查找的节点位于树的底部。平均深度决定了平均情况下的运行时间。

普通的 BST 树在递增顺序下插入元素，会导致树变得细长，极端情况时间复杂度变为 O (N)，因此我们要想办法避免这样的情况。

B 树

有个疯狂的想法：我们干脆永远不添加叶节点！插入时，我们只在当前的叶节点添加。这样，高度永远不会增加。B 树的核心思想是将底层的节点过度填充，以防止树的高度增加。这使我们能够确保最大高度为 logN。

但是如果不断往现有的节点添加元素，那么这个节点就变成一个极长的链表，复杂度也会来到 O (N)。因此我们会限制一个节点的长度，一般是 3 或者 4。

当添加一个节点的时候，超出了节点长度的限制 L，那么就会把这个节点分成三份：

• 中点的元素（取左）：移动到父节点里面
• 比中点小的元素：开辟一个新的叶子
• 比中点大的元素：保持在原来的叶子不动

B 树不变的特性

BST 的插入顺序会影响 BST 的结构，这对于 B 树也是一样的：2, 3, 4, 5, 6, 1, 7 插入使得高度只有 1，而 1, 2, 3, 4, 5, 6, 7 插入则使得高度为 2。但是不管怎么样，B 树有些特性是不变的：

• 所有叶子节点必须与源节点保持相同的距离。
• 一个含有 k 个元素的非叶节点必须恰好有 k+1 个子节点。

这两个特性使得 B 树始终保持茂密。

B 树中搜索总运行时是 O(logN)。

总结

BSTs 的最佳情况高度为 Θ(logN) ，最坏情况高度为 Θ(N) 。大 O 不是最坏情况的同义词！

B 树是对二叉搜索树的改进，避免了 Θ(N) 的最坏情况。

• 节点可以包含 1 到 L 个项目。
• 它几乎和普通的 BST 一样工作。
• add 操作通过向现有的叶节点中添加元素来工作。
• 如果节点过于拥挤，它们会分裂。
• 生成的树具有完美的平衡。操作的运行时是 O(logN) 。