设为首页收藏本站

中原工学院论坛

 找回密码
 立即注册

扫一扫,访问微社区

QQ登录

只需一步,快速开始

查看: 143|回复: 1

[分享] 漫画:什么是红黑树?

[复制链接]

271

主题

1448

帖子

1306

积分

管理员

Rank: 125Rank: 125Rank: 125Rank: 125Rank: 125

积分
1306

新人进步奖

发表于 2018-10-16 17:05:01 | 显示全部楼层 |阅读模式

马上注册,享用更多功能!灵感论坛,推动创造力的社区。

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
                                                                                                   

61ebe89228b3689ce577192f29cf62fc.jpg



3d994efc56a90674ab4b3055b98e2ddb.jpg



9043ebbac55a50e6feccc05ee613167e.jpg



4de0fb2d504e9fe8710c583843d566a8.jpg


————————————



9e1c64d4d22a4ac5b9c2dffcfca274ff.jpg



0d25b8be898464474898b7a738789370.jpg



ce2eb05cabd1136cdfac622e9e5639dd.jpg



49d10b86cff0da262eeaa0fa6b8329c6.jpg




afa58a455a8bdb92fa64abf1c5f3f72e.jpg



b4e0018200d880dc6a46c3b782982419.jpg



1cb9c3ccd90d32a8f0e1594bacfe8b90.jpg



a3b33f729fc730c74ffc642b46ea5255.jpg


————————————






e542dbe52471be6c9fa7022f3153148b.jpg




5f2f3da670a714faf26e7fa1ab671333.jpg



390e2c76e378e24b77ac22746cf430f1.jpg


二叉查找树(BST)具备什么特性呢?

1.子树上所有结点的值均小于或等于它的根结点的值。
2.子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。


下图中这棵树,就是一颗典型的二叉查找树:




c98f809e67e74f2ed999a40bd2870cd7.png



dd4b5cc63f66ebbc1b70beada6953342.jpg


1.查看根节点9


132f8e52b8c86c4137a4fd35a5c8f22a.jpg


2.由于10 > 9,因此查看右孩子13


9c10c57fdd92416ce48e3b7c27b35fc8.jpg


3.由于10 < 13,因此查看左孩子11


88d901991a36293a3515e5763dd2172c.jpg


4.由于10 < 11,因此查看左孩子10,发现10正是要查找的节点:


837ffc3832e381ef2c502d1aefa5859d.jpg



84180c61a8489f79cb9fa77ac7e62f68.jpg



714df827cf56fa87271f02004d8752cd.jpg



a9c03474625f5343f69d7f088958a0f5.jpg



01d800dc92b1919afadbf5e7920cea85.jpg



d737c91510b32cb10e4d947c93519b8d.jpg



8cfd014215e20a83852eb023017e1cfc.jpg


假设初始的二叉查找树只有三个节点,根节点值为9,左孩子值为8,右孩子值为12:


0f7b2740d4d2fba59f9ca3d414fd81f7.png


接下来我们依次插入如下五个节点:7,6,5,4,3。依照二叉查找树的特性,结果会变成什么样呢?




c8f8d4b16f492be685a7833283c8c9f1.png




03e3490c01f1a13129564e8d2a610cf2.jpg



01c68628f6fa5b1b76174efe933f1228.jpg



add7b8b95b29f3f875e2716e4d343648.jpg



de3400992f1e47a0201a111f50356467.jpg


1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点(NIL节点)。
4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

下图中这棵树,就是一颗典型的红黑树:


4a0b4ea817cc904be02d121117b586bb.jpg




4a4d499779f32ca822550972ac5bdaca.jpg



8067b2d8a43daba6962f78cf4053c29c.jpg



aa2c407ee303d5b2a6bbd55bd73834e8.jpg


什么情况下会破坏红黑树的规则,什么情况下不会破坏规则呢?我们举两个简单的栗子:

1.向原红黑树插入值为14的新节点:




623c755e43a0f1d9a968b5dc068c61d5.jpg


由于父节点15是黑色节点,因此这种情况并不会破坏红黑树的规则,无需做任何调整。





2.向原红黑树插入值为21的新节点:


885f8e4269fff1c98a6e65221b96f02b.jpg



由于父节点22是红色节点,因此这种情况打破了红黑树的规则4(每个红色节点的两个子节点都是黑色),必须进行调整,使之重新符合红黑树的规则。





d65f19c78559e919ce5cb0db476543ee.jpg



04eb7174e7de60ff11b91e4b8f3315e4.jpg


变色:
为了重新符合红黑树的规则,尝试把红色节点变为黑色,或者把黑色节点变为红色。

下图所表示的是红黑树的一部分,需要注意节点25并非根节点。因为节点21和节点22连续出现了红色,不符合规则4,所以把节点22从红色变成黑色:


5eafd9d9d9941ba4fde1e4262487a65f.png



但这样并不算完,因为凭空多出的黑色节点打破了规则5,所以发生连锁反应,需要继续把节点25从黑色变成红色:


5f583ea59054a075bfc98d1baa976723.jpg


此时仍然没有结束,因为节点25和节点27又形成了两个连续的红色节点,需要继续把节点27从红色变成黑色:


23f0aaee53a7b0d98200ec7dcdc7866e.png



左旋转:

逆时针旋转红黑树的两个节点,使得父节点被自己的右孩子取代,而自己成为自己的左孩子。说起来很怪异,大家看下图:


cf56d829055b4bc0fa150b568bec28a3.png

图中,身为右孩子的Y取代了X的位置,而X变成了自己的左孩子。此为左旋转。


右旋转:

顺时针旋转红黑树的两个节点,使得父节点被自己的左孩子取代,而自己成为自己的右孩子。大家看下图:


b20526f816637ffb831b262a32e8e9f8.png


图中,身为左孩子的Y取代了X的位置,而X变成了自己的右孩子。此为右旋转。



2cc09ec122312dd837fce8b593540ea7.jpg



2e7635924fb534857cf12ea10aafad2e.jpg


我们以刚才插入节点21的情况为例:



885f8e4269fff1c98a6e65221b96f02b.jpg


首先,我们需要做的是变色,把节点25及其下方的节点变色:


39aa1119fb2028d6f9799d384319905c.jpg



此时节点17和节点25是连续的两个红色节点,那么把节点17变成黑色节点?恐怕不合适。这样一来不但打破了规则4,而且根据规则2(根节点是黑色),也不可能把节点13变成红色节点。

变色已无法解决问题,我们把节点13看做X,把节点17看做Y,像刚才的示意图那样进行左旋转


cf56d829055b4bc0fa150b568bec28a3.png



b3c49f493ed046191e5bfad94d1e8278.jpg



1451de410d855cd9c8578ee93733f4bc.jpg


由于根节点必须是黑色节点,所以需要变色,变色结果如下:


9e87e0fdf558be0d70463efaee7b4147.jpg


这样就结束了吗?并没有。因为其中两条路径(17 -> 8 -> 6 -> NIL)的黑色节点个数是4,其他路径的黑色节点个数是3,不符合规则5。

这时候我们需要把节点13看做X,节点8看做Y,像刚才的示意图那样进行右旋转
b20526f816637ffb831b262a32e8e9f8.png







3dc06bcdb6b8149425564774de5ef529.jpg



1318d3fa72504ed31ad7117f990dd3f5.jpg


最后根据规则来进行变色



7fb74cb66b3a1e754f355dc4af64bc6b.jpg


如此一来,我们的红黑树变得重新符合规则。这一个例子的调整过程比较复杂,经历了如下步骤:

变色 -> 左旋转 -> 变色 -> 右旋转 -> 变色



1b4347e6d883baae1e048bcabadd9663.jpg



5ff15f5fae71f68350acfd08906c55c4.jpg



5952feac88543ee99a7dec979dffd952.jpg



fa723cf08956eb6d7c6775ad50dc20a0.jpg


几点说明:

1. 关于红黑树自平衡的调整,插入和删除节点的时候都涉及到很多种Case,由于篇幅原因无法展开来一一列举,有兴趣的朋友可以参考维基百科,里面讲的非常清晰。

2.漫画中红黑树调整过程的示例是一种比较复杂的情形,没太看明白的小伙伴也不必钻牛角尖,关键要懂得红黑树自平衡调整的主体思想。



—————END—————



               
life style

7

主题

21

帖子

60

积分

注册会员

Rank: 6Rank: 6

积分
60
发表于 2018-10-21 08:28:58 | 显示全部楼层
呦呦资源论坛开放注册了!!限时开放注册

92xll.com
*滑动验证:
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

QQ|小黑屋|手机版|Archiver|中原工学院论坛 ( 豫ICP备11003946号 ) 百度统计

GMT+8, 2018-11-17 19:03 , Processed in 0.090059 second(s), 34 queries .

© 2010-2017 中原工学院团委 | 中工灵感论坛

请将您的想法告诉我们,帮助我们改进服务 请将您的想法告诉我们,帮助我们改进服务

快速回复 返回顶部 返回列表