[分享]漫画算法:5分钟搞明白红黑树到底是什么?_Android, Python及开发编程讨论区_Weblogic技术|Tuxedo技术|中间件技术|Oracle论坛|JAVA论坛|Linux/Unix技术|hadoop论坛_联动北方技术论坛  
网站首页 | 关于我们 | 服务中心 | 经验交流 | 公司荣誉 | 成功案例 | 合作伙伴 | 联系我们 |
联动北方-国内领先的云技术服务提供商
»  游客             当前位置:  论坛首页 »  自由讨论区 »  Android, Python及开发编程讨论区 »
总帖数
1
每页帖数
101/1页1
返回列表
0
发起投票  发起投票 发新帖子
查看: 5511 | 回复: 0   主题: [分享]漫画算法:5分钟搞明白红黑树到底是什么?        上一篇   下一篇 
huang.wang
注册用户
等级:中将
经验:17623
发帖:407
精华:1
注册:1970-1-1
状态:离线
发送短消息息给huang.wang 加好友    发送短消息息给huang.wang 发消息
发表于: IP:您无权察看 2019-9-12 17:12:59 | [全部帖] [楼主帖] 楼主


本文转自公众号 视学算法


image.png

image.png

下面为标准的二叉排序树

image.png

初始状态

image.png

其实想要搜索值为226的节点很简单,搜索动画过程如下:

1.gif

image.png

image.png

这样不行!

这是个病!

得治!

image.png

红黑树就是一种平衡的二叉查找树,说他平衡的意思是他不会变成“瘸子”,左腿特别长或者右腿特别长。除了符合二叉查找树的特性之外,还具体下列的特性:

1. 节点是红色或者黑色

2. 根节点是黑色

3. 每个叶子的节点都是黑色的空节点(NULL)

4. 每个红色节点的两个子节点都是黑色的。

5. 从任意节点到其每个叶子的所有路径都包含相同的黑色节点。

下面为标准的红黑树,阿广建议大家对照下面的图理解上边写的红黑树的性质哦~


image.png

(黑色的NULL节点可忽略)

image.png

例如上面标准的红黑树,插入值为12的节点。

image.png

插入之后发现仍然满足红黑树的要求!

但是如果插入值为21的节点呢?

如下图所示

image.png

image.png

先来看一下变色!

为了符合红黑树的规则,会把节点红变黑或者黑变红。下图展示的是红黑树的部分,需要注意节点25并非根节点。因为21和22链接出现红色,不符合规则4,所以把22红变黑:

image.png

但这样还是不符合规则5,所以需要把25黑变红,看下图:

image.png

image.png

image.png

image.png

接下来先讲一下什么是左旋转!通过动画举个例子吧!

2.gif

33.gif

左旋转思想示意图如下

image.png

通俗点讲一下,可以看下面的左旋转静态示意图

image.png

按照左旋转,对上边已经变色完成之后图进行左旋转。

image.png

image.png

image.png

44.gif

55.gif

可见右旋转的思想总结如下:

image.png


通俗点讲一下,可以看下面的右旋转静态示意图

image.png

接下来,对上边经过左旋转之后的图进行右旋转。

image.png

image.png

image.png

image.png

人生像红黑树一样,总是需要某种平衡


一边是给予,一边是接受

一边是付出,一边是得到

一边是耕耘,一边是收获

一边是物质,一边是精神



我超级酷,但是如果你回复我的话我可以不酷那么一小会儿。


——来自logo.png


赞(0)    操作        顶端 
总帖数
1
每页帖数
101/1页1
返回列表
发新帖子
请输入验证码: 点击刷新验证码
您需要登录后才可以回帖 登录 | 注册
技术讨论