1.什么是红黑树
红黑树是一种自平衡的二叉树
2.红黑树与234树的关系
红黑树与234树是有等价关系的，每一个红黑树都对应这一个234树，而每一个234树则对应着多个红黑树
2.1.什么是234树呢
234树是阶为4的B树,是一个由叶子节点向根部生长的树，正因为是由叶子向根部生长，所以234树是一颗永远平衡的树。
2.2. 234树的节点
2.3. 234树的生长
2.4.红黑树与234树的等价关系
2.5.从234树的角度理解红黑树的五大性质
1、节点必须是红黑或者黑色。
2、根节点必须是黑色。
234树只有三种节点，而每种节点转换成红黑树就是：单节点（黑色），双节点（上黑下红），三节点（父节点黑，两儿子是红），同样这也能证明第二个性质，因为234树每个节点转换成红黑树，无论是234树的2节点、3节点或者4节点在根节点，转换成红黑树，都是黑色在上面，所以无论怎样，根节点一定是黑色。
3、叶子节点（NIL）是黑色。（NIL节点无数据，是空节点）。
这里说的叶子节点其实是人为加上去的，是不存在，那既然是认为加上去的，为什么要定义为黑色呢？其实从性质2可以反推：当这颗红黑树不存在实际的节点，那是不是只能为空呢，那这个时候根节点就是空，再因为根节点必须是黑色，所以叶子节点（NIL）必须是黑色。
4、红色节点必须有两个黑色儿子节点。
从234树来看，每个节点都会从2节点成长成4节点，每一种节点都是上黑下红，4节点两个红色的子节点下面连的必定是黑色的节点。当这个红色节点没有子节点是，他还有一个为NIL的空节点，由性质3空节点必须是黑色，也能证明红色节点必须有两个黑色的儿子节点。
5、从任一节点出发到其每个叶子节点的路径，黑色节点的数量相当（黑色平衡）
这个性质也就是红黑树自平衡的一个重要性质了，红黑树平衡一直指的是黑色平衡，为什么黑色永远是平衡的？
从234树来看，234树是一个永远平衡的树，因为他是自下而上生长的。而他只有三种节点，2节点、3节点、4节点转化成红黑树的节点都是有且仅有一个黑色节点，正因为234树从任一节点出发到每一个叶子节点的路径的节点都是相等的，而这些节点转换成红黑树时，每一个节点都只能转化出一个黑色节点，所以红黑树从任一节点出发到其每一个叶子节点的路径上，黑色节点的数量都是相等的。
2.3.java代码实现红黑树
该部分代码是模仿TreeMap源码加上自己理解，作了简化写的。
2.3.1.基本变量定义
在了解红黑树怎么插入和删除节点之前，得先知道左旋右旋是怎样的。
2.3.2.左旋
左旋主要有三个关键点：（以要左旋的节点为X举例说明）
1、x节点是否存在右子节点，不存在则不能左旋
2、x节点的父节点要成为其右子节点的父节点
3、x节点的右子节点（xr）的左子节点（rl）要成为x节点新的右子节点
2.3.3.右旋
右旋和左旋是一样的，只是方向全部都得反过来
右旋的三个关键点：（以要右旋的节点为X举例说明）
1、x节点是否存在左子节点，不存在则不能右旋
2、x节点的父节点要成为其左子节点的父节点
3、x节点的左子节点（xl）的右子节点（lr）要成为x节点新的左子节点
2.3.4.增加节点
新增节点
平衡新增节点的颜色
2.3.5.前驱节点和后继节点
在了解删除节点前，需要先了解两个概念，在删除时会用到：
- 前驱节点：小于当前节点的最大值
- 后继节点：大于当前节点的最小值
代码实现：
前驱节点
后继节点
2.3.6.删除节点
1、删除的节点为叶子节点时（这里不是指根节点和NIL节点）：
- 红色：直接删除
- 黑色：这时兄弟节点肯定存在，不存在红黑树不能平衡，需要判断兄弟节点是否为黑色，若为黑色，则兄弟节点变成红色，父节点为红色时，染黑；父节点为黑色时，将父节点变成需要平衡的节点，继续循环这个步骤，直到找到有一个父节点为红色。
2、删除的节点存在一个子节点：
- 红色：直接删除，子节点代替该节点
- 黑色：若子节点为红色，子节点变成黑色代替；若子节点为黑色，则进行第一种情况里，节点为黑色的步骤。
代码实现
自此红黑树的增删查,已用java代码全部实现
下面为整个类的代码,与上面是重复的,方便复制:
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.bianchenghao6.com/h6javajc/2346.html