红黑树
2020-05-12 15:45:26 0 举报
红黑树
作者其他创作
大纲/内容
NIL
22
25
8
21
红黑树
左旋: 逆时针旋转,父节点被自己的右孩子取代,而自己成为自己的左孩子
向红黑树中插入14的节点,由于15是黑色节点,所以没有破坏结构,不需要做任何的改变
13
27
c
Y
X
15
1
17
a
6
右旋:顺时针旋转,父节点被做孩子取代,而自己成为自己的右孩子
b
11
如果向树中插入21的话,会破坏红黑树的规则,必须要调整,就是变色和旋转
红黑(Red-black)树 是一种自平衡二叉查找树,1972年由Rudolf Bayer发明,它与AVL树类似,都在插入和删除操作时能通过旋转操作保持二叉查找树的平衡,以便能获得高效的查找性能。它可以在 O(logn) 时间内做查找,插入和删除等操作。红黑树是2-3-4树的一种等同,但有些红黑树设定只能左边是红树,这种情况就是2-3树的一种等同了。对于AVL树来说,红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作,整体来说性能要优于AVL树。特点: 节点是红色或黑色。 根节点是黑色。 每个叶节点(NIL节点)是黑色的。 每个红色节点的两个子节点都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点) 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。 最长路径不超过最短路径的2倍
为了符合红黑树的规则,会把节点红变黑或者黑变红,21,22是连续的红色,因此要将22红变黑
此时还没有结束,因为25和27都出现了红色,因此需要将27变成黑色
基础知识补充
14
此时,不符合规则5,因此需要将25黑变红
0 条评论
回复 删除
下一页