c - Time Complexity的拆分AVL Tree功能

我有以下用于拆分 AVL tree 的代码,但我不太确定它是否具有 O(log(n)) 或 O((log n)2) 的 Time Complexity。

笔记:

  • join 的复杂度是 O(log(n)) 其中 nNumber of Elements in Two Trees combined
  • insert 的复杂度也是 O(log(n)),其中 nNumber of Elements in the Tree
node* split(node* t, int k)
    {  

        if (t==NULL) 
        {
            return new_node(0);
        }

        if(t->val == k) {
           node* temp = new_node(0);
           temp->left=t->left;
           temp->right=t->right;

           temp->height = max(height(temp->left), height(temp->right)) +1;
           printf("%d TEMP\n", t->val);
           display(temp);
           return temp;    
       }
       if(k < t->val) {
           node* temp = split(t->left, k);
           temp->right = join(temp->right, t->right);
           temp->right = insert(temp->right, t->val);
           return temp;
       }
       if(k > t->val) {
           node* temp = split(t->right,k);
           printf("t->left\n");
           node* blah1, *blah2;
           blah1 = t->left;
           blah2 = temp->left;
           temp->left = join(blah1, blah2);
           temp->left = insert(temp->left, t->val);
           return temp;
        }
    }

回答1

它应该有 O(log (n)^2) 最差 time complexity,因为在最坏的情况下,您将调用 split lg n(即在每个深度)并且您的函数需要 O(log n) 在每个深度调用 join,log n * O(log n) = O(log (n)^2)

相似文章

随机推荐

最新文章