笔试算法题（51）：简介 - 红黑树（RedBlack Tree）
2024-08-30 19:15:43
红黑树（Red-Black Tree）
- 红黑树是一种BST，但是每个节点上增加一个存储位表示该节点的颜色（R或者B）；通过对任何一条从root到leaf的路径上节点着色方式的显示，红黑树确保所有路径的差值不会超过一倍，最终使得BST接近平衡；
- 红黑树内每个节点包含五个属性：color, key, left, right和p，p表示指向父亲节点的指针；一棵BST需要同时满足下述五个性质才能称作红黑树：
每个节点只能是红色或者黑色节点中的一种；
根节点必须是黑色；
每个叶节点（NULL）必须是黑色；
如果一个节点是红色，则它的两个子节点必须是黑色；
对于树中任何一个节点，该节点到其叶节点的所有路径上的黑色节点数相同
- 红黑树的空间复杂度为O(N)；支持三种操作：search, insert, delete，并且所有操作的时间复杂度都为O(logN)，最好情况跟最坏情况的复杂度相同。对于search操作而言，其依赖BST的性质，所以不需 要依赖节点的着色信息；着色信息仅为了保证BST的平衡性，insert和delete操作则可能破坏BST的平衡性，所以这两种操作需要对红黑树中节点 的着色信息进行调整。
//左旋操作中，oldroot的右子节点成为新的root，root的左子节点成为oldroot的右子节点，
//oldroot成为新root的左子节点
template <class KeyType>
void Node<KeyType>::RotateLeft(Node<KeyType> * & root) {
Node<KeyType> * oldRoot = root;
root = root->mySubtree[RIGHT];
oldRoot->mySubtree[RIGHT] = root->mySubtree[LEFT];
root->mySubtree[LEFT] = oldRoot;
} //右旋操作中，oldroot的左子节点成为新的root，root的右子节点成为oldroot的左子节点，
//oldroot成为新root的右子节点
template <class KeyType>
void Node<KeyType>::RotateRight(Node<KeyType> * & root) {
Node<KeyType> * oldRoot = root;
root = root->mySubtree[LEFT];
oldRoot->mySubtree[LEFT] = root->mySubtree[RIGHT];
root->mySubtree[RIGHT] = oldRoot;
} //向T索引的红黑树中插入新节点z，使用BST的性质查找z的插入位置，并且将新节点z标
//注为红色；
RB-INSERT(T, z)
y ← nil[T]
x ← root[T]
while x ≠ nil[T]
do y ← x
if key[z] < key[x]
then x ← left[x]
else x ← right[x]
p[z] ← y
if y = nil[T]
then root[T] ← z
else if key[z] < key[y]
then left[y] ← z
else right[y] ← z
left[z] ← nil[T]
right[z] ← nil[T]
color[z] ← RED
RB-INSERT-FIXUP(T, z)
插入一个节点并标注为红色的操作可能破坏红黑树的性质2和性质4；当插入节点为根节点的时候破坏性质2，此时直接将其变成黑色就可以恢复；当破坏性质4的时候则需要一系列的恢复操作；
case1：原树为空，新节点为根节点；恢复策略为将其改成黑色；
case2：新节点的父节点是黑色；满足所有红黑树规则；
case3：新节点的父节点是红色，父节点的兄弟节点是红色；恢复策略为将新节点的父节点和父节点的兄弟节点改成黑色，其祖父节点改成红色，针对祖父节点重新调用该方法；
case4：新节点的父节点是红色，父节点的兄弟节点是黑色，新节点为父节点的右子；恢复策略为以新节点的父节点为支点左旋；
case5：新节点的父节点是红色，父节点的兄弟节点是黑色，新节点为父节点的左子；恢复策略为将新节点的父节点改成黑色，祖父节点改成红色，并以祖父节点为支点右旋；
RB-INSERT-FIXUP(T, z)
while color[p[z］ = RED
do if p[z] = left[p[p[z］]
then y ← right[p[p[z］]
if color[y] = RED
then color[p[z］ ← BLACK ▹ Case
color[y] ← BLACK ▹ Case
color[p[p[z］] ← RED ▹ Case
z ← p[p[z］ ▹ Case
else if z = right[p[z］
then z ← p[z] ▹ Case
LEFT-ROTATE(T, z) ▹ Case
color[p[z］ ← BLACK ▹ Case
color[p[p[z］] ← RED ▹ Case
RIGHT-ROTATE(T, p[p[z］) ▹ Case
else (same as then clause with "right" and "left" exchanged)
color[root[T］ ← BLACK //
RB-DELETE(T, z)
if left[z] = nil[T] or right[z] = nil[T]
then y ← z
else y ← TREE-SUCCESSOR(z)
if left[y] ≠ nil[T]
then x ← left[y]
else x ← right[y]
p[x] ← p[y]
if p[y] = nil[T]
then root[T] ← x
else if y = left[p[y］
then left[p[y］ ← x
else right[p[y］ ← x
if y ≠ z
then key[z] ← key[y]
copy y's satellite data into z
if color[y] = BLACK
then RB-DELETE-FIXUP(T, x)
return y
case1：x的兄弟w是红色
case2：x的兄弟w是黑色，并且w的两个孩子是黑色
case3：x的兄弟w是黑色，并且w的左孩子是红色，w的右孩子是黑色
case4：x的兄弟w是黑色，并且w的右孩子是红色
RB-DELETE-FIXUP(T, x)
while x ≠ root[T] and color[x] = BLACK
do if x = left[p[x］
then w ← right[p[x］
if color[w] = RED
then color[w] ← BLACK ▹ Case
color[p[x］ ← RED ▹ Case
LEFT-ROTATE(T, p[x]) ▹ Case
w ← right[p[x］ ▹ Case
if color[left[w］ = BLACK and color[right[w］ = BLACK
then color[w] ← RED ▹ Case
x ← p[x] ▹ Case
else if color[right[w］ = BLACK
then color[left[w］ ← BLACK ▹ Case
color[w] ← RED ▹ Case
RIGHT-ROTATE(T, w) ▹ Case
w ← right[p[x］ ▹ Case
color[w] ← color[p[x］ ▹ Case
color[p[x］ ← BLACK ▹ Case
color[right[w］ ← BLACK ▹ Case
LEFT-ROTATE(T, p[x]) ▹ Case
x ← root[T] ▹ Case
else (same as then clause with "right" and "left" exchanged)
color[x] ← BLACK
最新文章
- HTML5 之 FileReader（图片上传）
- 关于BT网络的一些改进
- AndroidDevTools简介
- 安装SSD固态硬盘
- ios开发之OC基础-ios开发学习路线图
- 使 div 元素看上去像一个按钮
- 分布式算法(一致性Hash算法)
- sed 批量替换多个文件里的某个字符/串
- ftp上来显示的时间和系统时间不一致
- Java中的Runtime类
- BZOJ 3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者（贪心）
- JavaWeb开发之Servlet
- Node.js开发Web后台服务
- drbd(三)：drbd的状态说明
- Angular2入门：TypeScript的模块
- React-Native之截图组件view-shot的介绍与使用
- NOI2018Day1T1 归程 并查集 kruskal kruskal重构树 倍增表 Dijkstra
- 主从热备+负载均衡（LVS + keepalived）
- 【Tomcat】tomcat配置文件详解
- WPF进度条