打牢地基-拿下红黑树

红黑树

红黑树、2-3树的简单定义:

实现红黑树的基本结构以及添加操作(维护定义，左旋、右旋、颜色反转)

红黑树与BST、AVL 的性能比较及总结；

1. 红黑树的简单定义:

1.1 基本特性

算法导论对红黑树的定义有一定弊端，上来直接看定义，会懵

1.2 理解红黑树更好的一种方式 - 算法4

红黑树与2-3树的等价关系，理解2-3树和红黑树之间的关系红黑树就很简单了学习2-3树不仅对理解红黑树有帮助，对于理解B类树，也是有巨大帮助的:

1.3 2-3 树

1.3.1 2-3 树的特性:

一棵完整的2-3树

1.3.2 2-3 树如何维持绝对的平衡

2-3树维持绝对平衡的步骤:

新入节点如果打破了2-3树的定义(加入节点后节点中存储了>2个的元素)，则中间节点上移成为根节点

1.3.3 2-3树和红黑树是等价的

因为我们定义的树结构不会用具体的对象去定义节点连接的边，所以我们将3节点中的较小元素的节点用红色表示，其在较大元素节点的左边，并且表示为红色。如下图所示:

红黑树中红色节点的由来:

红黑树不是AVL树，但是是保持黑平衡的二叉树(节点的左右黑子树高度差 1.3.4 红黑树的代码定义(对BST树进行改造)1.3.4.1 定义红黑树的节点颜色

1.3.4.2 红黑树维持根节点为黑色 & 等价2-3树 中2节点的新增操作

转换过程:

1.3.4.3 红黑树对应等价2-3树3节点融合(新增节点操作) 颜色反转与右旋转

场景1:新加元素的val比当前3节点的值都大

当前场景(新加入节点在当前节点的右侧)新增完节点后:

会发现变形完后的临时4节点会变为3个2节点，此时节点颜色都为黑色接下来当临时4节点变为3个2节点后，根节点需要继续向上融合，且当前根节点需要变为红色

最后我们发现待向上(与父亲节点)融合的根节点需要变为红色其实这个过程就是颜色反转- flip_colors如下图所示:

至

场景2:新加元素的val比当前3节点的值都小如下图所示:

此时需要进行一个右旋转(对根进行旋转)如下图所示:

经过右旋转，变为如下形式:

之后再进行颜色反转就可以保证红黑树每一个红色节点的子树跟节点都为黑色的性质了。

其实会发现，x的节点颜色值跟原先根节点的颜色值保持一致，之后原先跟节点的颜色值变为红色，表示当前3个2节点对应临时的4节点。

**场景3: 新加元素的val在当前3节点的中间

左 右 颜色反转所以通过总结可以知道：

如下所示，我们最终实现的红黑树结构定义以及add元素操作

2 红黑树与AVL、BST 之间的性能比较及差异

2.1 红黑树性能测试

红黑树相对于AVL树insert 和 remove 操作更有优势一点

3. 红黑树的性能总结

红黑树性能总结:

TreeMap、TreeSet 底层是红黑树，统计性能更优。如下图所示: