安基网 欢乐生肖 编程 软件学院 查看内容

漫画:5 分钟学会红黑树算法

2019-8-27 11:01| 投稿: |来自:


免责声明:本站系公益性非盈利IT技术普及网,本文由投稿者转载自互联网的公开文章,文末均已注明出处,其内容和图片版权归原网站或作者所有,文中所述不代表本站观点,若有无意侵权或转载不当之处请从网站右下角联系我们处理,谢谢合作!

摘要: 作者 | 阿广责编 | 伍杏玲下面为标准的二叉排序树:初始状态:其实想要搜索值为226的节点很简单,搜索动画过程如下:这样不行!这是个病!得治!红黑树就是一种平衡的二叉查找树,说他平衡的意思是他不会变成“瘸子 ...

作者 | 阿广

责编 | 伍杏玲

下面为标准的二叉排序树:

初始状态:

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

这样不行!

这是个病!

得治!

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

1. 节点是红色或者黑色

2. 根节点是黑色

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

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

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

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

(黑色的节点可忽略)

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

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

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

如下图所示:

先来看一下变色!

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

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

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

左旋转思想示意图如下:

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

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

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

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

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

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

一边是给予,一边是接受

一边是付出,一边是得到

一边是耕耘,一边是收获

一边是物质,一边是精神

阿广你年过二十而未立

置身于五光十色的世俗社会

我希望阿广都能铭记

一个古老但不失色彩的道理!

“活得简单才能活得自由”

因为舍得,所以淡泊

因为朴素,难以物役

所以保持精神和内在的富有

才是平衡的前提!

声明:本文系作者投稿,版权归作者所有。



小编推荐:欲学习电脑技术、系统维护、网络管理、编程开发和安全攻防等高端IT技术,请 点击这里 注册账号,公开课频道价值万元IT培训教程免费学,让您少走弯路、事半功倍,好工作升职加薪!

本文出自:https://www.toutiao.com/i6719312932947100164/

免责声明:本站系公益性非盈利IT技术普及网,本文由投稿者转载自互联网的公开文章,文末均已注明出处,其内容和图片版权归原网站或作者所有,文中所述不代表本站观点,若有无意侵权或转载不当之处请从网站右下角联系我们处理,谢谢合作!

相关阅读

最新评论

 最新
返回顶部
幸运赛车 幸运飞艇官网 彩宝彩票平台 欢乐生肖 三分快3 五分时时彩 三分快3 上海11选5计划 河北11选5走势图 欢乐生肖