面试让我手写红黑树( 七 ) _红黑树

其实根据红黑树的历史来看，最早红黑树就是来自于2-3树的结构，所以要学习清楚的结构就要学习 2-3树。但同时对于 2-3树的学习也不能只是依靠一份理论，否则对于红黑的学习来看，就是用不太理解的 2-3树理论套红黑树理论，依旧没法理解。所以小傅哥在上一章专门讲解了 2-3树，并做了具体的代码实现。
现在来本章，我们在来看看红黑树与2-3树的关系；
红黑树红黑树 2-3树

文章插图

文章插图

一棵标准二叉红黑树红黑树演化（红色节点拉平）最终恢复到2-3树
红黑树一棵在2-3树基础上的左倾红黑树，这样就可以把红色节点与对应的父节点拉平，再把两个拉平的节点放到一个节点中。就是我们熟悉的2-3树了。如果你还没有学习过2-3树，最好先看下小傅哥的2-3树，否则你会看的很吃力
现在再来看下红黑树的五条定义；

每个节点不是红色就是黑色。黑色决定平衡，红色不决定平衡。这对应了2-3树中一个节点内可以存放1~2个节点。
根是黑色的。这条规则有时会被省略。由于根总是可以从红色变为黑色，但不一定相反，因此该规则对分析几乎没有影响。
所有叶子 (NIL) 都是黑色的。这里指的是红黑树都会有一个空的叶子节点，是红黑树自己的规则。
如果一个节点是红色的，那么它的两个子节点都是黑色的。通常这条规则也叫不会有连续的红色节点。这体现在2-3树中，一个节点最多临时会有3个节点，中间是黑色节点，左右是红色节点。2-3树中出现这样的情况后，会进行节点迁移，中间节点成为父节点，左右节点成为子节点。
从给定节点到其任何后代 NIL 节点的每条路径都包含相同数量的黑色节点。对应2-3树中，每一层都只是有一个节点贡献了树高决定平衡性，也就是对应红黑树中的黑色节点。

好啦，现在再看这5条理论是不就不需要再死记硬背了。因为编程本就是对数学逻辑的具体实现，只要把核心逻辑理顺其实很好理解。接下来小傅哥就带着大家动手实现一下红黑树。
2. 红黑树结构实现
基于 BST 二叉搜索树的基础上，AVL树添加了树高作为计算平衡因子的条件，那么红黑树也需要添加一个新的颜色属性，用于处理平衡操作。

public class Node { public Class clazz; public Integer value; public Node parent; public Node left; public Node right; // AVL 树所需属性 public int height; // 红黑树所需属性 public Color color = Color.RED; }

相比于AVL树通过左右旋转平衡树高，红黑树则是在2-3树的基础上，只对黑色节点维护树高，所以它会使用到染色和左右旋来对树高调衡。染色与左右旋相比，减少了平衡操作

源码地址：https://github.com/fuzhengwei/java-algorithms
本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree
动画演示：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html—— 红黑树初次理解还是比较困难的，可以结合学习内容的同时做一些动画演示。

2.1 左倾染色
新增节点1，相当于2-3树中在节点2上添加了一个节点，这个时候并不影响树高，只需要染色保持红黑树的规则即可。染色过程如图所示。

文章插图

Node uncle = grandParent.right; // 染色 if (uncle.color == Node.Color.RED){ parent.color = Node.Color.BLACK; uncle.color = Node.Color.BLACK; grandParent.color = Node.Color.RED; current = grandParent; }