美文网首页算法
红黑树插入删除过程

红黑树插入删除过程

作者: MangK | 来源:发表于2016-10-23 00:55 被阅读1332次

    如果不了解插入、删除原理请先阅读 红黑树。本例是我学习的时候载自网上的例子,并不是自己原创,我只是更详细的演示说明了插入、过程。

    一、插入

    插入结点: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

    相关文章

      网友评论

      • 摩登先生:插入20不太明白...应该是第二种情况才对呀,但是我用第二种情况又弄不出来.
      • 8fe8946fa366:有些图看不清啊
      • f76f9308d391:不错,根据前一篇对插入删除情况的总结,这篇再从案例一步一步分析,图文并茂,另外这个画图工具是什么啊:kissing_closed_eyes:
        f76f9308d391:@MangK 感谢:kissing_heart:
        MangK:@淡淡的时候 OmniGraffle 网上有破解的

      本文标题:红黑树插入删除过程

      本文链接:https://www.haomeiwen.com/subject/zwshuttx.html