避免 BST 中的长 "bare" 分支和平衡

Question

所以我正在对二叉搜索树进行一些试验，这里需要一些提示。

我想要实现的是 self-balancing BST，但不是通常的。我正在寻找的 BST 应该只有在出现长 "bare" 分支时才会自行平衡。请参阅下面的示例，以便更好地理解我的意思。

         add(6,5,7,1,2,3,4);

          Result BST                        Balanced 
        (before balance)       
               6                              6
            5     7        balance       3         7
         1                  -->       1     4
           2                            2     5
             3
                4         


     x=5
    (long bare branch of length x occurs (5,1,2,3,4)) 
    Balancing starts only when a long bare branch occurs in the BST!
    In this case, after add(4);

长裸分支：最多有一个child的x个节点的序列，其中x是给定的常数（例如，它是5）。

因此，一旦我将 (4) 添加到示例 BST，就会出现一个长的裸分支，然后 BST 才需要修复。所以在某种程度上，它有点像 AVL 树，但只有当一定数量的不平衡节点堆积时才开始平衡节点。

我对这个的可能实现有一些想法，但我认为它非常低效（我必须在 add() 或 remove() 之后遍历整个树，并且只需计算连续的节点一个或更少 child.)

对于这种平衡和裸分支出现检测的更有效算法有什么想法吗？

非常感谢您。

Answer 1

长"bare"分支检测：

add():只需要往上走x个节点。由于 x 是一个（应该很小的）常数，所以 O(1)
remove()：向上查找，直到找到具有两个 children 或没有 parent 的节点，或者达到 x 步。如果还没有到x，往下看，直到找到一个none有两个以上的children（或none）。不能超过 x 步，所以又是 O(1)。

避免 BST 中的长 "bare" 分支和平衡

Avoiding long "bare" branches in BST and balancing

algorithm

binary-search-tree