红黑树插入删除过程
2016-10-23 本文已影响1332人
MangK
如果不了解插入、删除原理请先阅读 红黑树。本例是我学习的时候载自网上的例子，并不是自己原创，我只是更详细的演示说明了插入、过程。
一、插入
插入结点：12、1、9、2、0、11、7、19、4、15、18、5、14、13、10、16、6、3、8、17 全程演示
1.插入结点12
1.插入结点12
2.插入结点1
2.插入结点1
3.插入结点9（左-情况2）
3.插入结点9（左-情况2）
4.插入结点2（左-情况1）
4.插入结点2（左-情况1）
5.插入结点0
5.插入结点0
6.插入结点11
6.插入结点11
7.插入结点7（右-情况1）
7.插入结点7（右-情况1）
8.插入结点19
8.插入结点19
9.插入结点4（右-情况2）
9.插入结点4（右-情况2）
10.插入结点15（右-情况1）
10.插入结点15（右-情况1）
11.插入结点18（左-情况2）
11.插入结点18（左-情况2）
12.插入结点5（右-情况1）
12.插入结点5（右-情况1）
13.插入结点14（左-情况1）
13.插入结点14（左-情况1）
14.插入结点13（左-情况3）
14.插入结点13（左-情况3）
15.插入结点10
15.插入结点10
16.插入结点16（右-情况1）
16-1.插入结点16（右-情况1）
16-2.插入结点16（右-情况1）
17.插入结点6（左-情况2）
17.插入结点6（左-情况2）
18.插入结点3（左-情况2）
18.插入结点3（左-情况2）
19.插入结点8（右-情况1）
19.插入结点8（右-情况1）
20.插入结点17（右-情况3）
20.插入结点17（右-情况3）
二、删除
删除结点：12、1、9、2、0、11、7、19、4、15、18、5、14、13、10、16、6、3、8、17 全程演示
1.删除结点12（右-情况4），实际上删除的是结点13所在位置，之后将结点13赋值给结点12所在位置即可
1.删除结点12（右-情况4）
2.删除结点1（左-情况4），实际上删除的是结点0所在位置，之后将结点0赋值给结点1所在位置即可
2.删除结点1（左-情况4）
3.删除结点9（左-情况2），实际上删除的是结点10所在位置，之后将结点10赋值给结点9所在位置即可
3.删除结点9（左-情况2）
4.删除结点2（左-情况2），实际上删除的是结点3所在位置，之后将结点3赋值给结点2所在位置即可
4.删除结点2（左-情况2）
5.删除结点0，删除红色结点，无影响
5.删除结点0
6.删除结点11，实际上删除的是结点13所在位置，之后将结点13赋值给结点11所在位置即可，由于结点13为红色，无影响
6.删除结点11
7.删除结点7，实际上删除的是结点8所在位置，之后将结点8赋值给结点7所在位置即可，由于结点8为红色，无影响
7.删除结点7
8.删除结点19（右-情况4）
8.删除结点19（右-情况4）
9.删除结点4（左-情况2），实际上删除的是结点5所在位置，之后将结点5赋值给结点4所在位置即可
9.删除结点4（左-情况2）
10.删除结点15（左-情况3）
10.删除结点15（左-情况3）
11.删除结点18（右-情况2）
11.删除结点18（右-情况2）
12.删除结点5（左-情况4），实际上删除的是结点3所在位置，之后将结点3赋值给结点5所在位置即可
12.删除结点5（左-情况4）
13.删除结点14（左-情况3），实际上删除的是结点13所在位置，之后将结点13赋值给结点14所在位置即可
13.删除结点14（左-情况3）
14.删除结点13（左-情况2）
14.删除结点13（左-情况2）
15.删除结点10，实际上删除的是结点16所在位置，之后将结点16赋值给结点10所在位置即可
15.删除结点10
16.删除结点16（右-情况1），实际上删除的是结点17所在位置，之后将结点17赋值给结点16所在位置即可
16.删除结点16（右-情况1）
17.删除结点6，实际上删除的是结点8所在位置，之后将结点8赋值给结点6所在位置即可，由于结点8为红色，无影响
17.删除结点6
18.删除结点3（左-情况2）
18.删除结点3（左-情况2）
19.删除结点8
19.删除结点8
20.删除结点17
20.删除结点17
