Java中的红黑树（如果想知道Java中有关红黑树的知识点，那么只看这一篇就足够了！）

红黑树是一种自平衡的二叉查找树，它能够在最坏情况下保持O(log n)的时间复杂度进行查找、插入和删除操作。在Java中，红黑树被广泛应用于集合框架中的TreeMap和TreeSet等数据结构。

红黑树的基本性质

红黑树具有以下五个性质：

1. 节点是红色或黑色。
2. 根节点是黑色。
3. 每个叶子节点（NIL或空节点）是黑色。
4. 如果一个节点是红色，则它的两个子节点都是黑色（即没有两个连续的红色节点）。
5. 从任何节点到其所有叶子节点的路径都包含相同数量的黑色节点。

这些性质确保了红黑树在最坏情况下也能保持相对平衡，从而保证O(log n)的时间复杂度。

Java中的红黑树实现

在Java中，TreeMap和TreeSet都是基于红黑树实现的。下面是一个简单的红黑树实现的示例。

class Node {
    int data;
    Node parent;
    Node left;
    Node right;
    boolean color; // true for red, false for black

    public Node(int data) {
        this.data = data;
        this.color = true; // 新节点默认为红色
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

public class RedBlackTree {
    private Node root;
    private Node TNULL;

    // Preorder
    private void preOrderHelper(Node node) {
        if (node != TNULL) {
            System.out.print(node.data + " ");
            preOrderHelper(node.left);
            preOrderHelper(node.right);
        }
    }

    // Balance the tree after deletion of a node
    private void fixDelete(Node x) {
        Node s;
        while (x != root && x.color == false) {
            if (x == x.parent.left) {
                s = x.parent.right;
                if (s.color == true) {
                    s.color = false;
                    x.parent.color = true;
                    leftRotate(x.parent);
                    s = x.parent.right;
                }
                if (s.left.color == false && s.right.color == false) {
                    s.color = true;
                    x = x.parent;
                } else {
                    if (s.right.color == false) {
                        s.left.color = false;
                        s.color = true;
                        rightRotate(s);
                        s = x.parent.right;
                    }
                    s.color = x.parent.color;
                    x.parent.color = false;
                    s.right.color = false;
                    leftRotate(x.parent);
                    x = root;
                }
            } else {
                s = x.parent.left;
                if (s.color == true) {
                    s.color = false;
                    x.parent.color = true;
                    rightRotate(x.parent);
                    s = x.parent.left;
                }
                if (s.right.color == false && s.left.color == false) {
                    s.color = true;
                    x = x.parent;
                } else {
                    if (s.left.color == false) {
                        s.right.color = false;
                        s.color = true;
                        leftRotate(s);
                        s = x.parent.left;
                    }
                    s.color = x.parent.color;
                    x.parent.color = false;
                    s.left.color = false;
                    rightRotate(x.parent);
                    x = root;
                }
            }
        }
        x.color = false;
    }

    private void printHelper(Node root, String indent, boolean last) {
        if (root != TNULL) {
            System.out.print(indent);
            if (last) {
                System.out.print("R----");
                indent += "   ";
            } else {
                System.out.print("L----");
                indent += "|  ";
            }

            String sColor = root.color ? "RED" : "BLACK";
            System.out.println(root.data + "(" + sColor + ")");
            printHelper(root.left, indent, false);
            printHelper(root.right, indent, true);
        }
    }

    // 左旋
    private void leftRotate(Node x) {
        Node y = x.right;
        x.right = y.left;
        if (y.left != TNULL) {
            y.left.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.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 x) {
        Node y = x.left;
        x.left = y.right;
        if (y.right != TNULL) {
            y.right.parent = x;
        }
        y.parent = x.parent;
        if (x.parent == null) {
            this.root = y;
        } else if (x == x.parent.right) {
            x.parent.right = y;
        } else {
            x.parent.left = y;
        }
        y.right = x;
        x.parent = y;
    }

    public RedBlackTree() {
        TNULL = new Node(0);
        TNULL.color = false;
        root = TNULL;
    }

    public void preorder() {
        preOrderHelper(this.root);
    }

    public void printTree() {
        printHelper(this.root, "", true);
    }

    public static void main(String[] args) {
        RedBlackTree bst = new RedBlackTree();
        // 插入节点
        bst.insert(new Node(55));
        bst.insert(new Node(40));
        bst.insert(new Node(20));
        bst.insert(new Node(10));

        // 打印树
        bst.printTree();
    }
}

总结

红黑树的优势在于它能够保持数据的有序性和适度的平衡，使得查找、插入和删除操作在O(log n)的时间复杂度内完成。虽然实现比较复杂，但它的自平衡性质使得其在实际应用中非常重要，例如在Java的TreeMap和TreeSet中。理解红黑树的性质和操作是掌握数据结构和算法的重要一步。