当前位置：首页 > article >正文

数据结构第一弹-平衡树

article 2025/1/11 20:50:58

大家好，今天和大家一起分享一下数据结构中的平衡树~

平衡树是一种特别重要的数据结构，它通过维持树的高度来保证操作的效率，从而在众多数据结构中脱颖而出。我们今天深入探讨平衡树的概念、种类、工作原理以及应用实例。

1. 平衡树简介

平衡树是一种自我调整的数据结构，旨在保持左右子树的高度差不超过一个特定值，以确保插入、删除等操作后树仍能保持较佳的时间复杂度。这种特性使得平衡树成为实现动态集合（如数据库索引）的理想选择。根据维护平衡的方式不同，平衡树可以分为多种类型，其中最著名的包括AVL树、红黑树等。

1.1 AVL树

AVL树得名于其发明者Adelson-Velsky和Landis。它是最早被发明的自平衡二叉搜索树。在AVL树中，任何节点的两个子树的高度最多相差1。每当插入或删除元素导致树失去平衡时，都会执行一系列旋转操作来恢复平衡状态。这些旋转包括单旋（左旋、右旋）和双旋（先左后右旋、先右后左旋）。尽管AVL树提供了O(log n)级别的查找、插入和删除时间复杂度，但频繁地进行旋转操作可能会影响性能。

1.2 红黑树

红黑树是一种近似平衡的二叉搜索树，它通过给每个节点添加颜色属性（红色或黑色）并遵循某些规则来保证“大致”平衡的状态。主要规则包括：

每个节点要么是红色，要么是黑色。
根节点总是黑色。
所有叶子节点都是黑色（这里的叶子指的是空指针NIL）。
如果一个节点是红色，则它的两个子节点必须为黑色。
从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

与AVL树相比，红黑树牺牲了一定程度的严格平衡性，换来的是更简单的维护成本及更高的实际运行效率。红黑树也支持O(log n)的操作时间复杂度，并且由于其相对较少的重平衡操作，在许多情况下比AVL树表现更好。

2. 工作原理

无论是AVL树还是红黑树，它们的核心思想都是通过限制树的高度来保证高效的查询速度。当新元素加入或旧元素移除时，两种类型的平衡树都会自动调整自身结构，以确保满足各自的平衡条件。这一过程通常涉及节点颜色的变化（对于红黑树而言）、节点间的重新链接（旋转操作），以及必要时的颜色修正。

2.1 插入操作

在向平衡树中插入新元素的过程中，首先按照二叉搜索树的标准流程找到合适的位置放置新节点；然后，根据所选平衡树的具体类型（AVL或红黑树），检查是否需要进行平衡调整。如果发现不平衡情况，则通过适当的旋转及颜色更改来恢复平衡状态。

2.2 删除操作

删除操作同样遵循二叉搜索树的基本原则，即找到待删节点后用其前驱或后继替换之。之后，根据当前树种的不同，可能需要进一步处理以保证整个结构仍然符合平衡要求。例如，在AVL树中，删除可能导致某部分子树高度下降过多，此时就需要通过旋转等方式来重新平衡整棵树。

3 AVL树的实现

3.1 节点定义

class TreeNode {
    int key, height;
    TreeNode left, right;

    public TreeNode(int d) {
        key = d;
        height = 1; // 新节点的高度初始化为1
    }
}

3.2 获取高度

int getHeight(TreeNode N) {
    if (N == null)
        return 0;
    return N.height;
}

3.3 更新高度

void updateHeight(TreeNode N) {
    if (N != null) {
        N.height = Math.max(getHeight(N.left), getHeight(N.right)) + 1;
    }
}

3.4 计算平衡因子

int getBalanceFactor(TreeNode N) {
    if (N == null)
        return 0;
    return getHeight(N.left) - getHeight(N.right);
}

3.5 右旋操作

TreeNode rightRotate(TreeNode y) {
    TreeNode x = y.left;
    TreeNode T2 = x.right;

    // 执行旋转
    x.right = y;
    y.left = T2;

    // 更新高度
    updateHeight(y);
    updateHeight(x);

    return x;
}

3.6 左旋操作

TreeNode leftRotate(TreeNode x) {
    TreeNode y = x.right;
    TreeNode T2 = y.left;

    // 执行旋转
    y.left = x;
    x.right = T2;

    // 更新高度
    updateHeight(x);
    updateHeight(y);

    return y;
}

3.7 插入操作

TreeNode insert(TreeNode node, int key) {
    // 正常的BST插入
    if (node == null) {
        return new TreeNode(key);
    }

    if (key < node.key) {
        node.left = insert(node.left, key);
    } else if (key > node.key) {
        node.right = insert(node.right, key);
    } else { // 相等的情况，不重复插入
        return node;
    }

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

    // 获取平衡因子
    int balance = getBalanceFactor(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;
}

4 红黑树的实现（简化版）

对于红黑树，我们同样采用一个简化的实现方式，只关注基本的颜色属性和插入逻辑。

4.1 节点定义

enum Color { RED, BLACK };

class RBTreeNode {
    int key;
    Color color;
    RBTreeNode left, right, parent;

    public RBTreeNode(int k, Color c) {
        key = k;
        color = c;
        left = right = parent = null;
    }
}

4.2 左旋操作

void leftRotate(RBTreeNode node) {

    RBTreeNode rightChild = node.right;
    node.right = rightChild.left;
    if (rightChild.left != null) {
        rightChild.left.parent = node;
    }
    rightChild.parent = node.parent;
    if (node.parent == null) {
        root = rightChild; // 假设root是全局变量
    } else if (node == node.parent.left) {
        node.parent.left = rightChild;
    } else {
        node.parent.right = rightChild;
    }
    rightChild.left = node;
    node.parent = rightChild;
}

4.3 右旋操作

void rightRotate(RBTreeNode node) {
    RBTreeNode leftChild = node.left;
    node.left = leftChild.right;
    if (leftChild.right != null) {
        leftChild.right.parent = node;
    }
    leftChild.parent = node.parent;
    if (node.parent == null) {
        root = leftChild; // 假设root是全局变量
    } else if (node == node.parent.right) {
        node.parent.right = leftChild;
    } else {
        node.parent.left = leftChild;
    }
    leftChild.right = node;
    node.parent = leftChild;
}

4.4 插入修复

这部分代码较为复杂，涉及多个条件判断以及旋转操作。为了简洁起见，在这里不完全展开。以下伪代码：