资讯

历史

科技

环境与自然

成长

游戏

财经

文学与艺术

美食

健康

家居

文化

情感

汽车

三农

军事

旅行

运动

教育

生活

星座命理

红黑树（Red/Black Tree）：平衡与效率的完美结合

创作时间:

作者:

@小白创作中心

红黑树（Red/Black Tree）：平衡与效率的完美结合

引用

CSDN

https://blog.csdn.net/m0_58067066/article/details/144097597

红黑树（Red-Black Tree）是一种自平衡的二叉搜索树，它在保证基本操作（如插入、删除、查找）的效率的同时，还保持了树的平衡性。让我们通过一个小故事和一个小例子来理解红黑树的概念和工作原理：

故事背景

在树的世界里，有一个名为“红黑树”的王国。红黑树王国由一个国王（根节点）和许多臣民（节点）组成。每个臣民都有两个孩子（左孩子和右孩子），并且每个臣民的颜色要么是红色，要么是黑色。国王和他的臣民们遵循着一套严格的规则来维持王国的平衡和秩序。

红黑树的规则

红黑树必须遵循以下五条基本规则：

每个节点要么是红色，要么是黑色。

这就像每个臣民都有一个唯一的身份标记，红色的臣民代表新加入的成员，黑色的臣民代表长期服务的成员。

根节点必须是黑色的。

国王作为王国的最高统治者，总是黑色，象征着稳定和权威。

每个叶子节点（NIL节点）是黑色的。

在红黑树中，叶子节点实际上是空节点（NIL），它们总是黑色，代表着树的终点。

如果一个节点是红色，那么它的两个孩子必须是黑色的。

这是为了防止连续的红色节点出现，保持树的平衡性。红色节点不能相邻，以免树变得过于不平衡。

对于每个节点，从该节点到其所有后代叶子节点的简单路径上，黑色节点的数量必须相同。

这确保了树的高度不会过度增长，保证了操作的效率。

小例子

假设有一个红黑树如下：

插入规则分析

第一步：将节点插入到二叉搜索树中

按照二叉搜索树的规则：

比较 12 和根节点 10：12 > 10，向右子树移动。
比较 12 和节点 15：12 < 15，向左子树移动。
比较 12 和节点 13：12 < 13，成为节点 13 的左子节点。

此时插入后的树结构如下：

新插入的节点 12 初始为红色。

第二步：调整以维护红黑树性质

现在我们逐步检查红黑树规则，并修复可能的违规：

1.检查红黑树规则 4：红色节点不能有红色子节点。

新节点 12 是红色，其父节点 13 也是红色。
违反了规则 4。

2.处理冲突（父节点为红色）：

Case 1：叔节点也是红色（节点 18 为红色）。
解决方法：重新着色。
父节点 13 和叔节点 18 改为黑色。
祖父节点 15 改为红色。

3.检查祖父节点是否冲突：

祖父节点 15 为红色，其父节点 10 为黑色。
没有进一步冲突，调整完成。

Java实现示例

下面是一个简化的红黑树插入操作的Java实现示例，基于上述小例子：

public class RedBlackTree {
    private static final boolean RED = true;
    private static final boolean BLACK = false;
    private class Node {
        int key;
        boolean color;
        Node left, right, parent;
        Node(int key) {
            this.key = key;
            this.color = RED;
        }
    }
    private Node root;
    public void insert(int key) {
        Node node = new Node(key);
        if (root == null) {
            root = node;
            root.color = BLACK;
            return;
        }
        Node y = null;
        Node x = root;
        while (x != null) {
            y = x;
            if (node.key < x.key) {
                x = x.left;
            } else {
                x = x.right;
            }
        }
        node.parent = y;
        if (node.key < y.key) {
            y.left = node;
        } else {
            y.right = node;
        }
        insertFixup(node);
    }
    private void insertFixup(Node node) {
        while (node != root && node.parent.color == RED) {
            if (node.parent == node.parent.parent.left) {
                Node uncle = node.parent.parent.right;
                if (uncle != null && uncle.color == RED) {
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.right) {
                        node = node.parent;
                        leftRotate(node);
                    }
                    node.parent.color = BLACK;
                    node.parent.parent.color = RED;
                    rightRotate(node.parent.parent);
                }
            } else {
                Node uncle = node.parent.parent.left;
                if (uncle != null && uncle.color == RED) {
                    node.parent.color = BLACK;
                    uncle.color = BLACK;
                    node.parent.parent.color = RED;
                    node = node.parent.parent;
                } else {
                    if (node == node.parent.left) {
                        node = node.parent;
                        rightRotate(node);
                    }
                    node.parent.color = BLACK;
                    node.parent.parent.color = RED;
                    leftRotate(node.parent.parent);
                }
            }
        }
        root.color = BLACK;
    }
    private void leftRotate(Node x) {
        Node 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;
    }
    private void rightRotate(Node y) {
        Node 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;
    }
    private boolean validateRedBlackTree(Node node) {
        if (node == null) {
            return true;
        }
        if (node.color == RED) {
            if ((node.left != null && node.left.color == RED) ||
                    (node.right != null && node.right.color == RED)) {
                System.out.println("Red violation at node: " + node.key);
                return false;
            }
        }
        return validateRedBlackTree(node.left) && validateRedBlackTree(node.right);
    }
    public boolean validateTree() {
        return validateRedBlackTree(root);
    }
    private void inOrderTraversal(Node node) {
        if (node != null) {
            inOrderTraversal(node.left);
            System.out.println("Key: " + node.key + ", Color: " + (node.color == RED ? "RED" : "BLACK"));
            inOrderTraversal(node.right);
        }
    }
    public void printTree() {
        inOrderTraversal(root);
    }
    public static void main(String[] args) {
        RedBlackTree tree = new RedBlackTree();
        int[] keys = {10, 5, 15, 3, 7, 13, 18, 12};
        for (int key : keys) {
            tree.insert(key);
        }
        tree.printTree();
        System.out.println("红黑树验证结果: " + tree.validateTree());
    }
}

这个实现展示了红黑树的插入操作和随后的平衡调整过程。通过颜色变换和旋转操作，红黑树保持了平衡性，确保了基本操作的效率。