数据结构与算法(十二)红黑树

数据结构可视化学习网址:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

性质

1.每个结点不是红色就是黑色
2.每个叶子节点都是黑色的空节点(NIL),根结点都是黑色
3.不可能有相连的红色的结点。
4.每个结点到其可达叶子结点的所有路径,包含黑色结点的数量是一样的。
5.所有新加的点都是红色

变换

1.红变黑,黑变红
2.左旋
3.右旋

变换规则

插入的时候旋转和颜色变换规则:
1.变颜色的情况:当前结点的父亲是红色,且它的祖父结点的另一个子结点(叔叔结点)也是红色。:
(1)把父节点设为黑色
(2)把叔叔也设为黑色
(3)把祖父也就是父亲的父亲设为红色(爷爷)
(4)把指针定义到祖父结点(爷爷)设为当前要操作的.
2.左旋:当前父结点是红色,叔叔是黑色的时候,且当前的结点是右子树。左旋
以父结点作为左旋。指针变换到父亲结点
3.右旋:当前父结点是红色,叔叔是黑色的时候,且当前的结点是左子树。右旋
(1)把父结点变为黑色
(2)把祖父结点变为红色 (爷爷)
(3)以祖父结点旋转(爷爷)

图示

红黑树图解_00.png

#   红黑树 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×