Java – 数据结构 – 红黑树

简介

红黑树是一种自平衡的二叉查找树，是计算机科学中月到的一种数据结构

1972年出现，当时被称之为平衡二买B树。后来，1978年被修改为如今的“红黑树”

它是一种特殊的二叉查找对，红黑树的每一个节点上都有存储位表示节点的颜色

每一个节点可以是红或者黑，红黑树不是高度平衡的，它的平衡是通过“红黑规则”进行实现的。

红黑树节点存储结构

包含上级父节点的内存地址

包含节点上的值

包含左子节点的内存地址和右子节点的内存地址，如果为Nil，则相当于为空

包含节点所表示的颜色（红或黑）

红黑树规则

要了解红黑树是怎么工作的，首先要先了解红黑树的规则

1.每一个节点或者是红色的，或者是黑色的。

2.根节点必须是黑色的。

3.如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点（Nil）是黑色的。

4.如果某一节点是红色的，那么它的子节点必须是黑色的（不能出现两个红色节点相连的情况）。

5.对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

规则①

每一个节点或者是红色的，或者是黑色的。

规则②

根节点必须是黑色的。

规则③

如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点（Nil）是黑色的。

规则④

如果某一节点是红色的，那么它的子节点必须是黑色的（不能出现两个红色节点相连的情况）。

规则⑤

对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点。

所有后代：是指该父节点下所有的子孙节点都是后代

叶节点：是指最下面的节点

简单路径：是指从根节点到叶节点的单向路径

红黑树添加节点

节点关系

首先我们要先了解节点与节点之间的关系

1.上一层是父节点

2.下一层是子节点

3.上上层是祖父节点

4.隔离是叔节点

添加节点时的步骤

以伪代码方式讲述

private void 红黑树来衡(Entry<K,V> 当前节点) {
        当前节点的颜色 = 红色;

        while (当前节点 != 空 && 当前节点 != 根 && 当前节点.父节点.颜色 == 红色) {
            if (父节点 == 祖父的左节点) {
                Entry<K,V> y = 祖父的右节点);
                if (祖父的右节点的颜色 == 红) {
                    setColor(父节点, 黑色);
                    setColor(祖父的右节点, 黑色);
                    setColor(祖父节点, 红色);
                    x = 祖父节点;
                } else {
                    if (当前节点 == 父节点的右节点) {
                        x = 父节点;
                        左旋(父节点);
                    }
                    setColor(parentOf(x), 黑色);
                    setColor(parentOf(parentOf(x)), 红色);
                    右旋(parentOf(parentOf(x)));
                }
            } else {
                Entry<K,V> y = 祖父节点的左节点;
                if (colorOf(y) == 红色) {
                    setColor(父节点, 黑);
                    setColor(祖父节点的左节点, 黑色);
                    setColor(祖父节点, 红色);
                    x = 祖父节点;
                } else {
                    if (x == 父节点的左节点) {
                        x = 父节点;
                        rotateRight(父节点);
                    }
                    setColor(parentOf(x), 黑色);
                    setColor(parentOf(parentOf(x)), 红色);
                    rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = 黑色;
    }