红黑树双红修正
2019-07-25 10:14:11 1 举报
红黑树双红修正
作者其他创作
大纲/内容
对称情况
【三角型】
25
34
58
90
60
其它变形情况
59
49
父
100
RR-2父红叔红
插入80
86
插入59
双红修正 等价B树理解红黑树
102
23
85
2.左旋
80
(染黑父亲 58、叔叔 34,然后染红祖父 49,转化为 RR-1)
叔
插入87
等价2-3-4 树
101
插入95
2.右旋
修正之后
(染黑49)
B树上溢
例子2:
插入85
RR-2 父红叔红(插入到等价 B-树的四节点中)
插入90
递归深度1
nil
递归深度3
插入102
RR-1 父红叔黑
(染黑 101 的父亲 100、叔叔 86,然后染红祖父 90)
三角形转直线型再处理
插入101
操作相反
【直线型】
例子1:
右旋
RR-0父红叔黑
1.左旋
87
例子3:
95
LR
RR-1父红叔黑
1.右旋
左旋
(左旋 25,右旋 60,然后染红 60,染黑 49)
(先左旋父亲 86,再右旋祖父 100,最后染红 100,染黑 90)
0 条评论
下一页