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

数据结构红黑树

article 2024/9/23 3:13:31

红黑树是一种自平衡的二叉搜索树，它通过确保任何从根到叶子的路径上不会有两个连续的红节点并且从根到叶子的所有路径上有相同数量的黑节点，从而近似平衡。这种平衡保证了在最坏情况下插入、删除、查找操作都能在O(log n)时间复杂度内完成。

下面，我将逐步介绍红黑树的关键操作，包括节点的定义、插入操作以及调整（修复）操作。由于完整的源码和解析非常冗长，我将简要概述每个部分，并给出关键代码片段。

红黑树节点的定义

在实现红黑树之前，我们首先定义树中的节点，包括节点的颜色、键值、左右子节点以及父节点的引用：

class RedBlackNode<T extends Comparable<T>> {
    enum Color { RED, BLACK }

    T key;
    Color color;
    RedBlackNode<T> left;
    RedBlackNode<T> right;
    RedBlackNode<T> parent;

    public RedBlackNode(T key, Color nodeColor, RedBlackNode<T> left, RedBlackNode<T> right) {
        this.key = key;
        this.color = nodeColor;
        this.left = left;
        this.right = right;
        this.parent = null; // 父节点在插入时确定
    }
}

红黑树的插入操作

插入操作首先按照二叉搜索树的性质插入节点，之后会根据红黑树的性质进行一系列的调整。

public void insert(T key) {
    RedBlackNode<T> node = new RedBlackNode<T>(key, RedBlackNode.Color.RED, null, null);
    // 正常的BST插入操作
    if (root == null) {
        root = node;
    } else {
        insertNode(root, node);
    }
    // 插入后的调整操作
    fixAfterInsertion(node);
}

插入后的调整操作

插入节点后可能会违反红黑树的性质，因此需要进行调整。下面是调整操作的伪代码概述：

while (新节点不是根节点且新节点的父节点是红色) {
    if (父节点是祖父节点的左子节点) {
        uncle = 祖父节点的右子节点
        if (uncle是红色) {
            // Case 1: 叔叔节点也是红色
            父节点设为黑色
            叔叔节点设为黑色
            祖父节点设为红色
            新节点 = 祖父节点
        } else {
            if (新节点是父节点的右子节点) {
                // Case 2: 新节点是其父节点的右子节点
                新节点 = 父节点
                左旋转(新节点)
            }
            // Case 3: 新节点是其父节点的左子节点
            父节点设为黑色
            祖父节点设为红色
            右旋转(祖父节点)
        }
    } else {
        // 对称地处理父节点是祖父节点右子节点的情况
        ...
    }
}
根节点设为黑色

左旋转示例

左旋转是在插入节点导致树不平衡时重新平衡树的操作之一。以下是左旋转的概念性Java代码：

void leftRotate(RedBlackNode<T> x) {
    RedBlackNode<T> y = x.right;
    x.right = y.left;
    if (y.left != null) {
        y.left.parent = x;
    }
    y.parent = x.parent;
    if (x.parent == null) {
        root = y;
    } else if (x == x.parent.left) {
        x.parent.left = y;
    } else {
        x.parent.right = y;
    }
    y.left = x;
    x.parent = y;
}

右旋转示例

右旋转是左旋转的对称操作，用于重新平衡树。

void rightRotate(RedBlackNode<T> y) {
    RedBlackNode<T> x = y.left;
    y.left = x.right;
    if (x.right != null) {
        x.right.parent = y;
    }
    x.parent = y.parent;
    if (y.parent == null) {
        root = x;
    } else if (y == y.parent.right) {
        y.parent.right = x;
    } else {
        y.parent.left = x;
    }
    x.right = y;
    y.parent = x;
}