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

Question

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

编辑：这是我 github 上代码的 link：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) 复杂度，他们希望您使用散列 table.

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

Big-O for using a for loop to insert into an AVL

c

algorithm

big-o

asymptotic-complexity