红黑树以及JAVA实现( 三 ) _红黑树

首先我们要明白的是，在红黑树中，只有黑色节点才计入高度，红色节点代表着其和父节点的链接是红色的。
非2节点由黑色节点+红色节点组合的形式表示，红黑树对应到2-3-4树的节点组合中只会存在一个黑色节点。
2.2.1 2节点转换

文章插图

2.2.2 3节点转换3节点转换成红黑树就是一个黑色节点带着红色子节点的树，这个树可以是左倾的也可以是右倾的，根据节点的key来决定，在以2-3树为基础实现的红黑树中，我们一般只允许左倾或则右倾树存在，如果出现不允许的倾斜树情况，一般会通过旋转变色来调整。

文章插图

2.2.3 4节点转换

文章插图

2.2.4 例子

文章插图

2.3 红黑树定义解释先在我们再来来挨个看这5条定义

第一条这个没什么好说的，红黑树红黑树，那肯定节点不是红色就是黑色
由于根节点必然是没有父节点的，而在上面我们所列举的转换形式中并没有红色节点为父节点的结构，所以根节点必然是黑色的
在红黑树中叶子节点会默认拥有两个为null的子节点，颜色自然是黑色
不允许又连续两个红色节点是为了限制红黑树的阶数为4，不允许出现2、3、4节点之外的节点类型
对应2-3-4树的第五条，保证了树的绝对平衡，对应到红黑树中只有黑色节点代表高度，所以只需要保证黑色节点的数目一致即可。

2.3.1 红黑树的旋转与变色我们在对红黑树进行添加的时候，一开始按照二叉树的方式添加，每个新节点的初始元素为红色（root节点为黑色），当我们继续进行添加，发现当前的红黑树结构不符合定义时，我们就需要通过旋转和对节点变色来重新平衡红黑树。
2.3.2 红黑树的旋转先说旋转，红黑树的旋转分为左旋和右旋，我们先通过左旋来进行详细讲解。左旋就是一个节点绕着他的右子节点逆时针旋转，变成右子节点的左子节点，我们以下图为例

文章插图

A进行左旋，变成B的左子节点，于此同时，B原先的左子树变成A的右子树，A的父节点变为B的父节点。
A的左子树依旧是A的左子树，B的右子树也依旧是B的右子树，不做变化。
这样，我们就完成了一次左旋，右旋则是绕则操作节点自身的子节点顺时针旋转，变成左子节点的右子树，左子节点的右子树迁移到操作节点的左子树，操作节点的父节点变成左子节点的父节点。原理一模一样。
2.3.3 红黑树的变色当然，我们在旋转以后，如果不变色，结果肯定是不正确的，只有进行变色之后的红黑树才是正确的，由于变色有很多种情况，所以我们这里只举一个简单的例子，后面在讲解添加和删除的时候再进行细致列举。