algorithm - 基于左右子树大小的平衡二叉搜索树

Question

我有两个问题:

1. 近平衡 BST 和近完全二叉树有什么区别。即使前者的定义很明确，我们也可以区分，但无法得到相关的文章。

2. 今天，在我的类里面，我被教导要平衡的条件是:

   max( size(root.left) , size(root.right) ) <= 3*n/4 ------------ (eqn 1).
   Hence, H(n) = height for the tree of n nodes following the above property < = 1+H(3*n/4).
   Continuing the recursive steps we get the bound for logn.

   我的问题是，这是一种特定类型的 BST 吗？例如，在 AVL 树的情况下，我记得条件是左右 child 的高度差异最多为 1，或者这是一个更一般的结果，可以减少前面所述的等式 1 以证明结果也适用于 AVL 树？即任何 Balanced BST 都会导致 sibling 的高度差异最多为 1 ?
   如果它与 AVL 不同，我们如何管理这种新型树中的插入和删除操作？

编辑:另外，如果你能解释为什么只有 3*n/4？
我的想法:这是因为我们可以肯定地说 H(n) <= 1+H(3*n/4)，因为如果我们取 3n/5 之类的东西小于 3n/4 那么 H(3n/5)不一定小于 H(2n/5)，因为 3n/5 和 2n/5 的比率小于 2，而且我们知道节点数的因子 2 会使高度增加 1。所以我们肯定不会写 H(n) <= 1 + H(3n/5)，也可能是 H(2n/5) 代替 H(3n/5)，对吗？

Answer 1

1. 几乎完整 BST 是所有级别都已填充的 BST，最后一个级别除外。这里的定义有些困惑(有人称此属性完美)。请引用wikipedia为此。
   平衡 是一个不太严格的标准，即所有(几乎)完整的 BST 都是平衡的，但并非所有平衡的 BST 都是完整的。在那篇维基百科文章中也有一个定义。在我的世界中，BST 是平衡的，如果它导致 O(log n) 操作成本。

2. 例如，可以说 BST 是平衡的，如果每个子树最多有 epsilon * n 个节点，其中 epsilon < 1(例如 epsilon = 3/4 或什至 epsilon = 0.999 -- 这是实际上根本不平衡)。原因是这样的 BST 的高度大致是 log_{1/epsilon} n = log_2 n/(- log_2 epsilon) = O(log n)，但是 1/(- log_2 0.99) = 99.5 是一个巨大的持续的。您可以尝试使用 epsilon = 1/2 的通常比率来证明这一点，其中两个子树的大小大致相同。

我不知道使用这个 3/4 的常见 BST。例如，常见的 BST 是 Red-Black-Trees , Splay-Trees或者 - 如果你在硬盘上 - 整个系列 B-Trees .对于您的示例，您可能可以通过用两个整数分别表示左子树和右子树中的节点数来增加每个节点来实现这些操作。插入或删除某些内容时，您会在从根部走到叶子(或向上)时更新数字，如果条件成立，则进行轮换。