从二叉搜索树构建 AVL 树

Question

我需要建议一种算法，该算法采用 BST（二叉搜索树），具有 2^(n + 1) - 1 键的 T1，并构建具有相同键的 AVL 树。该算法在最差和平均时间复杂度方面应该是有效的（作为 n 的函数）。

我不确定我应该如何处理这个问题。很明显，具有 2^(n + 1) - 1 键的 BST 的最小大小是 n（如果它是满的/平衡的，情况就是这样），但它对我有什么帮助？

有一种直接的方法是遍历树，每次将 T1 的根添加到 AVL 树，然后将其从 T1 中删除：

由于 T1 可能不平衡，删除在最坏情况下可能花费 O(n)
插入 AVL 的成本为 O(log n)
有2^(n + 1) - 1

所以总共要花费 O(n*logn*2^n)，而且贵得离谱。

但我为什么要从 T1 中删除？我在那里付出了很多，而且没有充分的理由。所以我想为什么不在 T1 上使用树遍历，并且对于我正在访问的每个节点，将它添加到 AVL 树中：

有 2^(n + 1) - 1 个节点，因此遍历将花费 O(2^n)（每个节点访问一次）
每次将当前节点添加到AVL中会花费O(logn)

所以总共要花费 O(logn * 2^n)。这是我能想到的最好的时间复杂度，问题是，它能以更快的方式完成吗？就像 O(2^n) 一样？某种方式可以使插入 AVL 树的成本仅为 O(1)?

我希望我说清楚了，我的问题属于这里。

非常感谢，

诺姆

Answer 1

有一种平衡 BST 并在线性时间内运行的算法称为 Day Stout Warren Algorithm

基本上它所做的就是通过 in-order 遍历 (O(n)) 将 BST 转换为排序数组或链表。然后，它递归地取数组的中间元素，使它成为根，并使其children分别成为左右子数组的中间元素（O(n)）。这是一个例子，

       UNBALANCED BST
            5
          /   \
         3     8
              / \
             7   9
            /     \
           6      10


        SORTED ARRAY
      |3|5|6|7|8|9|10|

现在这里是递归调用和结果树，

 DSW(initial array)

             7
 7.left = DSW(left array) //|3|5|6|
 7.right = DSW(right array) //|8|9|10|

             7
            / \
           5   9
 5.left = DSW(|3|)
 5.right = DSW(|6|)
 9.left = DSW(|8|)
 9.right = DSW(|10|)

             7
            / \
           5   9
          / \ / \
         3  6 8 10

从二叉搜索树构建 AVL 树

Building an AVL Tree out of Binary Search Tree

algorithm

avl-tree

time-complexity

binary-search-tree

data-structures