如果面试被问“红黑树”,可以这样回答
共 6659字,需浏览 14分钟
·
2020-09-17 03:30
![](https://filescdn.proginn.com/31105a5ce7e106a6be49a92b096b4074/29303a2a7a6e09a565fc8e34fcce43e8.webp)
正文
预备知识
![](https://filescdn.proginn.com/003ed0826f477bc43d7c5cff153ae1b1/9a4d8a902d8a1cf1edeccc809a3d900b.webp)
平衡二叉搜索树
①二叉搜索树
②平衡
![](https://filescdn.proginn.com/2b37c341c360443930f351db44967d17/fbb14edd73543f83cae038ea0c1b772c.webp)
③改进二叉搜索树
AVL 树
![](https://filescdn.proginn.com/978ff9010cf637564c8f3d15f8c02fbe/57c964f22b993ec655796bc77b0a19f6.webp)
![](https://filescdn.proginn.com/72dc120be98d89cac6f9d07beebc2385/39e5d6c2f5b7060f0c7ec2cacb6a1d83.webp)
每个结点的平衡因子只可能是 -1、0、1(如果绝对值超过 1,则认为是失衡)
每个结点的左右子树高度差不超过 1
搜索、插入、删除的时间复杂度是 O(logn)
B 树
![](https://filescdn.proginn.com/799c29520739210f6974c5ee960386d7/a6da6970b7f4cd7a41ce1809ff6031c8.webp)
特点如下:
1 个结点可以存储超过 2 个元素,可以拥有超过 2 个子结点
拥有二叉搜索树的一些性质
平衡,每个结点的所有子树高度一致
比较矮
①m 阶 B 树的性质(m ≥ 2)
根结点:1 ≤ x ≤ m - 1
非根结点:┌ m / 2 ┐ - 1 ≤ x ≤ m - 1
根结点:2 ≤ y ≤ m
非根结点:┌ m / 2 ┐ ≤ y ≤ m
②B 树 VS 二叉搜索树
![](https://filescdn.proginn.com/270eaa6d97c70dc9c2ea8f70d96c5f36/c45eec5b3edcc7c1980e8852c20d8c9c.webp)
B 树和二叉搜索树,在逻辑上是等价的
多代结点合并,可以获得一个超级结点,且 n 代合并的超级结点,最多拥有 (2^n) 个子结点 (至少是 (2^n) 阶 B 树)
红黑树定义和性质
每个结点是要么是红色或黑色
根结点必须是黑色
叶结点(外部结点、空结点)是黑色
红色结点不能连续(也就是,红色结点的孩子和父亲都是黑色)
对于每个结点,从该点至 nil(树尾端,Java 中为 null 的结点)的任何路径都包含所相同个数的黑色结点
红黑树与 B 树的等价变换
![](https://filescdn.proginn.com/7665793625dff29946667d37eb040559/86f9bb3c648e9d929a74d99e8d877112.webp)
![](https://filescdn.proginn.com/a12ee4ac7fef629877ef0bbfb9953f68/4cbfde1f6fa2ab90ae6bdb7f9468a6ec.webp)
红黑树与 4 阶 B 树(2-3-4树)具有等价性
黑色结点与红色子结点融合在一起,形成 1 个 B 树结点
红黑树的黑色结点个数与 4 阶 B 树的结点总个数相等
红黑树的基本操作
![](https://filescdn.proginn.com/11b64c3db11fb214f38dd439c086b1d1/9d0a86a5905dd6f6bf5eab57b18067ed.webp)
N-node:当前结点
P-parent:父结点
S-sibling:兄弟结点
U-uncle:叔父结点(P 的兄弟结点)
G-grand:祖父结点(P 的父结点)
左旋
![](https://filescdn.proginn.com/adfe3c9f9b3b32150188855c594fe2c6/4ae9b6228783b0a8c4ee896655d2b006.webp)
右旋
![](https://filescdn.proginn.com/255337401b28a8e64cc5e13192c1a9fd/c86b60000c10d9a26c46bb530872e0b9.webp)
变色
变换规则
把父结点和叔父结点变为黑色
把祖父结点变为红色
把指针定义到祖父结点
把父结点变为黑色
把祖父结点变为红色
对祖父结点右旋
红黑树搜索
![](https://filescdn.proginn.com/30ba77d001c3630e2eb3ad9bc419b961/e1cacd4797015d875bf16777a9eb0629.webp)
从根结点开始检索,把根结点设置为当前结点。
若当前结点为空,返回 nil。
若当前结点不为空,比较当前结点 key 与搜索 key 的大小。
若当前结点 key 等于搜索 key,那么该 key 就是搜索目标,返回当前结点。
若当前结点 key 大于搜索 key,把当前结点的左子结点设置为当前结点,重复步骤 2。
若当前结点 key 小于搜索 key,把当前结点的右子结点设置为当前结点,重复步骤 2。
红黑树插入
定位插入的位置
![](https://filescdn.proginn.com/8d926be5e1ec68d79415ef78c85d74fa/f61f808f44b4f670f3c4a4ff28b8aa44.webp)
从根结点开始检索。
若根结点为空,那么插入结点设为根结点,结束。
若根结点不为空,那么把根结点设为当前结点。
若当前结点为 nil,返回当前结点的父结点,结束。
若当前结点 key 等于搜索 key,那么该 key 所在结点就是插入结点,更新结点的值,结束。
若当前结点 key 大于搜索 key,把当前结点的左子结点设置为当前结点,重复步骤 4。
若当前结点 key 小于搜索 key,把当前结点的右子结点设置为当前结点,重复步骤 4。
插入后实现自平衡
![](https://filescdn.proginn.com/86103a4f2cfc9dc3985582826818876e/e17a09588fa73c0e3e65bc0c5d2206a2.webp)
将插入结点设为将要替换结点的颜色
更新当前结点的值为插入结点的值
![](https://filescdn.proginn.com/992e12fd8f9e1b15b0428d1ad41d64c7/8349873a1bf072616adf7e89694c060c.webp)
将父结点和叔父结点变为黑色
将祖父结点变为红色
将祖父结点设置为当前插入结点
![](https://filescdn.proginn.com/83fdd92392463a643257b03a60898f54/34dae772cafdafb6d0d7d758766a03d7.webp)
将父结点变为黑色
将祖父结点变为红色
将祖父结点右旋
![](https://filescdn.proginn.com/0bd5ffa79854dbfdc160801742d452e9/0f4c4589a7ac0d5d1d62952719297424.webp)
将父结点进行左旋
将父结点设为插入结点,得到场景 4.2.1
进行场景 4.2.1 的处理
![](https://filescdn.proginn.com/c88824a71d46ede5726d5d9f6a0d00d2/c377cc5424fc161bf773434b2706eb61.webp)
将父结点变为黑色
将祖父结点变为红色
对祖父结点进行左旋
![](https://filescdn.proginn.com/4555ed43a9e708794697a375a86ad2f7/a55aa5af9d3b852c01de28bee76c7b96.webp)
将父结点进行右旋
将父结点设置为插入结点,得到场景 4.3.1
进行场景 4.3.1 的处理
![](https://filescdn.proginn.com/b2582cd3e7b8ecb3aafad95768fc76a8/4fb63edaded976066f30c34f4047a595.webp)
红黑树删除
定位删除的位置
删除后实现自平衡
若删除结点无子结点,直接删除即可。
若删除结点只有一个子结点,用子结点替换删除结点。
若删除结点有两个子结点,用**后继结点(大于删除结点的最小结点)**替换删除结点。
![](https://filescdn.proginn.com/6543ba7a4581662c66559d4cde3c0bdb/a0e30cf340eebcdad9ee0a40da1f2153.webp)
![](https://filescdn.proginn.com/efee2d088da0e437925746f8d84c7405/41fc7d8885378cb6d936c13e12af8ae8.webp)
![](https://filescdn.proginn.com/e9c24aec34beac2d87e0fdd1620d640f/9a8d75212504ebaf10df0e1d2e1512f8.webp)
R:替换结点
P:替换结点的父结点
S:替换结点的兄弟结点
SL:兄弟结点的左子结点
SR:兄弟结点的右子结点
灰色:结点颜色可能是红色,也可能是黑色
![](https://filescdn.proginn.com/e494d2a87a082dbd2087a179f7973b48/4142c76e9ca93521be1a63950f52f561.webp)
![](https://filescdn.proginn.com/3d9ce473048a83bf272898733cc1d6b9/d0888d34d40915c18b1025de6b66609d.webp)
将兄弟结点变为黑色
将父结点变为红色
对父结点进行左旋,得到场景 2.1.2.3
进行场景 2.1.2.3 的处理
![](https://filescdn.proginn.com/bc8366fb4f672188b695e0c7c26b48d3/ac0e8aebd08882552a520af850e0eaae.webp)
将兄弟结点的颜色变为父结点的颜色
将父结点变为黑色
将兄弟结点的右子结点变为黑色
对父结点进行左旋
![](https://filescdn.proginn.com/248013865b962b61e97aa0fbf4c424b3/d81600a86b4c8d79e2eaabb39fa55c38.webp)
将兄弟结点变为红色
将兄弟结点的左子结点变为黑色
对兄弟结点进行右旋,得到场景 2.1.2.1
进行场景 2.1.2.1 的处理
![](https://filescdn.proginn.com/eaec686ed04473d62d7dd521ba86a90e/b0b9f2fd103ba737ea1613267bfa5d75.webp)
如果父结点为黑色:将兄弟结点变为红色;将父结点作为新的替换结点;重新进行删除结点的场景处理。
如果父结点为红色:替换结点的父结点和替换结点的兄弟结点颜色交换;删除结点和替换结点的值交换后,删除替换结点。
![](https://filescdn.proginn.com/a3dbf8e4986a02314d1bbddd0f058ab0/3633d949678d2fc37e570c5d9a75c17c.webp)
将兄弟结点变为黑色
将父结点变为红色
对父结点进行右旋,得到场景 2.2.2.3
进行场景 2.2.2.3 的处理
![](https://filescdn.proginn.com/b6e0f8b09d16fb49015aee5c3fec8a34/4d1a064a80ae8ac5c133244005897973.webp)
将兄弟结点的颜色变为父结点的颜色
将父结点变为黑色
将兄弟结点的左子结点变为黑色
对父结点进行右旋
![](https://filescdn.proginn.com/460456430e677cb4761689a753aa9448/6aa874d286f145dfc2c12d4db506a93e.webp)
将兄弟结点变为红色
将兄弟结点的右子结点设为黑色
对兄弟结点进行左旋,得到场景 2.2.2.1
进行场景 2.2.2.1 的处理
![](https://filescdn.proginn.com/8f6200e0a4be5fef28462730aede9eca/2bed4b5833be13687e02af15a268e8b0.webp)
如果父结点为黑色:将兄弟结点变为红色;将父结点作为新的替换结点;重新进行删除结点的场景处理。
如果父结点为红色:替换结点的父结点和替换结点的兄弟结点颜色交换;删除结点和替换结点的值交换后,删除替换结点。
最近热文
• 她是北大“一个人的毕业照”主人公,2010级古生物专业独苗,十年后搞起了AI • 刚刚用鸿蒙跑了个“hello world”!跑通后,我特么开始怀疑人生了.... • 今天终于搞懂了:为什么 Java 的 main 方法必须是 public static void? • 朋友入职中软一个月(外包华为)就离职了! 最近整理了一份大厂算法刷题指南,包括一些刷题技巧,在知乎上已经有上万赞。同时还整理了一份6000页面试笔记。关注下面公众号,在公众号内回复「刷题」,即可免费获取!回复「加群」,可以邀请你加入读者群!
明天见(。・ω・。)ノ♡