红黑树，超强动静图详解，简单易懂

Scorpion 发布于2019-08-19 11:48 / 2574人阅读

摘要：写在前面红黑树，对很多童鞋来说，是既熟悉又陌生。每次需要查看红黑树内容时都很难以更生动形象的方式来理解其内容。

写在前面

红黑树，对很多童鞋来说，是既熟悉又陌生。学校中学过，只了解大概；工作中不怎么使用，但面试又是重点。每次需要查看红黑树内容时都很难以更生动形象的方式来理解其内容。没错，本文内容就是要解决这个问题，用简单的语言，搭配静图和动图(利用大脑图形记忆方式)，让你对红黑树有更深入的了解和更清晰的记忆，希望小伙伴们再次遇到红黑树的问题不至于头大，建议读该文章姿势: 打开两个页面，一个页面看图片和内容，一个页面看公式，像玩魔方一样，多玩几次就明白了

通过工具 (公众号回复「工具」—>那些可以提高效率的工具—>红黑树) 动态感受红黑树的转换过程

俺家司令买完东西后，我俩经常会发生这样的一段对话:

司令:你猜我买的这个多少钱？
我: 1000
司令: 高了
我: 500
司令: 低了:
我: 750
...... 直到最后猜中

这样说大家应该已经猜到了是「二分查找法」，通过这个例子我想要引出的是树，来看图片

程序中的树其实是我们日常看到的树的倒影，或者发挥一下想象，倒影也可以是树根

二叉查找树

二叉查找树，Binary Search Tree 「BST」，要想了解二叉查找树，我们首先看下二叉查找树有哪些特性呢？

某节点的左子树节点值仅包含小于该节点值

某节点的右子树节点值仅包含大于该节点值

左右子树每个也必须是二叉查找树

看个图就轻松理解上面三句话的意思了:

上图，结合二叉查找树的三条约束来看，非常好，没有什么问题。再来看一个图，依旧符合上面三条约束，感觉有问题吗？

这是一个走路一米六，一米八的树

这是一个畸形的树，大风一挂很可能被折断的树

从程序的角度来说这个树不够平衡，查找次数或时间复杂度 O(h)可能会随着一条腿长无限增长

理科生在高中学习生物时学过一个关键字「去除顶端优势」，通过去除植物顶端优势，侧芽会迅速生长，慢慢变得强壮和平衡， 红黑树其实就是去除二叉查找树顶端优势的解决方案，从而达到树的平衡

红黑树

红黑树，Red-Black Tree 「RBT」是一个自平衡(不是绝对的平衡)的二叉查找树(BST)，树上的每个节点都遵循下面的规则:

每个节点都有红色或黑色

树的根始终是黑色的 (黑土地孕育黑树根，

混合云私有云红黑树 python 红黑树 linux 红黑树 linux红黑树代码

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77911.html

@ConfigurationProperties 注解使用姿势，这一篇就够了

摘要：在项目中，为满足以上要求，我们将大量的参数配置在或文件中，通过注解，我们可以方便的获取这些参数值使用配置模块假设我们正在搭建一个发送邮件的模块。这使得在不影响其他模块的情况下重构一个模块中的属性变得容易。在编写项目代码时，我们要求更灵活的配置，更好的模块化整合。在 Spring Boot 项目中，为满足以上要求，我们将大量的参数配置在 application.properties 或...

SolomonXie 2019-08-19 11:48 评论0 收藏0
@ConfigurationProperties 注解使用姿势，这一篇就够了

摘要：在项目中，为满足以上要求，我们将大量的参数配置在或文件中，通过注解，我们可以方便的获取这些参数值使用配置模块假设我们正在搭建一个发送邮件的模块。这使得在不影响其他模块的情况下重构一个模块中的属性变得容易。在编写项目代码时，我们要求更灵活的配置，更好的模块化整合。在 Spring Boot 项目中，为满足以上要求，我们将大量的参数配置在 application.properties 或...

KoreyLee 2019-08-19 10:13 评论0 收藏0
SegmentFault 技术周刊 Vol.31 - 码农也要学算法

摘要：记作称为算法的渐进时间复杂度，简称时间复杂度。学习数据结构与算法之链表链表一种常见的数据结构，可以存储有序的元素集合。首先在大的分类上，它们都是散列算法。 showImg(https://segmentfault.com/img/bVSDvj?w=900&h=385); 当人工智能、AlphaGo、无人驾驶、智能投顾等词语不断在人们视野中出现的时候，意味着我们正步入一个算法的时代。计算...

cgspine 2019-06-26 15:45 评论0 收藏0
数据结构 - 收藏集 - 掘金

面试旧敌之红黑树（直白介绍深入理解） - Android - 掘金读完本文你将了解到：什么是红黑树黑色高度红黑树的 5 个特性红黑树的左旋右旋指定节点 x 的左旋右图转成左图指定节点 y 的右旋左图转成右图红黑树的平衡插入二叉查找树的插入插入后调整红黑树结构调整思想插入染红后... java 多线程同步以及线程间通信详解 & 消费者生产者模式 & 死锁 & Thread...

leeon 2019-08-16 10:32 评论0 收藏0
红黑树的插入

摘要：算法导论由于性质，红黑树中不会出现两个红色结点相邻的情形。红黑树的插入首先以二叉搜索树的方式插入结点，并将其着为红色。假设整棵二叉搜索树中，只有和因违背性质而无法成为正常的红黑树，此时将图调整成图，则可以恢复成正常的红黑树。红黑树的性质一棵满足以下性质的二叉搜索树是一棵红黑树每个结点或是黑色或是红色。根结点是黑色的。每个叶结点(NIL)是黑色的。如果一个结点是红色的，则它...

sunsmell 2019-08-21 17:43 评论0 收藏0