红黑树双红修正
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 条评论
回复 删除
下一页
