algorithm - 从二叉搜索树构建 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

基本上，它所做的就是通过中序遍历 (O(n)) 将 BST 转换为排序数组或链表。然后，它递归地获取数组的中间元素，使其成为根，并使其子数组分别成为左右子数组的中间元素(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