在按顺序插入元素时保持二进制树平衡

Question

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

这一种选择是使用从排序后的数组或链表创造一个平衡树的标准方法,如在讨论这个问题,也这样的其他问题.但是,我想要一种方法,其中可以将一些元素插入到树中,然后对其执行查找,然后在其后添加其他元素,而不必将树分解为列表并重新制作整个事物.

另一个选择是使用许多自平衡树实现之一,AVL,AA,Red-Black等等.但是,所有这些都在插入过程中施加了某种开销,我想知道是否存在考虑到元素总是按递增顺序插入的约束,可能是一种避免这种情况的方法.

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

举个例子,假设我有以下树:

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

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

Answer 1

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

有正常的BST.这意味着如果我们设法在插入期间保持深度,则查找为O(log N).

在进行插入时(假设我们的元素大于之前的元素),您将从根到最右边的元素.当您遇到其子树是完美二叉树的节点(所有内部节点都有2个子节点且所有叶子处于相同深度)时,您将新节点作为此节点的父节点插入.

如果您到达树中最右侧的节点并且未应用先前的规则,则表示它具有左子节点,但它没有正确的子节点.因此,新节点成为当前节点的正确子节点.

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

如果我们尝试添加另一个节点,那么4的子树仍然不完美,也不是6的子树.6是最右边的节点,所以我们将7添加为6的右子节点.

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

如果我们使用这个算法,根的左子节点的子树将始终是完美的,并且右子节点的子树将永远不会具有比左子节点更高的高度.因此,整个树的高度将始终为O(log N),因此查找时间也是如此.插入也将花费O(log N)时间.

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

与我的其他答案中基于阵列的解决方案相比,查找的时间复杂度相同,但此BST的插入时间更短.