如果不了解插入、删除原理请先阅读 红黑树。本例是我学习的时候载自网上的例子,并不是自己原创,我只是更详细的演示说明了插入、过程。
一、插入
插入结点: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
网友评论