跳到主要内容

平衡二叉树详解

1. 平衡二叉树的定义​

平衡二叉树（Balanced Binary Tree），也称为AVL树，是一种高度平衡的二叉查找树。它的特点是对于每个节点，左子树和右子树的高度差不超过1。具体来说，对于任意节点 (N) ：

∣height(Nleft)−height(Nright)∣≤1| \text{height}(N_{\text{left}}) - \text{height}(N_{\text{right}}) | \leq 1

2. 平衡因子​

平衡因子（Balance Factor）是用于衡量节点的左右子树高度差的指标。对于节点 (N) ，其平衡因子定义为：

BF(N)=height(Nleft)−height(Nright)\text{BF}(N) = \text{height}(N_{\text{left}}) - \text{height}(N_{\text{right}})

3. 操作​

平衡二叉树的操作包括插入、删除和旋转。以下是这些操作的详细说明和C语言实现。

3.1 插入操作​

插入节点后，可能会导致树失去平衡，需要通过旋转操作来恢复平衡。

代码实现：​

#include <stdio.h>
#include <stdlib.h>

// 定义节点结构
typedef struct AVLNode {
    int key;
    struct AVLNode *left;
    struct AVLNode *right;
    int height;
} AVLNode;

// 获取节点高度
int height(AVLNode *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

// 创建新节点
AVLNode* createNode(int key) {
    AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; // 新节点高度为1
    return(node);
}

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

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

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

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

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

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

// 获取节点平衡因子
int getBalance(AVLNode *N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

// 插入节点
AVLNode* insertNode(AVLNode* node, int key) {
    if (node == NULL)
        return(createNode(key));

    if (key < node->key)
        node->left = insertNode(node->left, key);
    else if (key > node->key)
        node->right = insertNode(node->right, key);
    else // 相同的键不允许插入
        return node;

    node->height = 1 + max(height(node->left), height(node->right));

    int balance = getBalance(node);

    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

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

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

    return node;
}

3.2 删除操作​

删除节点后也可能导致树失去平衡，需要通过旋转操作来恢复平衡。

代码实现：​

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

    return current;
}

// 删除节点
AVLNode* deleteNode(AVLNode* root, int key) {
    if (root == NULL)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    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->key = temp->key;
            root->right = deleteNode(root->right, temp->key);
        }
    }

    if (root == NULL)
        return root;

    root->height = 1 + max(height(root->left), height(root->right));

    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;
}

4. 旋转操作详解​

旋转操作是为了维护AVL树的平衡性。常见的旋转操作包括右旋、左旋、左右旋和右左旋。

4.1 右旋（Right Rotation）​

右旋是对某个节点进行的顺时针旋转。用于平衡因子大于1，且新插入的节点在左子树的左子树。

y/xyright/T1⇒x/T1y/yright\begin{array}{ccc} & y & \\ / & & \\ x & & y_{\text{right}} \\ / \\ T1 \\ \end{array} \Rightarrow \begin{array}{ccc} & x & \\ / & & \\ T1 & & y \\ / \\ y_{\text{right}} \\ \end{array}
4.2 左旋（Left Rotation）​

左旋是对某个节点进行的逆时针旋转。用于平衡因子小于-1，且新插入的节点在右子树的右子树。

x/xlefty/T2⇒y/xT2/xleft\begin{array}{ccc} & x & \\ / & & \\ x_{\text{left}} & & y \\ / \\ T2 \\ \end{array} \Rightarrow \begin{array}{ccc} & y & \\ / & & \\ x & & T2 \\ / \\ x_{\text{left}} \\ \end{array}

平衡二叉树完整代码示例​

#include <stdio.h>
#include <stdlib.h>

// 定义节点结构
typedef struct AVLNode {
    int key;
    struct AVLNode *left;
    struct AVLNode *right;
    int height;
} AVLNode;

// 获取节点高度
int height(AVLNode *N) {
    if (N == NULL)
        return 0;
    return N->height;
}

// 最大值
int max(int a, int b) {
    return (a > b) ? a : b;
}

// 创建新节点
AVLNode* createNode(int key) {
    AVLNode* node = (AVLNode*)malloc(sizeof(AVLNode));
    node->key = key;
    node->left = NULL;
    node->right = NULL;
    node->height = 1; // 新节点高度为1
    return(node);
}

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

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

    y->height = max(height(y->left), height(y->right)) + 1;
    x->height = max(height(x->left), height(x->right)) + 1;

    return x;
}

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

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

    x->height = max(height(x->left), height(x->right)) + 1;
    y->height = max(height(y->left), height(y->right)) + 1;

    return y;
}

// 获取节点平衡因子
int getBalance(AVLNode *N) {
    if (N == NULL)
        return 0;
    return height(N->left) - height(N->right);
}

// 插入节点
AVLNode* insertNode(AVLNode* node, int key) {
    if (node == NULL)
        return(createNode(key));

    if (key < node->key)
        node->left = insertNode(node->left, key);
    else if (key > node->key)
        node->right = insertNode(node->right, key);
    else // 相同的键不允许插入
        return node;

    node->height = 1 + max(height(node->left), height(node->right));

    int balance = getBalance(node);

    if (balance > 1 && key < node->left->key)
        return rightRotate(node);

    if (balance < -1 && key > node->right->key)
        return leftRotate(node);

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

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

    return node;
}

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

    return current;
}

// 删除节点
AVLNode* deleteNode(AVLNode* root, int key) {
    if (root == NULL)
        return root;

    if (key < root->key)
        root->left = deleteNode(root->left, key);
    else if (key > root->key)
        root->right = deleteNode(root->right, key);
    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->key = temp->key;
            root->right = deleteNode(root->right, temp->key);
        }
    }

    if (root == NULL)
        return root;

    root->height = 1 + max(height(root->left), height(root->right));

    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;
}

// 中序遍历树
void inOrder(AVLNode *root) {
    if (root != NULL) {
        inOrder(root->left);
        printf("%d ", root->key);
        inOrder(root->right);
    }
}

// 主函数
int main() {
    AVLNode *root = NULL;

    root = insertNode(root, 9);
    root = insertNode(root, 5);
    root = insertNode(root, 10);
    root = insertNode(root, 0);
    root = insertNode(root, 6);
    root = insertNode(root, 11);
    root = insertNode(root, -1);
    root = insertNode(root, 1);
    root = insertNode(root, 2);

    printf("中序遍历 AVL 树:\n");
    inOrder(root);

    root = deleteNode(root, 10);

    printf("\n删除 10 后的中序遍历 AVL 树:\n");
    inOrder(root);

    return 0;
}

平衡二叉树（AVL树）的时间复杂度和空间复杂度分析​

时间复杂度​

  1. 插入操作

    • 查找插入位置: 由于AVL树是一种平衡二叉查找树，查找插入位置的时间复杂度为 (O(\log n))。
    • 平衡操作: 在最坏情况下，需要进行一次或两次旋转，每次旋转的时间复杂度为 (O(1))。因此，插入操作的总时间复杂度为 (O(\log n))。

  2. 删除操作

    • 查找删除节点: 与插入操作类似，查找删除节点的时间复杂度为 (O(\log n))。
    • 平衡操作: 删除节点后可能需要多次旋转来保持平衡，但每次旋转的时间复杂度为 (O(1))。因此，删除操作的总时间复杂度为 (O(\log n))。

  3. 查找操作

    • AVL树的查找操作与普通二叉查找树类似，由于树的高度为 (O(\log n))，因此查找操作的时间复杂度为 (O(\log n))。

  4. 旋转操作

    • 单次旋转操作的时间复杂度为 (O(1))，因为旋转仅涉及常数级别的节点调整。

空间复杂度​

  1. 空间复杂度
    • 每个节点需要存储其高度信息，因此每个节点的空间复杂度为 (O(1))。
    • 整棵树的空间复杂度为 (O(n))，其中 (n) 为节点数。
    • 递归操作的空间复杂度：由于递归操作的栈空间与树的高度成正比，而AVL树的高度为 (O(\log n))，所以递归操作的空间复杂度为 (O(\log n))。

综上所述，AVL树的时间复杂度和空间复杂度如下：

操作时间复杂度空间复杂度
插入(O(\log n))(O(1))
删除(O(\log n))(O(1))
查找(O(\log n))(O(1))
旋转(O(1))(O(1))
空间总计(O(n))(O(n))
递归操作(O(\log n))(O(\log n))

这些复杂度使得AVL树在需要频繁插入、删除和查找操作的应用场景中表现出色，能够有效保持平衡，从而保证操作的高效性。