Java 数据结构篇-实现红黑树的核心方法

红黑树是一种自平衡的二叉搜索树，其主要目的是保持树的平衡性，确保在最坏情况下基本操作（插入、删除和查找）的时间复杂度为O(log n)。红黑树的特点主要包括以下几条规则：

1. 节点是红色或黑色。
2. 根节点始终是黑色。
3. 每个叶子节点（Nil节点）都是黑色。
4. 如果一个节点是红色，则它的两个子节点都必须是黑色（即不允许出现双红）。
5. 从任一节点到其每个叶子节点的所有路径都包含相同数量的黑色节点。

接下来，我们将实现红黑树的插入操作，关注其核心处理逻辑，包括调整红黑树的结构和颜色。

红黑树节点类

首先，我们需要定义红黑树的节点类：

class Node {
    int data;
    Node parent;
    Node left;
    Node right;
    int color; // 0为黑色，1为红色

    public Node(int data) {
        this.data = data;
        this.color = 1; // 新插入的节点初始化为红色
        this.left = null;
        this.right = null;
        this.parent = null;
    }
}

红黑树类

接下来，我们定义红黑树类，同时包含插入和调整的方法：

class RedBlackTree {
    private Node root;
    private Node TNULL;

    // 中序遍历树
    private void inOrderHelper(Node node) {
        if (node != TNULL) {
            inOrderHelper(node.left);
            System.out.print(node.data + " ");
            inOrderHelper(node.right);
        }
    }

    // 插入新节点
    public void insert(int key) {
        Node node = new Node(key);
        node.parent = null;

        // 寻找适当位置插入
        Node y = null;
        Node x = this.root;

        while (x != TNULL) {
            y = x;
            if (node.data < x.data) {
                x = x.left;
            } else {
                x = x.right;
            }
        }

        node.parent = y;
        if (y == null) {
            root = node; // 树为空，插入为根节点
        } else if (node.data < y.data) {
            y.left = node;
        } else {
            y.right = node;
        }

        node.left = TNULL;
        node.right = TNULL;
        node.color = 1; // 新节点是红色

        fixInsert(node); // 修正红黑树的性质
    }

    // 修正树的性质
    private void fixInsert(Node k) {
        Node u;
        while (k.parent != null && k.parent.color == 1) {
            if (k.parent == k.parent.parent.left) {
                u = k.parent.parent.right; // 叔叔节点
                if (u.color == 1) {
                    // 叔叔节点是红色
                    k.parent.color = 0; // 父节点变成黑色
                    u.color = 0; // 叔叔节点变成黑色
                    k.parent.parent.color = 1; // 祖父节点变成红色
                    k = k.parent.parent; // 向上调整
                } else {
                    if (k == k.parent.right) {
                        k = k.parent; // 左旋
                        leftRotate(k);
                    }
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    rightRotate(k.parent.parent);
                }
            } else {
                u = k.parent.parent.left;
                if (u.color == 1) {
                    k.parent.color = 0;
                    u.color = 0;
                    k.parent.parent.color = 1;
                    k = k.parent.parent;
                } else {
                    if (k == k.parent.left) {
                        k = k.parent;
                        rightRotate(k);
                    }
                    k.parent.color = 0;
                    k.parent.parent.color = 1;
                    leftRotate(k.parent.parent);
                }
            }
        }
        root.color = 0; // 根节点永远是黑色
    }

    // 左旋操作
    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 void inOrder() {
        inOrderHelper(this.root);
    }

    // 构造函数
    public RedBlackTree() {
        TNULL = new Node(0);
        TNULL.color = 0;
        root = TNULL;
    }
}

示例

现在，我们可以使用这个红黑树类进行插入操作并输出树的中序遍历结果：

public class Main {
    public static void main(String[] args) {
        RedBlackTree rbt = new RedBlackTree();

        rbt.insert(55);
        rbt.insert(40);
        rbt.insert(65);
        rbt.insert(20);
        rbt.insert(50);
        rbt.insert(60);
        rbt.insert(70);

        rbt.inOrder(); // 打印树的中序遍历
    }
}

总结

本文介绍了红黑树的基本概念以及插入操作的实现。通过适当的旋转和颜色调整，红黑树能够保持自平衡，确保操作的高效性。这一数据结构在许多实际应用中都有重要意义，例如在Java的TreeMap和TreeSet中就使用了红黑树。理解和实现红黑树是掌握数据结构和算法的重要一步。