通俗易懂的红黑树图解(上)
source link: https://www.zoo.team/article/red-black-tree-1
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
前言
○ 学习红黑树难吗？
红黑树本质上是一颗二叉查找树，它是在二叉查找树的基础上给节点增加红黑颜色属性以及五条约束的性质。所以学习红黑树之前，需要先了解一下二叉查找树的知识；红黑树与二叉查找树的查找操作是一模一样的，所以掌握了二叉查找树之后，学习红黑树就只剩下增加及删除节点了（注意：红黑树没有更新节点操作）。
本文主要是介绍红黑树的基础知识以及增加节点操作，删除操作会放到《通俗易懂的红黑树图解（下）》。增加节点操作从内容上看有五种场景，场景一、二、三比较简单，实际上只需要重点关注后两种场景，阅读到这里，是不是觉得红黑树也不难。
关键字： 二叉查找树 学习红黑树不难
言归正传
○ 什么是红黑树？
红黑树（英语：Red-Black-Tree）是在 1972 年由 鲁道夫·贝尔 发明，被称为" 对称二叉 B 树 "，是一种由红黑节点组成并能自平衡的二叉查找树。
红黑树保证了最坏情形下在 O(logn) 时间复杂度内完成查找、插入及删除操作；因此红黑树可用于很多场景，比如在 Java 的集合框架 (HashMap、TreeMap、TreeSet)、Nginx 的 Timer 管理、Linux 虚拟内存管理以及 C++ 的 STL 等等都能看到它的应用。
红黑树另外一个熟知的应用场景就是面试了，红黑树作为数据结构当中最典型的一种树，常被拿来当面试题考查树的相关知识。
关键字： 二叉查找树 、 自平衡 、 面试
○ 大 O 记法
在比较算法性能时，不仅仅考虑算法计算时间及空间等因素，更重要的是数据量变化时算法计算时间及空间是如何变化的，它们是什么样的变化关系曲线；大 O 记法就是用来表示算法在最坏情况下，算法复杂度与数据量的变化关系，但它只是一种粗略的统计。
O(1)：计算时间与数据量大小没有关系，是常量时间；
O(n)：计算时间与数据量成线性正比关系； O(logn)：计算时间与数据量成对数关系；
二叉查找树
○ 什么是二叉查找树
二叉查找树（英语：Binary Search Tree），也称为二叉搜索树、有序二叉树（Ordered Binary Tree）或排序二叉树（Sorted Binary Tree），是指一棵空树或者具有下列性质的二叉树：
- 若任意节点的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
- 若任意节点的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
- 任意节点的左、右子树也分别为二叉查找树
- 没有键值相等的节点
关键字： 任意非空二叉查找树，左子节点值 < 根节点值； 根节点值 < 右子节点值
○二叉查找树的查找操作
在二叉查找树中查找 N ，首先从根节点开始，将根节点设置为当前节点，若当前节点为空，则查找失败，若 N 与当前节点值相等，返回当前节点，若 N 大于当前节点值，则从当前节点的右子节点开始查找，否则从当前节点的左子节点开始查找，直到返回目标节点或者查找失败；
如下图在二叉查找树中查找目标 8 ，查找路径依次为 ⑨ --> ⑥ --> ⑦ --> ⑧
关键词： 红黑树的查找也是这么简单！！
○二叉查找树遍历
遍历是二叉树上最重要的运算之一，它是指沿着某条搜索路线，依次对二叉树中的每一个节点均且仅做一次访问；L、D、R分别表示遍历左子树、访问根节点及遍历右子树
前序遍历【DLR】：前序遍历也叫先根遍历，先访问根节点然后遍历左子树，最后遍历右子树；
// 示例代码
preOrderTraverse(node) {
if (node) {
this.visitNode(node);
this.preOrderTraverse(node.left);
this.preOrderTraverse(node.right);
}
}
中序遍历【LDR】：中序遍历也叫中根遍历，先遍历左子树然后访问根节点，最后遍历右子树；
// 示例代码
inOrderTraverse(node) {
if (node) {
this.inOrderTraverse(node.left);
this.visitNode(node);
this.inOrderTraverse(node.right);
}
}
后序遍历【LRD】：后序遍历也叫后根遍历，先遍历左子树然后遍历右子树，最后访问根节点；
// 示例代码
postOrderTraverse(node) {
if (node) {
this.postOrderTraverse(node.left);
this.postOrderTraverse(node.right);
this.visitNode(node);
}
}
红黑树
○ 为什么还要红黑树？
二叉查找树并非平衡树，它只限制了左右子树与根点之间的大小关系，只有在平衡二叉查找树时，其时间复杂度才能达到 * O(logn) * ，并且在极端情况下它甚至会退化成链表；
如下所示在新创建的二叉查找树上依次添加数据 1、2、3、4、5、6、7、8、9、10 节点，此二叉查找树就退化成了链表，增删查性能也退化到了O(n)，所以为了避免这种情况，就出现了 AVL 及红黑树这种能自平衡的二叉查找树；
AVL 树是严格的平衡二叉树，必须满足所有节点的左右子树高度差不超过 1；而红黑树是相对黑色节点平衡的二叉树，
关键字： AVL 树 红黑树
○ 红黑树的性质
- 每个节点或者是黑色或者是红色
- 根节点是黑色
- 每个叶子节点（null）是黑色
- 如果一个节点是红色，则它的子节点必须是黑色，即两个红色节点不能直接相连
- 从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑色节点
红黑树的五个性质避免了二叉查找树退化成单链表的情况，并且性质 4 和性质 5 确保了任意节点到其每个叶子节点路径中最长路径不会超过最短路径的 2 倍，即一颗树是黑红节点相间的树，另一颗全是黑节点的树；也就是红黑树是相对黑色节点的平衡二叉树；
关键字: 节点非黑即红 、 两红色节点不能直接相连 、 从一节点出发抵达所有叶子节点（null）经过的黑色节点数目相同
○ 红黑树自平衡的实现：
红黑树节点的插入和删除可能会破坏上述红黑树的性质并打破它的平衡，因此需要进行调整从而让红黑树重新恢复平衡；调整分两种方式：旋转以及变色。
- 旋转又分为左旋转和右旋转两种形式：
左旋：如下图所示以 P 为旋转支点，旋转支点 P 的右子节点 R 变为父节点，其右子节点 R 的左子节点 RL 变为旋转支点 P 的右子节点；左旋之后左子树的节点相对旋转之前要多出一个节点，也就是左子树从右子树借用一个节点；
/**
* 左旋示例代码：
* P R
* / \ / \
* L R ====> P RR
* / \ / \
* RL RR L RL
* @param node 旋转支点
*/
rotateLeft(node) {
// R
const rchild = node.right;
// P.right = RL
node.right = rchild.left;
// RL.parent = P;
if (rchild.left) {
rchild.left.parent = node;
}
// R.parent = P.paretn
rchild.parent = node.parent;
// 根节点情况，
if (!node.parent) {
this.root = rchild;
} else {
if (node === node.parent.right) {
// node 是父节点的右节点，
node.parent.right = rchild;
} else {
// node 是父节点的左节点，
node.parent.left = rchild;
}
}
// R.left = P
rchild.left = node;
// P.parent = R;
node.parent = rchild;
}
右旋：如下图所示以 R 为旋转支点，旋转支点 R 的左子节点 P 变为父节点，而左子节点 P 的右子节点 RL 变为旋转支点 R 的左子节点；右旋之后右子树的节点相对旋转之前要多出一个节点，也就是右子树从左子树借用一个节点； 
/**
* 右旋示例代码：
* R P
* / \ / \
* P RR ====> L R
* / \ / \
* L RL RL RR
* @param node 旋转支点
*/
rotateRight(node) {
// P
const lchild = node.left;
// R.left = RL ;
node.left = lchild.right;
// RL.parent = R
if (lchild.right) {
lchild.right.parent = node;
}
// P.parent = R.parent;
lchild.parent = node.parent;
// 根节点情况，
if (!lchild.parent) {
this.root = lchild;
} else {
if (node === node.parent.right) {
// node 是父节点的右节点，
node.parent.right = lchild;
} else if (node === node.parent.left) {
// node 是父节点的左节点，
node.parent.left = lchild;
}
}
// P.right = R;
lchild.right = node;
// R.parent = P;
node.parent = lchild;
}
-
变色就是由黑色节点变成红色节点或者红色节点变成黑色节点；
○ 节点插入
具体到实际应用中，红黑树的节点是不能随意旋转和变色的，红黑树的旋转和变色有方式方法，首先需要先找到插入节点的父节点位置，与红黑树查找方式类似。本文以插入的节点为红色为例，当然也可以用黑色节点作为插入节点，但会更复杂。另外本文中所有节点中提的值都指的是 Key ，实际上节点还存在其它属性。
场景一：空树
根据红黑树性质第二点，红黑树根节点为黑色，即将插入节点修改成黑色即可；
处理：插入节点 N 变成黑色节点并设置为根节点；
场景二：插入节点 Key 已存在
在插入节点之前，红黑树是保持着平衡状态，只需要将插入节点的颜色变为被替换节点的颜色，同时替换掉原节点；
处理：插入的节点 N2 变成原节点 N 的颜色并替换掉 N 节点；图中节点为灰色表示节点可以是红色或者是黑色，下图同理；
场景三：插入节点的父节点是黑色节点
处理：插入的是红色节点 N，并不影响红黑树的平衡，插入之后不需要作其它处理。
场景四：插入节点的父节点是红色节点且叔叔是红色节点
插入节点的叔叔节点是红色节点，根据红黑树性质 4 ，两个红色节点不能直接相连；
处理：把父节点 P 及叔叔节点 S 由红色节点变成黑色节点，再把祖父节点 PP 变成红色，至此解决了插入节点与父节点两个红色节点直连的问题，并且黑色节点数量保持不变，但祖父节点由黑色变成了红色； 如果祖父节点的父节点是红色节点应如何处理？ 处理：将祖父节点 PP 当作新插入的红色节点，从祖父节点的父节点开始由底向上进行处理，直至插入节点的父节点为黑色节点或者插入节点为根节点。
场景五：插入节点的父红点是红色节点，且叔叔节点是空 (null) 节点或者是黑色节点
- 场景 5.1，插入节点 N 是父节点 P 的左节点且父节点 P 是祖父节点 PP 的左节点:
叔叔节点是空节点这种场景好理解，下图中叔叔节点为黑色是什么情况，它不是已经处于非平衡状态了么？莫急，下图只是红黑树的局部图，回顾一下场景四由底向上处理时，祖父节点 PP 由黑色变成红色，对应到下图就是红色的父节点 P。 处理：父节点 P 变成红黑色，祖父节点变成红色，并以祖父节点 PP 为支点进行右旋；
- 场景 5.2，插入节点是父节点的右节点且父节点 P 是祖父节点 PP 的左节点:
处理：以插入节点的父节点 P 为支点进行左旋，转换到场景 5.1；
- 场景 5.3，插入节点 N 是父节点 P 的右子节点且父节点 P 是祖父节点 PP 的右节点:
处理：与场景 5.1 互为镜像，父节点 P 变成黑色，祖父节点变成红色，并以祖父节点 PP 为支点进行左旋；
- 场景 5.4，插入节点的父节点的左子节点，父节点是祖父节点的右子节点：
处理：与场景 5.2 互为镜像，以插入节点的父节点 P 为支点进行右旋，转换到场景 5.3；
节点定义：
/**
* 节点
*/
class Node {
constructor(key, value, color = COLOR.RED) {
this.key = key;
this.value = value;
this.color = color;
this.left = null;
this.right = null;
this.parent = null;
}
}
节点插入及插入平衡操作
/**
* 插入key, value
*/
insert(key, value) {
if (this.root) {
// 红黑树为非空场景
let parent;
let node = this.root;
const newNode = new Node(key, value, COLOR.RED);
// 查找插入位置
while (node) {
parent = node;
if (key === node.key) {
// 场景二： 插入节点key已存在
newNode.color = node.color;
this.update(node, newNode);
return;
} else if (key < node.key) {
node = node.left;
} else {
node = node.right;
}
}
newNode.parent = parent;
if (key < parent.key) {
parent.left = newNode;
} else {
parent.right = newNode;
}
this.balanceInsertion(newNode);
} else {
// 场景一：红黑树为空树场景
this.root = new Node(key, value, COLOR.BLACK);
}
}
// 插入节点平衡修正
balanceInsertion(node) {
// 场景三：插入节点的父节点为黑色节点，无需修正
while (node.parent != null && node.parent.color === COLOR.RED) {
let uncle = null;
// 父节点是祖父节点左节点
if (node.parent === node.parent.parent.left) {
uncle = node.parent.parent.right;
// 场景四：叔叔节点为红色
if (uncle != null && uncle.color === COLOR.RED) {
// 父节点、叔叔节点变成黑色，祖父节点变成红色，以祖父节点当作需要新节点继续调用修正方法；
node.parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
node.parent.parent.color = COLOR.RED;
node = node.parent.parent;
continue;
}
// 场景五：叔叔节点为空节点或者是黑色节点；
// 场景5.2 插入节点是父节点的右节点，先进行左旋转换到场景5.1
if (node === node.parent.right) {
// 左旋之后，原插入节点的父节点变成新插入节点；
node = node.parent;
this.rotateLeft(node);
}
// 场景5.1 插入节点是父节点的左节点；
// 父节点变成黑色、祖父节点变成红色
node.parent.color = COLOR.BLACK;
node.parent.parent.color = COLOR.RED;
// 对祖父节点右旋
this.rotateRight(node.parent.parent);
} else {
// 父节点是祖父节点右子节点
uncle = node.parent.parent.left;
// 场景四：叔叔节点为红色
if (uncle != null && uncle.color === COLOR.RED) {
// 父节点、叔叔节点变成黑色，祖父节点变成红色，以祖父节点当作需要新节点继续调用修正方法；
node.parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
node.parent.parent.color = COLOR.RED;
node = node.parent.parent;
continue;
}
// 场景5.4 插入节点是父节点的左节点，先进行右旋转换到场景5.3
if (node === node.parent.left) {
// 右旋之后，原插入节点的父节点变成新插入节点；
node = node.parent;
this.rotateRight(node);
}
// 场景5.3插入节点是父节点的右节点；
// 父节点变成黑色、祖父节点变成红色
node.parent.color = COLOR.BLACK;
node.parent.parent.color = COLOR.RED;
// 对祖父节点左旋
this.rotateLeft(node.parent.parent);
}
}
this.root.color = COLOR.BLACK;
}
总结
通俗易懂的红黑树图解（上）基本就介绍完了，主要讲的是红黑树的基本性质、查找以及插入操作。下篇就开始讲一讲红黑树的删除，和插入节点一样只需要做些旋转及变色操作，真的不难！
❉ 作者介绍 ❉
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK