avl二叉树增删改查c++

AVL树是一种自平衡的二叉搜索树，可以高效地执行增删改查操作。下面以C语言为例来介绍AVL树的增删改查操作。

首先，我们需要定义AVL树节点的数据结构，包括节点的值、左子树指针、右子树指针和节点的高度。

typedef struct AVLNode {
    int val;
    struct AVLNode* left;
    struct AVLNode* right;
    int height;
} AVLNode;

接下来，我们可以实现AVL树的插入、删除、更新和查询操作。

1. 插入操作：

插入节点的基本流程是先按照二叉搜索树的规则找到插入位置，然后更新节点的高度，并进行平衡操作，使树保持平衡。

AVLNode* insert(AVLNode* root, int val) {
    if (root == NULL) {
        root = createNode(val);
    }
    else if (val < root->val) {
        root->left = insert(root->left, val);
    }
    else if (val > root->val) {
        root->right = insert(root->right, val);
    }
    root->height = max(height(root->left), height(root->right)) + 1;
    int balance = getBalance(root);

    if (balance > 1 && val < root->left->val) {
        return rightRotate(root);
    }

    if (balance < -1 && val > root->right->val) {
        return leftRotate(root);
    }

    if (balance > 1 && val > root->left->val) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    if (balance < -1 && val < root->right->val) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

2. 删除操作：

删除节点的基本流程是先按照二叉搜索树的规则找到待删除节点，然后更新节点的高度，并进行平衡操作，使树保持平衡。

AVLNode* delete(AVLNode* root, int val) {
    if (root == NULL) {
        return root;
    }
    else if (val < root->val) {
        root->left = delete(root->left, val);
    }
    else if (val > root->val) {
        root->right = delete(root->right, val);
    }
    else {
        if (root->left == NULL || root->right == NULL) {
            AVLNode* temp = root->left ? root->left : root->right;
            if (temp == NULL) {
                temp = root;
                root = NULL;
            }
            else {
                *root = *temp;
            }
            free(temp);
        }
        else {
            AVLNode* temp = minValueNode(root->right);
            root->val = temp->val;
            root->right = delete(root->right, temp->val);
        }
    }
    if (root == NULL) {
        return root;
    }
    root->height = max(height(root->left), height(root->right)) + 1;
    int balance = getBalance(root);

    if (balance > 1 && getBalance(root->left) >= 0) {
        return rightRotate(root);
    }

    if (balance < -1 && getBalance(root->right) <= 0) {
        return leftRotate(root);
    }

    if (balance > 1 && getBalance(root->left) < 0) {
        root->left = leftRotate(root->left);
        return rightRotate(root);
    }

    if (balance < -1 && getBalance(root->right) > 0) {
        root->right = rightRotate(root->right);
        return leftRotate(root);
    }

    return root;
}

3. 更新操作：

更新操作即是先删除旧节点，然后插入新节点。

AVLNode* update(AVLNode* root, int oldVal, int newVal) {
    root = delete(root, oldVal);
    root = insert(root, newVal);
    return root;
}

4. 查询操作：

查询操作即是在树中按照二叉搜索树的规则查找目标值。

AVLNode* search(AVLNode* root, int val) {
    if (root == NULL || root->val == val) {
        return root;
    }
    else if (val < root->val) {
        return search(root->left, val);
    }
    else {
        return search(root->right, val);
    }
}

以上就是使用C语言实现AVL树的插入、删除、更新和查询操作的示例代码，希望对你有帮助。