AVL树联合最坏情况的复杂性
我有一个空的AVL树和两棵AVL树。我想结合两棵树的结合。我这样做是使用树木和插入（o（log（log（n）））的一部分遍历的一部分IE中的一部分遍历的遍历。
AVLTree TreeUnion(t1, t2){
newTree = AVLTreeNew();
traverse(t1->root, newTree);
traverse(t2->root, newTree);
return(newTree);
}
void traverse(AVLTree t1, AVLTree newTree){
if(t == NULL){
return;
}
traverse(t->left);
AVLInsert(newTree, t->item);
traverse(t->left);
}
我在两棵树上都这样做。
我对此的复杂性分析感到困惑，因为我想到了它和树的大小不断增加，因此我们从o（1）或o（log（1））的大小的树开始，因为没有旋转，所以我不太确定。我们得到o（1/log（1）） + O（log（2）） + O（log（3）） + O（log（4）） + O（log（5）） + O（log（log（n-1）） ） + o（log（n）） + o（n） + o（m），
我们得到对数时间的总和 +
如果t1-＆gt; size = x; size = x; = 3和t2-＆gt; size = y = 3。我将其计算为log（1） + log（2） + log（3） 大小
+ t2-＆gt ;
; size 朝着正确的方向迈进。
I have an empty AVL Tree and two AVL Trees. I want to get the union of both trees. I do so using an inorder traversal of both trees and inserting (O(log(n)) in the do part of the traversal ie.
AVLTree TreeUnion(t1, t2){
newTree = AVLTreeNew();
traverse(t1->root, newTree);
traverse(t2->root, newTree);
return(newTree);
}
void traverse(AVLTree t1, AVLTree newTree){
if(t == NULL){
return;
}
traverse(t->left);
AVLInsert(newTree, t->item);
traverse(t->left);
}
I do this on both trees.
I'm confused about the complexity analysis of this because I thought about it and the tree size is constantly increasing so we start off with a tree of size one which is either O(1) or O(log(1)) I'm not too sure because there's no rotation. The tree size is increasing so we get O(1/log(1)) + O(log(2)) + O(log(3)) + O(log(4)) + O(log(5)) + O(log(n-1)) + O (log(n)) + O(n) + O(m)
We get a sum of logarithmic times + the sum of the primitive operations of traversing through the tree in complexity calculation.
if t1->size = x = 3 and t2->size = y = 3. I have calculated this to be. Log(1) + Log(2) + Log(3) + Log(4) + Log(5) + Log(6) + t1->size + t2->size.
Giving an overall worst-case complexity of O(x + y). Is this correct or am I doing it wrong? If so why? I have trouble calculating the complexity of recursive functions.
Any steps toward the right direction would be appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
如果新树的总尺寸为n，则插入的前半部分将小于N/2，而在插入片段的后半部分将至少N/2。
考虑仅在后半部分：这至少需要ω（n/2 * log（n/2））=ω（n log n）时间。
您的整个算法不能比后半部分更快，因此您有O（n log n）算法。
If the total size of the new tree is N, then it will be less than N/2 for the first half of the inserts, and at least N/2 for the last half of the inserts.
Consider just the last half: This takes at least Ω(N/2 * log(N/2)) = Ω(N log N) time.
Your whole algorithm can't be faster than just the last half, so you have an O(N log N) algorithm.