红黑树概念
红黑树,是一种二叉搜索树,但在每个结点上增加一个存储位表示结点的颜色,可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制,红黑树确保没有一条路径会比其他路径长出俩倍,因而是接近平衡的。
红黑树的性质
- 最长路径做多是最短路径的2倍
- 每个结点不是红色就是黑色
- 根节点是黑色的
- 如果一个节点是红色的,则它的两个孩子结点是黑色的【没有2个连续的红色节点】
- 对于每个结点,从该结点到其所有后代叶结点的简单路径上,均 包含相同数目的黑色结点
- 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
红黑树节点的定义
class RBTreeNode{
RBTreeNode left = null;
RBTreeNode right = null;
RBTreeNode parent = null;
COLOR color = RED; // 节点的颜色
int val;
public RBTreeNode(int val){
this.val = val;
}
}
红黑树的插入
红黑树是在二叉搜索树的基础上加上其平衡限制条件,因此红黑树的插入可分为两步:
- 按照二叉搜索的树规则插入新节点
- 检测新节点插入后,红黑树的性质是否造到破坏
因为新节点的默认颜色是红色,因此:如果其双亲节点的颜色是黑色,没有违反红黑树任何性质,则不需要调整;但当新插入节点的双亲节点颜色为红色时,就违反了性质三不能有连在一起的红色节点,此时需要对红黑树分情况来讨论:
约定:cur为当前节点,p为父节点,g为祖父节点,u为叔叔节点
情况一: cur为红,p为红,g为黑,u存在且为红
cur和p均为红,违反了性质三,此处能否将p直接改为黑?
解决方式:将p,u改为黑,g改为红,然后把g当成cur,继续向上调整。
情况二: cur为红,p为红,g为黑,u不存在/u为黑
p为g的左孩子,cur为p的左孩子,则进行右单旋转;相反,
p为g的右孩子,cur为p的右孩子,则进行左单旋转
p、g变色–p变黑,g变红文章来源:https://www.toymoban.com/news/detail-602663.html
情况三: cur为红,p为红,g为黑,u不存在/u为黑
p为g的左孩子,cur为p的右孩子,则针对p做左单旋转;相反,
p为g的右孩子,cur为p的左孩子,则针对p做右单旋转
则转换成了情况2文章来源地址https://www.toymoban.com/news/detail-602663.html
public boolean insert(int val){
// ...
// 新节点插入后,如果parent节点的颜色是红色,一定违反性质三
while(null != parent && COLOR.RED == parent.color){
RBTreeNode grandFather = parent.parent;
if(parent == grandFather.left){
RBTreeNode uncle = grandFather.right;
if(null != uncle && uncle.color == COLOR.RED){
// 情况一:叔叔节点存在且为红,
// 解决方式:将叔叔和双亲节点改为黑色,祖父节点改为红色
// 如果祖父的双亲节点的颜色是红色,需要继续往上调整
parent.color = COLOR.BLACK;
uncle.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
cur = grandFather;
parent = cur.parent;
}else{
// 情况二和情况三
// 叔叔节点不存在 || 叔叔节点存在,但是颜色是黑色
if(cur == parent.right){
// 情况三
rotateLeft(parent);
RBTreeNode temp = parent;
parent = cur;
cur = temp;
}
// 情况二
rotateRight(grandFather);
parent.color = COLOR.BLACK;
grandFather.color = COLOR.RED;
}}else{
}
}
// 在上述循环更新期间,可能会将根节点给成红色而违反性质1,因此此处必须将根节点改为黑色
root.color = COLOR.BLACK;
return true;
}
到了这里,关于红黑树概念的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!