树的删除六、红黑树与AVL树的比较七、红黑树的应用八、红黑树模拟实现一、红黑树的概念

红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。

通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。

每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的则它的两个孩子结点是黑色的即树中没有连续的红色节点对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点即每条路径的黑色节点数量相等每个叶子结点(这里的叶子结点指的是空结点也叫做NIL节点

红黑树中第三和第四条规则构成互斥极限的最短一定是全黑极限的最长一定是一黑一红

enum

红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步一、按照二叉搜索的树规则插入新节点。

二、检测新节点插入后红黑树的性质是否造到破坏。

因为新节点的默认颜色是红色如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连续的红色节点此时需要对红黑树分情况来讨论。

情况一:

cur为当前节点p为父节点g为祖父节点u为叔叔节点。

此处看到的树可能是一颗完整的树但是也有可能是一颗子树。

解决方式是将将p,u改为黑g改为红。

继续把g当成curg是根节点需要将g改为黑色如果g是子树且g的双亲颜色为红色则需要继续向上调整。

情况二:

如果u节点不存在那么cur一定为新插入的节点否则就违反性质4。

如果u节点存在则一定是黑色的cur之前也是黑色的因为新增节点是a、b节点所以现在它是红色。

解决方式如果p为g的左孩子cur为p的左孩子则进行右单旋转p为g的右孩子cur为p的右孩子则进行左单旋转。

然后再将p变黑g变红。

情况三:

解决方式如果p为g的左孩子cur为p的右孩子则针对p做左单旋转如果p为g的右孩子cur为p的左孩子则针对p做右单旋转。

旋转后就转变为了情况二。

在这三种情况中都有cur为红p为红g为黑可以看出红黑树的关键是叔叔。

U存在且为红则变色继续往上处理U不存在或为黑则旋转加变色。

情况二和情况三的主要区别是单旋和双旋的不同。

从图中可以看出当p

cur

Node(kv);//新节点的默认颜色是红色因为如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整cur-_col

RED;if

parent-_parent;assert(grandfater);assert(grandfater-_col

BLACK);//

parent-_left){RotateR(grandfater);parent-_col

RED;}else{//

cRotateL(parent);RotateR(grandfater);cur-_col

RED;}break;}}else

parent-_right){RotateL(grandfater);parent-_col

RED;}else{//

cRotateR(parent);RotateL(grandfater);cur-_col

BLACK;return

红黑树的检测分为两步一、检测其是否满足二叉搜索树这里只需要中序遍历是否为有序序列即可。

二、检测其是否满足红黑树的性质。

public:bool

红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O(log2Nlog_2

Nlog2​N)红黑树不追求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红黑树更多。

红黑树的应用场景建议观看这个视频讲解红黑树在linux中的3种应用场景

八、红黑树模拟实现

Node(kv);//新节点的默认颜色是红色因为如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整cur-_col

RED;if

parent-_parent;assert(grandfater);assert(grandfater-_col

BLACK);//

parent-_left){RotateR(grandfater);parent-_col

RED;}else{//

cRotateL(parent);RotateR(grandfater);cur-_col

RED;}break;}}else

parent-_right){RotateL(grandfater);parent-_col

RED;}else{//

cRotateR(parent);RotateL(grandfater);cur-_col

BLACK;return

nullptr){return;}_InOrder(root-_left);cout

root-_kv.first

endl;_InOrder(root-_right);}void

RotateL(Node*