c - 用于使用 for 循环插入 AVL 的 Big-O

Question

我正在为我申请的一家公司编写代码示例，他们要求我的代码在最坏的情况下在 O(n) 内运行。我决定使用 AVL 树，但要将我提供的值插入 AVL 树，我必须使用嵌套循环结构。这会使我的代码在最坏的情况下在 O(n²) 中运行还是在 O(n log n) 中运行？

编辑:这是我 github 上代码的链接:https://github.com/hsleiman1/Algorithms/blob/master/equilibriumIndexAVL.c

我的代码:

int equilibriumIndex(int A[], int N) {
    int i, newRoot = 1;

    while (newRoot < N) {
        node *leftTree = NULL;
        node *rightTree = NULL;
        for (i = 0; i < N; i++) {
            if (i == newRoot) continue;
            if (i < newRoot) leftTree = insert(leftTree, A[i]);
            if (i >= newRoot) rightTree = insert(rightTree, A[i]);
        }

        if (addSubTree(leftTree) == addSubTree(rightTree)) return newRoot;
        free(leftTree);
        free(rightTree);
        newRoot++;
    }
    return 0;
}

int addSubTree(node *subTree) {
     if (subTree == NULL)
         return 0;
     else
         return (subTree->value * subTree->repeat) + addSubTree(subTree->left) + addSubTree(subTree->right);
 }

 node *leafInit(node *leaf, int key) {
     leaf = (node*)malloc(sizeof(node));
     if (leaf != NULL) {
         leaf->value = key;
         leaf->left = NULL;
         leaf->right = NULL;
         leaf->repeat = 1;
     }
     return leaf;
 }

 node *insert(node *leaf, int key) {
     if (leaf == NULL) 
         leaf = leafInit(leaf, key);
     else if (key < leaf->value)
         leaf->left = insert(leaf->left, key);
     else
     if (key > leaf->value)
         leaf->right = insert(leaf->right, key);
     else
         leaf->repeat++;

     leaf = rotate(leaf, key);

     return leaf;
}

node *rotate(node *subTree, int key) {
     node *temp;
     int balance = getBalance(subTree);
     if (balance < -1) {
         temp = subTree->left;
         if (key > temp->value) {
             subTree->left = rightRotate(subTree->left);
             subTree = leftRotate(subTree);
         }
     } else
     if (balance > 1) {
         temp = subTree->right;
         if (key < temp->value) {
             subTree->right = leftRotate(subTree->right);
             subTree = rightRotate(subTree);
        }
     } else
     if (balance < -1 && key < subTree->value)
         subTree = leftRotate(subTree);
     else
     if (balance > 1 && key > subTree->value)
         subTree = rightRotate(subTree);

     return subTree;
 }

 node *leftRotate(node *leaf) {
     node *x = leaf->left;
     node *y = x->right;

     x->right = leaf;
     leaf->left = y;

     return x;
 }

 node *rightRotate(node *leaf) {
     node *x = leaf->right;
     node *y = x->left;

     x->left = leaf;
     leaf->right = y;

     return x;
 }

 int height(node *leaf) {
     if (leaf == NULL) return 0;
     else return max(height(leaf->left), height(leaf->right)) + 1;
 }
 int max(int num, int num1) {
     if (num < num1) return num1;
     else return num;
 }
 int getBalance(node *leaf) {
     return height(leaf->right) - height(leaf->left);
 }

Answer 1

使用 AVL 树永远不会使您的复杂度达到 O(n)。如果你做对了，这可能会很棘手，你会得到 O(n.log(n))，如果你做错了，你可能会得到一棵退化树和 O 的复杂度(n²)。

对于 O(n) 的复杂性，他们希望您使用哈希表。