树2：红黑树
树的平衡性
平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。
平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。
所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。
常见的平衡二叉查找树有：AVL树、Splay Tree（伸展树）、Treap（树堆）和红黑树等等。使用最广泛的是红黑树，从linux内核到jdk的HashMap等等都被广泛使用到。
红黑树
红黑树是一种自平衡的二叉搜索树，通过特定的规则确保树的高度始终保持在 O(logn)，从而保证各项操作的高效性。
红黑树的英文是“Red-Black Tree”，简称 R-B Tree。它是一种不严格的平衡二叉查找树（近似平衡的二叉查找树）。顾名思义，红黑树中的节点，一类被标记为黑色，一类被标记为红色。除此之外，一棵红黑树还需要满足这样几个要求：
- 根节点是黑色的；
- 每个叶子节点都是黑色的空节点（NIL），也就是说，叶子节点不存储数据；
- 任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的；
- 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点；
其中第二点通常会被隐含忽略，也就是说我们不用显式标识出来。
作为一种非线性数据结构，保证上面的四点性质的二叉搜索树就可以保证树的平衡性。可以这么说，上面四点性质就是对平衡性的通俗实践总结，和"奇变偶不变，符号看象限一样"一样。
平衡二叉查找树的初衷，是为了解决二叉查找树因为动态更新导致的性能退化问题。所以，“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化得太严重。
二叉查找树很多操作的性能都跟树的高度成正比。一棵极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是 logn，所以如果要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近 logn 就好了。
首先我们将红色节点忽略，删除红色节点之后，剩下的黑色节点，由于有第四点性质的约束（每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点），在忽略了红色节点的情况下，剩下的节点组成的树是没有高度差的，其高度低于logn。
那么在不忽略红色节点情况下，又由于第三点性质的约束（任何相邻的节点都不能同时为红色，也就是说，红色节点是被黑色节点隔开的），红色节点不能相邻，也就是说，有一个红色节点就要至少有一个黑色节点，将它跟其他红色节点隔开。红黑树中包含最多黑色节点的路径不会超过 logn，所以加入红色节点之后，最长路径不会超过 2logn，也就是说，红黑树的高度近似 2logn。
所以，红黑树的高度只比高度平衡的 AVL 树的高度（log2n）仅仅大了一倍，在性能上，下降得并不多。这样推导出来的结果不够精确，实际上红黑树的性能更好。
红黑树的四点性质约束确保树高 h≤2log(n+1)，即 h=O(logn)。
实现
红黑树实现的关键是在插入和删除节点的时候通过旋转和改变颜色操作保证树的性质不变。对于插入和删除，都可以通过分类讨论来处理。
旋转
旋转分为左旋和右旋
左旋
XY节点的左旋操作如下，ABC表示子树
[X] [Y]
/ \ / \
[A] [Y] ————> [X][C]
/ \ / \
[B][C] [A][B]右旋
XY节点的右旋操作如下，ABC表示子树
[X] [Y]
/ \ / \
[Y] [C] ————> [A][X]
/ \ / \
[A][B] [B][C]插入
红黑树规定，插入的节点必须是红色的。而且，二叉查找树中新插入的节点都是放在叶子节点上。
插入操作可以分为以下几种情况：
- 如果插入节点的父节点是黑色的，那我们什么都不用做，它仍然满足红黑树的定义。
- 如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。
- 其他情况，都是需要通过旋转和改变颜色来达到平衡的。
需要操作又只有以下三种情况（以叔节点在左分支为例，左分支与右分支的旋转操作时对称的）：
假设节点node是新插入的节点，也是最初的关注节点。由于每条路径的黑色节点都需要相同，所以我们要格外关注当前节点的叔节点（父节点的兄弟节点）。
本质是在连续两个红色的节点的情况下进行旋转与改色操作使之符合红黑树定义。
CASE 1：如果关注节点是 node，它的叔叔节点 uncle 是红色
这种情况下，原本的树就是一颗符合定义的二叉树，父节点和叔节点挂在一个黑节点下面，此时由于插入了新的红节点导致连续红节点的出现，我们将父节点和树节点进行染黑色消除当前不连续红的情况，将祖父节点染红以平衡左右黑高度。然后需要对祖父节点进行连续红节点的检查。
- 将关注节点 node 的父节点 p、叔叔节点 uncle 的颜色都设置成黑色；
- 将关注节点 node 的祖父节点 gp 的颜色设置成红色；
- 关注节点变成 node 的祖父节点 gp；
- 跳到 CASE 2 或者 CASE 3。
[gp]
/ \
[uncle(红)] [p(红)]
\
[node]变成
[gp（红，新node）]
/ \
[uncle(黑)] [p(黑)]
\
[node（旧node）]CASE 2：如果关注节点是 node，它的叔叔节点 uncle 是黑色，关注节点 node 是其父节点 p 的左子节点
这种情况只可能发生在插入中间态，由于父节点与叔节点不同色，如果当前节点是新插入的，那么也就意味着原本的树就是不符合红黑树定义的。此时我们旋转使得当前节点与父节点的位置与祖父节点的位置是一致的，保证后续旋转时相对位置关系一致。
- 关注节点变成节点 node 的父节点 p；
- 围绕新的关注节点p 右旋；
- 跳到 CASE 3。
[gp]
/ \
[uncle(黑)] [p(红)]
/
[node]变成
[gp]
/ \
[uncle(黑)] [node (旧node)]
\
[p（新node）]CASE 3：如果关注节点是 node，它的叔叔节点 uncle 是黑色，关注节点 node 是其父节点 p 的右子节点
（此时的当前节点和父节点必然是红色的，可以先调整颜色再旋转，将当前节点父节点变成黑色，在将祖父节点变成红色；以祖父节点旋转后祖父节点变成兄弟节点，父节点还是父节点）
这种情况也必然是中间态，从上面步骤过来的，原因和case 2是一样的。为了消除连续红节点，先旋转再染色，
- 围绕关注节点 node 的祖父节点 gp 左旋；
- 将关注节点 node 的父节点 p、兄弟节点 uncle 的颜色互换。
- 调整结束。
[gp]
/ \
[uncle(黑)] [p]
\
[node]先旋转
[p]
/ \
[gp] [node]
/
[uncle(黑)] 再变色
[p（设置成gp的颜色）]
/ \
[gp(设置成p的颜色)] [node]
/
[uncle(黑)] 值得注意的是，终止条件是关注节点与父节点不同为红节点。最终关注节点会一步步到root节点，root节点没有父节点也是终止的。root作为关注节点的时候说明root节点是红色，该树黑高度需要+1，也就是将root重新染黑。
删除
删除节点分为以下几种情况：
- 要删除的节点没有子节点
- 要删除的节点只有一个子节点
- 要删除的节点有两个子节点
对于第三种情况，我们可以将其转换成第一种和第二种情况，具体操作如下：
假设A是要删除的节点，他有两个分支b,c，那么我们要找到右分支c的最小元素C或者左分支b的最大元素B，通常我们选择在右分支寻找最小元素，这里以这种方式为例。
[A]
/ \
[b][c]获取到右分支最小元素C之后，将此元素内容交换到待删除元素A中。那么A就相当于删除了，此时需要将C元素删除，这样我们就把删除元素A转换成了删除右分支c的最小元素C的操作。
而删除C只能有第一第二两种情况。
删除的节点只有两种情况：
- 删除的是一个红节点
- 删除的是一个黑节点
由于删除之前，是符合定义的红黑树。那么在删除红节点的时候并不会影响平衡：
删除的红节点没有子节点，那么相当于将红节点替换成了nil也就是默认的黑节点，原本的性质并没有被破坏（不能有两个红节点相连和不能黑高度相等），其实可以确定any子树要么是一个红节点要么是一个nil。
[黑]
/ \
[any][红]
/\
[nil][nil]删除的红节点有一个子节点，那么相当于将红节点的黑色子节点上升了一层，由于原本是符合定义的红黑树，由于红节点的父子节点必然是黑节点，那么待删除红节点的黑子树必然比nil子节点多至少一个黑高度，所以，不存在红节点只有一个子树的情况。
[黑] 或者： [黑]
/ \ / \
[any][红] [any][红]
/\ /\
[黑][nil] [nil][黑]也就是说删除红节点是不需要调整的。
那么我们需要调整的情况就集中在删除黑节点的情况下：
首先是待删除黑节点有一颗子树的情况下，其子树必然是一个红节点，此时只需要将该红节点替换到待删除黑节点的位置即可，由于黑节点被删除，黑高度降低，那么此时我们就需要做出调整，将刚刚的红节点染色成黑节点
[p-any] 或者：[p-any]
/ \ / \
[any][黑] [any][黑]
/\ /\
[红][nil] [nil][红]其次是待删除的黑节点没有子树的情况下，相当于直接失去的一个黑高度，此时要对兄弟子树any进行分类讨论：
[p-any]
/ \
[any][黑]
/\
[nil][nil]我们的分类讨论集中在删除了一个无子节点的黑色节点上面
我们最初的关注节点就是这个删除的黑色节点，原本是黑色的关注节点称为称为双黑节点，原本是红色的关注节点称为红黑节点。红黑节点只会产生在删除处理的过程中。遇到红黑节点只需要将其染黑就可以完成删除操作了。所以复杂操作集中在关注节点是双黑节点的情况下：
CASE 1：关注节点 node 的兄弟节点 bro 是红节点的情况
- 将兄弟 bro 染黑
- 将父节点 p 染红
- 围绕p节点朝着关注节点 node 旋转
- 关注节点不变，继续处理
[p]
/ \
[bro(红)][node]变成
[bro(染黑)]
/ \
[any] [p(染红)]
\
[node]
CASE 2：关注节点 node 的兄弟节点 bro 是黑节点，且其子节点全部为黑节点。或者bro为nil节点
- 将兄弟bro节点染红
- 关注节点变为父节点p，继续处理（如果p是红色，那么就是处理红黑节点）
[p]
/ \
[bro(黑)][node]变成
[p（新关注节点）]
/ \
[bro(红)][node（旧关注节点）]CASE 3：关注节点 node 的兄弟节点 bro 是黑节点，且bro同侧子节点son为红节点
- 将son设置为其父节点bro同色（必然是红染黑）
- 将bro设置为p同色
- 将p设置为黑色
- 围绕p节点朝着双黑节点旋转，完成处理
[p]
/ \
[bro(黑)][node]
/ \
[son(红)][any]变成
[bro(与原来的p同色)]
/ \
[son(黑)] [p（黑）]
/
[any]CASE 4：关注节点 node 的兄弟节点 bro 是黑节点，且bro同侧子节点son不为红节点
- 将bro的不同侧子节点any设置为bro父节点p同色
- 将p设置为黑色
- 朝着双黑节点反方向旋转，目的是将any节点提上来
- 围绕p节点朝着关注节点方向旋转，完成处理。
[p]
/ \
[bro(黑)][node]
\
[any]先染色，旋转
[p（染黑）]
/ \
[any(p同色)][node]
/
[bro（黑）]再旋转
[any（原p同色）]
/ \
[bro（黑）][p(黑)]和插入不同，插入是会违反不能有两个连续红节点的规则。而删除会违反所有路径的黑节点相等的原则。我们只需要关注删除一个没有子节点的黑节点的情况，当关注节点是一个非root黑节点的情况下才需要经过复杂的分类讨论，否则只需将关注节点染黑就行（关注节点是，root节点或者红黑节点）。
代码
package cn.lishiyuan.algorithm.tree;
import java.util.Objects;
public class RedBlackTree<T extends Comparable<T>> implements LeeTree<T>{
private int size;
private Node<T> root;
private static final boolean RED = true;
private static final boolean BLACK = false;
public static class Node<T>{
private T data;
boolean color = RED;
private Node<T> parent;
private Node<T> left;
private Node<T> right;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
root = null;
size = 0;
}
@Override
public boolean contains(T element) {
if(element == null){
return false;
}
Node<T> node = findNode(element);
return Objects.nonNull(node);
}
protected Node<T> findNode(T data){
if(isEmpty()){
return null;
}
Node<T> node = root;
while (node!=null){
if (data.compareTo(node.data) == 0){
return node;
}else if (data.compareTo(node.data) < 0){
node = node.left;
}else {
node = node.right;
}
}
return null;
}
@Override
public T find(T element) {
if(element == null){
return null;
}
Node<T> node = findNode(element);
return Objects.nonNull(node) ? node.data : null;
}
@Override
public void add(T element) {
if(element == null){
throw new IllegalArgumentException("element is null");
}
// 新节点都是红色的
Node<T> node = newNode(element);
// 如果插入的节点是根节点，那我们直接改变它的颜色，把它变成黑色就可以了。
if(root == null){
root = node;
root.color = BLACK;
size++;
return; }
// 查找插入位置
Node<T> parent = root;
// 插入
for(;true;){
if (parent.data.compareTo(node.data)==0) {
// 存在相同节点直接返回
return;
}else if (parent.data.compareTo(node.data) < 0){
// 插入节点比当前节点大，向右查找
if(parent.right == null){
// 直接插入
parent.right = node;
node.parent = parent;
break; }else {
parent = parent.right;
}
}else {
// 插入节点比当前节点小，向右查找
if(parent.left == null){
parent.left = node;
node.parent = parent;
break; }else {
parent = parent.left;
}
}
}
// 已经插入
size++;
Node<T> focusNode = node;
// from 算法导论
// 插入后修正
// parent 和 node 都是红色（连续红节点检查，root元素不用检查）
// 注意：节点为null被当作黑色节点来处理
// 注意：我们的关注节点始终是红色节点
// 注意：叔节点在左分支和右分支的处理是对称的
for (; root != focusNode && focusNode.parent.color == RED;){
Node<T> focusNodeParent = focusNode.parent;
Node<T> focusNodeParentParent = focusNodeParent.parent;
if(focusNodeParent == focusNodeParentParent.left){
Node<T> uncle = focusNodeParentParent.right;
// 叔叔节点是右节点
if( colorOf(uncle) == RED){
// 叔叔节点是红色节点
/**
* CASE 1：如果关注节点是 a，它的叔叔节点 d 是红色
* 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；
* 将关注节点 a 的祖父节点 c 的颜色设置成红色；
* 关注节点变成 a 的祖父节点 c；
* 跳到 CASE 2 或者 CASE 3。
*/
// 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；
setColor(uncle,BLACK);
setColor(focusNodeParent,BLACK);
// 将关注节点 a 的祖父节点 c 的颜色设置成红色
setColor(focusNodeParentParent,RED);
// 关注节点变成 a 的祖父节点 c focusNode = focusNodeParentParent;
}else {
// 叔叔节点是黑色节点
if(focusNodeParent.right == focusNode){
/**
* CASE 2：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的右子节点
*
* - 关注节点变成节点 a 的父节点 b；
* - 围绕新的关注节点b 左旋；
* - 跳到 CASE 3。
*/
focusNode = focusNodeParent;
rotateLeft(focusNode);
}
/**
* CASE 3：如果关注节点是 a，它的叔叔节点 d 是黑色，关注节点 a 是其父节点 b 的左子节点
* - 围绕关注节点 a 的祖父节点 c 右旋；
* - 将关注节点 a 的父节点 b、兄弟节点 c 的颜色互换。
* - 调整结束。
*/
setColor(focusNode.parent,BLACK);
setColor(focusNode.parent.parent,RED);
// 围绕关注节点 a 的祖父节点 c 右旋；
rotateRight(focusNode.parent.parent);
}
}else {
Node<T> uncle = focusNodeParentParent.left;
// 叔叔节点是左节点
if(colorOf(uncle) == RED){
// 叔叔节点是红色节点
// 将关注节点 a 的父节点 b、叔叔节点 d 的颜色都设置成黑色；
setColor(uncle,BLACK);
setColor(focusNodeParent,BLACK);
// 将关注节点 a 的祖父节点 c 的颜色设置成红色
setColor(focusNodeParentParent,RED);
// 关注节点变成 a 的祖父节点 c focusNode = focusNodeParentParent;
}else {
// 叔叔节点是黑色节点
// 如果节点
if(focusNodeParent.left == focusNode){
focusNode = focusNodeParent;
rotateRight(focusNode);
}
setColor(focusNode.parent,BLACK);
setColor(focusNode.parent.parent,RED);
// 围绕关注节点 a 的祖父节点 c 右旋；
rotateLeft(focusNode.parent.parent);
}
}
}
root.color = BLACK;
}
@Override
public T remove(T element) {
if (element == null){
throw new NullPointerException();
}
Node<T> node = findNode(element);
if(node == null){
// 未找到
return null;
}
T returnData = node.data;
// 有两个节点，转换成删除右子树最小节点操作
if(node.left != null && node.right !=null){
// 右树的的最小节点
Node<T> min = node.right;
while (min.left != null){
min = min.left;
}
// 交换到当前位置
node.data = min.data;
// 变成删除min
node = min;
}
// 获取替换节点，上面已经处理了有两个节点的情况
// 处理有一个子节点的情况
Node<T> replaceNode = node.left != null ? node.left : node.right;
if(replaceNode != null){
replaceNode.parent = node.parent;
if (node.parent == null)
root = replaceNode;
else if (node == node.parent.left)
node.parent.left = replaceNode;
else node.parent.right = replaceNode;
node.left = node.right = node.parent = null;
// replaceNode只可能是红节点，进行染黑色处理
/**
* 首先是待删除黑节点有一颗子树的情况下，其子树必然是一个红节点，此时只需要将该红节点替换到待删除黑节点的位置即可，由于黑节点被删除，黑高度降低，那么此时我们就需要做出调整，将刚刚的红节点染色成黑节点
*
* ``` * [p-any] 或者：[p-any]
* / \ / \ * [any][黑] [any][黑]
* /\ /\ * [红][nil] [nil][红]
* ``` */ if(node.color == BLACK){
// replace节点必然为红色，需要改色
replaceNode.color = BLACK;
}
}else if(node.parent == null) {
// 左右节点都是空节点，当前节点是根节点的情况,直接root置空
root = null;
}else {
// 左右子节点都是空节点，且当前节点不是根节点,有两种情况
// 第一种情况是，原本节点就是没有左右节点的节点，如果该节点是一个黑节点，删除则破坏了黑高度，需要修复
// 第二种情况是，原本节点有两个节点，而原本节点的右子树最小节点没有节点，被替换上来之后,需要删除,删除后破坏了黑高度,需要修复
if(node.color == BLACK){
fixAfterDeleted(node);
}
// 删除节点
if(node.parent != null){
// 清除节点
if (node.parent.left == node){
node.parent.left = null;
}else {
node.parent.right = null;
}
}
node.left = node.right = node.parent = null;
}
size--;
return returnData;
}
/**
* 因为删除黑节点会改变黑高度，也会导致两个红节点相连
* <br>
* 又因为我们将删除节点的情况全部转换成了只有一个分支的情况，或者没有分支的情况。
* <br>
* 于是我们只需要分类讨论就行
*
* @param node
*/
private void fixAfterDeleted(Node<T> node){
while (node != root && colorOf(node) == BLACK){
if(node.parent.right == node){
// 当前黑节点在右分支
Node<T> bro = node.parent.left;
if(colorOf(bro) == RED){
/**
* * 兄弟节点是红节点
* 此时父节点必然是黑节点，将其染红；将兄弟染黑
* 进行旋转，将黑兄提到父节点位，此时原本的兄弟分支的黑高没有变化，
* 原本兄弟分支的某个黑节点成了关注节点的新兄弟需要接着处理
*
* [p] * / \ *[bro-红][node]
* / \ * [黑][黑]
*/ //当前兄弟节点必然是红色，父节点必然是黑色 父兄变色
setColor(bro,BLACK);
setColor(bro.parent,RED);
rotateRight(bro.parent);
// 此时关注节点的兄弟节点是原本bro的子节点
}else {
if( Objects.isNull(bro) || (colorOf(bro.right) == BLACK && colorOf(bro.left) == BLACK) ){
/**
* 兄弟是黑节点，且右两个黑子节点（包括nil）
* 将兄弟节点变红，此时当前路径的左右两个节点都少了一个黑高度
* 将关注节点上移（此时，如果新的关注节点是红色，直接染黑，如果是黑色，那么就还需要继续操作）
* [p]
* / \ * [bro-黑][node]
* /\ * [黑][黑]
*/ setColor(bro,RED);
// 关注节点上移
node = node.parent;
}else{
// bro 同侧节点为红的情况
if(colorOf(bro.left) == RED){
/**
* bro是黑色，其同路子节点是红色
* 将该子节点设置为父节点颜色（必然是黑）
* 将bro的颜色设置为父节点颜色
* 将父节点设置为黑色
* 朝双黑节点旋转
* 完成调整
*/
// bro的同路子节点变bro的颜色，bro的父节点变黑色
// 其实此时bro的同路子节点必然是红色，bro必然是黑色，bro的parent可黑可红
setColor(bro.left,colorOf(bro));
setColor(bro,colorOf(bro.parent));
setColor(bro.parent,BLACK);
rotateRight(node.parent);
node = root;
}else {
/**
* bro同侧子节点不为红，该异侧子节点设置为父节点一个颜色
* 将父节点设置为黑色，再将异侧子节点通过旋转提到bro位置
* 再围绕父节点进行旋转达到平衡
*/
setColor(bro.right,colorOf(bro.parent));
setColor(bro.parent,BLACK);
rotateLeft(bro);
// 由于左旋，其右节点已经上来了
// 再围绕bro的parent的parent右旋
rotateRight(bro.parent.parent);
node = root;
}
}
}
}else {
// 当前黑节点在左分支
Node<T> bro = node.parent.right;
if(colorOf(bro) == RED){
//当前兄弟节点必然是红色，父节点必然是黑色 父兄变色
setColor(bro,BLACK);
setColor(bro.parent,RED);
rotateLeft(bro.parent);
// 此时关注节点的兄弟节点是原本bro的子节点
}else {
if( Objects.isNull(bro) || (colorOf(bro.right) == BLACK && colorOf(bro.left) == BLACK) ){
setColor(bro,RED);
// 关注节点上移
node = node.parent;
}else{
// bro 同侧节点为红的情况
if(colorOf(bro.right) == RED){
// bro的同路子节点变bro的颜色，bro的父节点变黑色
// 其实此时bro的同路子节点必然是红色，bro必然是黑色，bro的parent可黑可红
setColor(bro.right,colorOf(bro));
setColor(bro,colorOf(bro.parent));
setColor(bro.parent,BLACK);
rotateLeft(node.parent);
node = root;
}else {
setColor(bro.left,colorOf(bro.parent));
setColor(bro.parent,BLACK);
rotateRight(bro);
// 由于左旋，其右节点已经上来了
// 再围绕bro的parent的parent右旋
rotateLeft(bro.parent.parent);
node = root;
}
}
}
}
}
// 将关注节点变黑，会发生在关注节点为红色或者关注节点为root的情况下
setColor(node,BLACK);
}
private boolean colorOf(Node<T> node){
return node == null? BLACK : node.color;
}
private void setColor(Node<T> node , boolean color){
if(node != null){
node.color = color;
}
}
/**
* 左旋
* @param node
*/
protected void rotateLeft(Node<T> node) {
// 将当前节点的右节点上提
Node<T> newNode = node.right;
// 将新的节点的左节点放到旧节点的右节点
node.right = newNode.left;
// 更新父节点
if (node.right != null) {
node.right.parent = node;
}
// 新节点的左节点设置为旧节点
newNode.left = node;
// 父节点处理
Node<T> parent = node.parent;
if (parent != null) {
if(parent.left == node){
parent.left = newNode;
}else {
parent.right = newNode;
}
}else {
root = newNode;
}
// 新节点的父节点是旧节点的父节点
newNode.parent = parent;
// 旧节点的父节点就是新节点
node.parent = newNode;
// 将新节点设置到父节点的合适位置
}
/**
* 右旋
* @param node
*/
protected void rotateRight(Node<T> node) {
// 当前节点的左节点向上提
Node<T> newNode = node.left;
// 旧节点的左节点是新节点的右节点
node.left = newNode.right;
// 更新父节点
if (node.left != null) {
node.left.parent = node;
}
newNode.right = node;
// parent
Node<T> parent = node.parent;
if (parent != null) {
if(parent.left == node){
parent.left = newNode;
}else {
parent.right = newNode;
}
}else {
root = newNode;
}
newNode.parent = parent;
node.parent = newNode;
}
@Override
public String toString() {
if(root == null){
return "[]";
}
// 中序遍历
String str = toString(root);
return "["+str+"]";
}
private String toString(Node<T> node){
if (node == null){
return "";
}
StringBuilder builder = new StringBuilder();
String leftStr = toString(node.left);
if (!leftStr.isEmpty()){
builder.append(leftStr).append(",");
}
String nodeStr = node.data.toString();
builder.append(nodeStr);
String rightStr = toString(node.right);
if (!rightStr.isEmpty()){
builder.append(",").append(rightStr);
}
return builder.toString();
}
private Node<T> newNode(T data){
Node<T> tNode = new Node<>();
tNode.color = RED;
tNode.data = data;
tNode.parent = null;
tNode.left = null;
tNode.right = null;
return tNode;
}
}
时间复杂度：
查找（Search）
与普通二叉搜索树相同，但得益于平衡性，不会退化成链表，最坏时间复杂度为 O(logn)。
插入（Insert）
步骤：先按二叉搜索树插入(O(log n))，再通过变色和旋转（最多 3 次）恢复平衡。
时间复杂度：O(log n)（旋转操作仅影响局部，常数时间）。
删除（Delete）
步骤：类似插入，但可能触发更复杂的调整（最多 3 次旋转）。
时间复杂度：O(logn)。
旋转操作（Rotations）
单次旋转时间为 O(1)，仅修改少量指针，不影响整体复杂度。
红黑树通过牺牲严格的平衡性（允许适度不平衡），换取了插入/删除操作的高效性，所有核心操作均保证 O(logn) 时间复杂度，适合频繁动态更新的场景（如 Linux 内核调度、Java TreeMap），其复杂性集中再插入和删除操作的修复。
评论已关闭