algorithm - 按顺序插入元素时保持二叉树平衡

Question

我想知道当已知元素总是按顺序插入时，是否有合适的算法来维持二叉树的平衡。

一个选项是使用标准方法从排序数组或链表创建平衡树，如 this 中所述。问题，还有this其他问题。但是，我想要一种方法，可以将一些元素插入树中，然后对其执行查找，然后再添加其他元素，而不必将树分解为列表并重新制作整个东西。

另一种选择是使用许多自平衡树实现中的一种，AVL、AA、Red-Black 等。但是，所有这些都会在插入过程中产生某种开销，我当时考虑到元素总是以递增顺序插入的约束，想知道是否有办法避免这种情况。

所以，为了清楚起见，我想知道是否有一种方法可以维护平衡的二叉树，这样我就可以在任何时候向其中插入任意新元素并保持树的平衡，提供新元素在树的排序中比树中已经存在的所有元素更大。

举个例子，假设我有下面这棵树:

       4
      / \
     /   \
    2     6
   / \   / \
  1   3 5   7

如果我知道元素将大于 7，是否有一种简单的方法可以在插入新元素时保持平衡？

Answer 1

如果您真的有兴趣使用 BST(我认为这不是最佳选择，您可以在我的其他答案中阅读)，您可以这样做:

具有正常的 BST。这意味着查找是 O(log N)，如果我们设法在插入期间保持深度。

当进行插入时(假设我们有一个比之前所有元素都大的元素)，你从根元素走到最右边的元素。当遇到子树为完美二叉树的节点(所有内部节点都有 2 个子节点且所有叶子都在同一深度)时，将新节点作为该节点的父节点插入。

如果您到达树中最右边的节点并且您没有应用之前的规则，这意味着它有一个左 child ，但没有右 child 。因此，新节点成为当前节点的右子节点。

比如下面第一棵树，4的子树不是完美的，但是5的子树是(根据定义，只有一个节点的树是完美的)。因此，我们将 6 添加为 5 的父级，这意味着 4 现在是 6 的父级，而 5 是 6 的左子级。

如果我们尝试添加另一个节点，4 的子树仍然不完美，6 的子树也不完美。而 6 是最右边的节点，所以我们添加 7 作为 6 的右 child 。

     4             4             4
    / \           / \           / \
   /   \         /   \         /   \
  2     5 -->   2     6 -->   2     6
 / \           / \   /       / \   / \
1   3         1   3 5       1   3 5   7

如果我们使用这个算法，根的左 child 的子树将永远是完美的，而右 child 的子树的高度永远不会比左 child 的高。因此，整棵树的高度总是 O(log N)，查找时间也是如此。插入也将花费 O(log N) 时间。

与自平衡 BST 相比，时间复杂度相同。但是这个算法应该更容易实现，而且实际上可能比它们更快。

与我另一个答案中基于数组的解决方案相比，查找的时间复杂度是相同的，但这个 BST 的插入时间更差。