Java数据结构之红黑树的原理及实现

1. 红黑树的概述

红黑树是一种自平衡二叉查找树。在二叉查找树中，左节点的值比父节点的值小，右节点的值比父节点的值大，而红黑树中还有两个特殊的规则：

• 每个节点不是红色就是黑色
• 根节点是黑色的

这两个规则确保了红黑树的平衡性和搜索性能。

红黑树是通过颜色标记来区分每个节点，一般使用红色来表示，所以得名为红黑树。

2. 插入操作实现

当我们向红黑树中插入一个节点时，首先将其作为一个叶子节点插入到树中。

之后，我们需要按照以下规则进行调整：

1. 推断出插入节点的叔叔节点，即它的父节点的兄弟节点。

2. 当插入节点的父节点是根节点，或者插入节点的父节点是黑色的时，红黑树依然满足平衡条件，插入操作结束。

3. 当插入节点的父节点是红色的时候，我们需要调整红黑树的颜色和结构，使之重新满足平衡条件。

4. 当插入节点的叔叔节点也是红色的时候，我们需要将插入节点的父节点和叔叔节点都变为黑色，祖父节点变为红色，然后将祖父节点当成新的插入节点，继续调整。

5. 当插入节点的叔叔节点是黑色的时候，我们需要进行旋转操作。这里分为两种情况：

   • 第一种情况是插入节点在其父节点的左子树中，而该父节点是祖父节点的左子树中。
   • 第二种情况是插入节点在其父节点的右子树中，而该父节点是祖父节点的右子树。

6. 重复以上步骤，直到红黑树重新满足平衡条件。

下面是示例代码：

public void insert(T data) {
    Node<T> node = new Node<>(data, BLACK);
    Node<T> x = this.root;
    Node<T> y = null;
    while (x != null) {
        y = x;
        if (data.compareTo(x.data) < 0) {
            x = x.left;
        } else {
            x = x.right;
        }
    }

    node.parent = y;
    if (y == null) {
        root = node;
    } else if (data.compareTo(y.data) < 0) {
        y.left = node;
    } else {
        y.right = node;
    }

    if (node.parent == null) {
        node.color = BLACK;
        return;
    }

    if (node.parent.parent == null) {
        return;
    }

    fixInsert(node);
}

3. 删除操作实现

当我们从红黑树中删除一个节点时，也需要按照一定的规则来进行调整。

1. 如果删除节点只有一个或者没有子节点，直接将删除节点替换为它的子节点即可。

2. 如果删除的节点有两个子节点，则需要找到其后继节点（即节点值大于此节点的最小节点），并将后继节点删除。最后，将后继节点的数据替换到删除节点中。

3. 如果删除节点是黑色的，则需要进行调整操作。该操作也分为两种情况：

4. 如果删除节点是根节点，那么直接删除即可。

5. 如果删除节点不是根节点，则需要进行旋转和重新染色操作，以使红黑树恢复平衡。

6. 重复以上步骤，直到红黑树重新满足平衡条件。

下面是示例代码：

public boolean delete(T data) {
    Node<T> node = search(data);
    if (node == null) {
        return false;
    }

    if (node.left != null && node.right != null) {
        Node<T> next = successor(node);
        node.data = next.data;
        node = next;
    }

    Node<T> child = null;
    if (node.left != null) {
        child = node.left;
    } else {
        child = node.right;
    }

    if (child != null) {
        child.parent = node.parent;
    }

    if (node.parent == null) {
        root = child;
    } else if (node == node.parent.left) {
        node.parent.left = child;
    } else {
        node.parent.right = child;
    }

    if (node.color == BLACK) {
        fixDelete(child, node.parent);
    }

    return true;
}

4. 示例说明

4.1 示例1：插入操作

假设我们需要向一棵空红黑树中插入以下节点：

3->2->1

这个过程可以如下图所示：

4.2 示例2：删除操作

假设我们需要将以下节点从红黑树中删除：

6->3->7

这个过程可以如下图所示：