【数据结构】AVL树

AVL树

AVL树（Adelson-Velsky和Landis树）是一种自平衡二叉搜索树。它通过维护树的高度平衡来确保树的操作复杂度为O(log n)。它通过在每个节点上跟踪平衡因子来保持树的平衡。平衡因子是左子树和右子树高度之间的差值。

AVL树的特性

• 每个节点都有一个平衡因子。
• 平衡因子等于左子树高度减去右子树高度。
• 平衡因子必须为-1、0或1。
• 当插入或删除节点后，平衡因子可能会发生改变，如果平衡因子超出了-1到1的范围，需要通过旋转操作来调整树的结构。

AVL树的操作

AVL树提供了基本的操作，包括插入、删除和查找操作。下面是这些操作的C语言实现。

定义节点结构

首先，我们定义AVL树的节点结构。节点包含一个整数值 value，指向左子树和右子树的指针 left 和 right，以及一个表示子树高度的字段 height。

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

左旋和右旋操作

AVL树使用左旋和右旋操作来调整树的结构，确保树的平衡。

// 计算节点的高度
int height(AVLNode *node) {
    if (node == NULL) {
        return 0;
    }
    return node->height;
}

// 更新节点的高度
void updateHeight(AVLNode *node) {
    if (node) {
        node->height = 1 + fmax(height(node->left), height(node->right));
    }
}

// 左旋操作
AVLNode* leftRotate(AVLNode *z) {
    AVLNode *y = z->right;
    AVLNode *T2 = y->left;

    // 执行左旋
    y->left = z;
    z->right = T2;

    // 更新节点高度
    updateHeight(z);
    updateHeight(y);

    // 返回新的根节点
    return y;
}

// 右旋操作
AVLNode* rightRotate(AVLNode *z) {
    AVLNode *y = z->left;
    AVLNode *T2 = y->right;

    // 执行右旋
    y->right = z;
    z->left = T2;

    // 更新节点高度
    updateHeight(z);
    updateHeight(y);

    // 返回新的根节点
    return y;
}

左旋操作将节点 z 的右子树调整为其父节点，右旋操作将节点 z 的左子树调整为其父节点。这些操作用于调整树的结构并保持平衡。

平衡因子计算

平衡因子是AVL树的一个重要属性。它表示节点的左子树高度减去右子树高度的差值。

int getBalance(AVLNode *node) {
    if (node == NULL) {
        return 0;
    }
    return height(node->left) - height(node->right);
}

插入操作

插入操作在AVL树中插入一个新的值，同时确保树保持平衡。插入后，需要调整树的结构以保持平衡。

// 插入操作
AVLNode* insert(AVLNode *node, int value) {
    // 执行标准的二叉搜索树插入操作
    if (node == NULL) {
        AVLNode *newNode = (AVLNode *)malloc(sizeof(AVLNode));
        newNode->value = value;
        newNode->height = 1;
        newNode->left = newNode->right = NULL;
        return newNode;
    }

    if (value < node->value) {
        node->left = insert(node->left, value);
    } else if (value > node->value) {
        node->right = insert(node->right, value);
    } else {
        // 值已存在于树中
        return node;
    }

    // 更新节点的高度
    updateHeight(node);

    // 获取平衡因子
    int balance = getBalance(node);

    // 根据平衡因子进行调整

    // 左左情况
    if (balance > 1 && value < node->left->value) {
        return rightRotate(node);
    }

    // 右右情况
    if (balance < -1 && value > node->right->value) {
        return leftRotate(node);
    }

    // 左右情况
    if (balance > 1 && value > node->left->value) {
        node->left = leftRotate(node->left);
        return rightRotate(node);
    }

    // 右左情况
    if (balance < -1 && value < node->right->value) {
        node->right = rightRotate(node->right);
        return leftRotate(node);
    }

    return node;
}

插入操作首先执行标准的二叉搜索树插入操作，将新值插入树中。然后，更新节点的高度并获取平衡因子。根据平衡因子的值，决定是否需要进行旋转操作来保持树的平衡。

删除操作

删除操作在AVL树中删除特定值，同时确保树保持平衡。删除操作可能需要多种情况处理。

// 找到最小值节点
AVLNode* minValueNode(AVLNode *node) {
    while (node->left != NULL) {
        node = node->left;
    }
    return node;
}

// 删除操作
AVLNode* deleteNode(AVLNode *root, int value) {
    // 执行标准的二叉搜索树删除操作
    if (root == NULL) {
        return root;
    }

    if (value < root->value) {
        root->left = deleteNode(root->left, value);
    } else if (value > root->value) {
        root->right = deleteNode(root->right, value);
    } else {
        // 找到要删除的节点
        if (root->left == NULL) {
            AVLNode *temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            AVLNode *temp = root->left;
            free(root);
            return temp;
        }

        // 找到右子树的最小值节点
        AVLNode *temp = minValueNode(root->right);
        // 复制最小值节点的值到当前节点
        root->value = temp->value;
        // 递归删除右子树的最小值节点
        root->right = deleteNode(root->right, temp->value);
    }

    // 更新节点的高度
    updateHeight(root);

    // 获取平衡因子
    int balance = getBalance(root);

    // 根据平衡因子进行调整

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

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

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

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

    return root;
}

删除操作首先执行标准的二叉搜索树删除操作。删除后，更新节点的高度并获取平衡因子。根据平衡因子的值，决定是否需要进行旋转操作来保持树的平衡。

查找操作

查找操作在AVL树中查找特定值。查找过程与二叉搜索树类似，但AVL树能够在操作后确保树的平衡。

AVLNode* search(AVLNode* node, int value) {
    if (node == NULL || node->value == value) {
        return node;
    }

    // 根据值的大小决定查找方向
    if (value < node->value) {
        return search(node->left, value);
    } else {
        return search(node->right, value);
    }
}

查找操作递归地遍历树，根据值的大小选择左子树或右子树进行查找。

总结

AVL树是一种自平衡二叉搜索树，通过维护树的高度平衡来确保树的操作复杂度为O(log n)。它提供了查找、插入和删除操作的对数时间复杂度，非常适合需要快速操作和高性能的数据结构。