建立AVL树的二进制搜索树

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

我不知道我该如何解决这个问题。很明显，具有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）？

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

非常感谢你，

诺姆

来源

2016-07-04 Noam

存在着结余BST和所谓Day Stout Warren Algorithm

线性时间运行的算法基本上它是所有的BST转换成有序阵列或通过按顺序遍历（O（n））进行链表。然后，递归地取数组的中间元素，使其成为根，并使其子元素分别为左和右子阵列的中间元素（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

来源

2016-07-04 17:27:30

非常感谢你的男人 – Noam

@Noam没问题，如果你找到了答案有帮助那么请不要忘记将其标记为已接受。祝你好运！ –

会做。你也可以给我的问题+1，如果它是清楚和有用的。 – Noam

建立AVL树的二进制搜索树

回答

相关问题