江苏龙网

  1. 主页 > 生活百科 > >

彻底理解红黑树( 六 )

红黑树


文章插图
 
图28 删除情景2.2.2.3
综上，红黑树删除后自平衡的处理可以总结为：

  1. 自己能搞定的自消化（情景1）
  2. 自己不能搞定的叫兄弟帮忙（除了情景1、情景2.1.2.3和情景2.2.2.3）
  3. 兄弟都帮忙不了的，通过父母，找远方亲戚（情景2.1.2.3和情景2.2.2.3）
哈哈，是不是跟现实中很像，当我们有困难时，首先先自己解决，自己无力了总兄弟姐妹帮忙，如果连兄弟姐妹都帮不上，再去找远方的亲戚了 。这里记忆应该会好记点～
最后再做个习题加深理解（请不熟悉的同学务必动手画下）：
习题2：请画出图29的删除自平衡处理过程 。
彻底理解红黑树

文章插图
 
 
五、写在后面
耗时良久，终于写完了～自己加深了红黑树的理解的同时，也希望能帮助大家 。如果你之前没学习过红黑树，看完这篇文章后可能还存在很多疑问，如果有疑问可以在评论区写出来，我会尽自己所能解答 。另外给大家推荐一个支持红黑树在线生成的网站，来做各种情景梳理很有帮助：
在线生成红黑树
sandbox.runjs.cn/show/2nngvn8w
（删除操作那个把替代结点看作删除结点思路就是我自己在用这个网站时自己顿悟的，我觉得这样讲解更容易理解 。）
少了代码是不是觉得有点空虚？哈哈，后续我会写关于Java和HashMap和TreeMap的文章，里面都有红黑树相关的知识 。相信看了这篇文章后，再去看Java和HashMap和TreeMap的源码绝对没难度！
最后来看下思考题和习题的答案吧 。
六、思考题和习题答案
思考题1：黑结点可以同时包含一个红子结点和一个黑子结点吗？
答：可以 。如下图的F结点：
彻底理解红黑树

文章插图
 
习题1：请画出图15的插入自平衡处理过程 。
彻底理解红黑树

文章插图
 
习题2：请画出图29的删除自平衡处理过程 。
彻底理解红黑树

文章插图
 

【彻底理解红黑树】


推荐阅读


上一篇：申请商标要多少钱

下一篇：银行卡暂停非柜面交易怎么办