数据结构与算法之美
王争
前Google工程师
立即订阅
71638 人已学习
课程目录
已完结 75 讲
0/4登录后,你可以任选4讲全文学习。
开篇词 (1讲)
开篇词 | 从今天起,跨过“数据结构与算法”这道坎
免费
入门篇 (4讲)
01 | 为什么要学习数据结构和算法?
02 | 如何抓住重点,系统高效地学习数据结构与算法?
03 | 复杂度分析(上):如何分析、统计算法的执行效率和资源消耗?
04 | 复杂度分析(下):浅析最好、最坏、平均、均摊时间复杂度
基础篇 (38讲)
05 | 数组:为什么很多编程语言中数组都从0开始编号?
06 | 链表(上):如何实现LRU缓存淘汰算法?
07 | 链表(下):如何轻松写出正确的链表代码?
08 | 栈:如何实现浏览器的前进和后退功能?
09 | 队列:队列在线程池等有限资源池中的应用
10 | 递归:如何用三行代码找到“最终推荐人”?
11 | 排序(上):为什么插入排序比冒泡排序更受欢迎?
12 | 排序(下):如何用快排思想在O(n)内查找第K大元素?
13 | 线性排序:如何根据年龄给100万用户数据排序?
14 | 排序优化:如何实现一个通用的、高性能的排序函数?
15 | 二分查找(上):如何用最省内存的方式实现快速查找功能?
16 | 二分查找(下):如何快速定位IP对应的省份地址?
17 | 跳表:为什么Redis一定要用跳表来实现有序集合?
18 | 散列表(上):Word文档中的单词拼写检查功能是如何实现的?
19 | 散列表(中):如何打造一个工业级水平的散列表?
20 | 散列表(下):为什么散列表和链表经常会一起使用?
21 | 哈希算法(上):如何防止数据库中的用户信息被脱库?
22 | 哈希算法(下):哈希算法在分布式系统中有哪些应用?
23 | 二叉树基础(上):什么样的二叉树适合用数组来存储?
24 | 二叉树基础(下):有了如此高效的散列表,为什么还需要二叉树?
25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?
26 | 红黑树(下):掌握这些技巧,你也可以实现一个红黑树
27 | 递归树:如何借助树来求解递归算法的时间复杂度?
28 | 堆和堆排序:为什么说堆排序没有快速排序快?
29 | 堆的应用:如何快速获取到Top 10最热门的搜索关键词?
30 | 图的表示:如何存储微博、微信等社交网络中的好友关系?
31 | 深度和广度优先搜索:如何找出社交网络中的三度好友关系?
32 | 字符串匹配基础(上):如何借助哈希算法实现高效字符串匹配?
33 | 字符串匹配基础(中):如何实现文本编辑器中的查找功能?
34 | 字符串匹配基础(下):如何借助BM算法轻松理解KMP算法?
35 | Trie树:如何实现搜索引擎的搜索关键词提示功能?
36 | AC自动机:如何用多模式串匹配实现敏感词过滤功能?
37 | 贪心算法:如何用贪心算法实现Huffman压缩编码?
38 | 分治算法:谈一谈大规模计算框架MapReduce中的分治思想
39 | 回溯算法:从电影《蝴蝶效应》中学习回溯算法的核心思想
40 | 初识动态规划:如何巧妙解决“双十一”购物时的凑单问题?
41 | 动态规划理论:一篇文章带你彻底搞懂最优子结构、无后效性和重复子问题
42 | 动态规划实战:如何实现搜索引擎中的拼写纠错功能?
高级篇 (9讲)
43 | 拓扑排序:如何确定代码源文件的编译依赖关系?
44 | 最短路径:地图软件是如何计算出最优出行路径的?
45 | 位图:如何实现网页爬虫中的URL去重功能?
46 | 概率统计:如何利用朴素贝叶斯算法过滤垃圾短信?
47 | 向量空间:如何实现一个简单的音乐推荐系统?
48 | B+树:MySQL数据库索引是如何实现的?
49 | 搜索:如何用A*搜索算法实现游戏中的寻路功能?
50 | 索引:如何在海量数据中快速查找某个数据?
51 | 并行算法:如何利用并行处理提高算法的执行效率?
实战篇 (5讲)
52 | 算法实战(一):剖析Redis常用数据类型对应的数据结构
53 | 算法实战(二):剖析搜索引擎背后的经典数据结构和算法
54 | 算法实战(三):剖析高性能队列Disruptor背后的数据结构和算法
55 | 算法实战(四):剖析微服务接口鉴权限流背后的数据结构和算法
56 | 算法实战(五):如何用学过的数据结构和算法实现一个短网址系统?
加餐:不定期福利 (6讲)
不定期福利第一期 | 数据结构与算法学习书单
不定期福利第二期 | 王争:羁绊前行的,不是肆虐的狂风,而是内心的迷茫
不定期福利第三期 | 测一测你的算法阶段学习成果
不定期福利第四期 | 刘超:我是怎么学习《数据结构与算法之美》的?
总结课 | 在实际开发中,如何权衡选择使用哪种数据结构和算法?
《数据结构与算法之美》学习指导手册
加餐:春节7天练 (7讲)
春节7天练 | Day 1:数组和链表
春节7天练 | Day 2:栈、队列和递归
春节7天练 | Day 3:排序和二分查找
春节7天练 | Day 4:散列表和字符串
春节7天练 | Day 5:二叉树和堆
春节7天练 | Day 6:图
春节7天练 | Day 7:贪心、分治、回溯和动态规划
加餐:用户学习故事 (2讲)
用户故事 | Jerry银银:这一年我的脑海里只有算法
用户故事 | zixuan:站在思维的高处,才有足够的视野和能力欣赏“美”
结束语 (3讲)
结束语 | 送君千里,终须一别
第2季回归 | 这一次,我们一起拿下设计模式!
打卡召集令 | 60 天攻克数据结构与算法
免费
数据结构与算法之美
登录|注册

25 | 红黑树(上):为什么工程中都用红黑树这种二叉树?

王争 2018-11-16
上两节,我们依次讲了树、二叉树、二叉查找树。二叉查找树是最常用的一种二叉树,它支持快速插入、删除、查找操作,各个操作的时间复杂度跟树的高度成正比,理想情况下,时间复杂度是 O(logn)。
不过,二叉查找树在频繁的动态更新过程中,可能会出现树的高度远大于 log2n 的情况,从而导致各个操作的效率下降。极端情况下,二叉树会退化为链表,时间复杂度会退化到 O(n)。我上一节说了,要解决这个复杂度退化的问题,我们需要设计一种平衡二叉查找树,也就是今天要讲的这种数据结构。
很多书籍里,但凡讲到平衡二叉查找树,就会拿红黑树作为例子。不仅如此,如果你有一定的开发经验,你会发现,在工程中,很多用到平衡二叉查找树的地方都会用红黑树。你有没有想过,为什么工程中都喜欢用红黑树,而不是其他平衡二叉查找树呢?
带着这个问题,让我们一起来学习今天的内容吧!

什么是“平衡二叉查找树”?

平衡二叉树的严格定义是这样的:二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看,上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树,但是非完全二叉树也有可能是平衡二叉树。
平衡二叉查找树不仅满足上面平衡二叉树的定义,还满足二叉查找树的特点。最先被发明的平衡二叉查找树是AVL 树,它严格符合我刚讲到的平衡二叉查找树的定义,即任何节点的左右子树高度相差不超过 1,是一种高度平衡的二叉查找树。
取消
完成
0/1000字
划线
笔记
复制
© 版权归极客邦科技所有,未经许可不得传播售卖。 页面已增加防盗追踪,如有侵权极客邦将依法追究其法律责任。
该试读文章来自付费专栏《数据结构与算法之美》,如需阅读全部文章,
请订阅文章所属专栏。
立即订阅
登录 后留言

精选留言(84)

  • 🐱您的好友William🐱
    老师做图的软件用的是什么啊?我看了不少的极客时间的blog,感觉老师这个是最好看的哈哈。
    2018-11-16
    4
    150
  • kakasi
    散列表:插入删除查找都是O(1), 是最常用的,但其缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于那些不需要顺序遍历,数据更新不那么频繁的。

    跳表:插入删除查找都是O(logn), 并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的,其顺序遍历和区间查找非常方便。

    红黑树:插入删除查找都是O(logn), 中序遍历即是顺序遍历,稳定。缺点是难以实现,去查找不方便。其实跳表更佳,但红黑树已经用于很多地方了。
    2018-12-02
    10
    123
  • Smallfly
    动态数据结构的动态是什么意思?

    动态是指在运行时该数据结构所占的内存会扩大或缩小。

    数组是一种静态的数据结构,在创建时内存大小已经确定,不管有没有插入数据。而链表是动态的数据结构,插入数据 alloc 内存,删除数据 release 内存。

    栈、队列、散列表、跳表、树都是抽象的数据结构,它们在内存中存在的形式都要依赖于数组或者链表。

    如果用链表实现,很明显它们是动态的数据结构;如果用数组实现,那么在扩容的时候会创建更大内存的数组,原数组被废弃,从抽象角度看,它们仍旧是动态的。

    作者回复: 我看smallfly大牛好像对动态数据结构有些误解,可能其他同学也会有。所以,我解释一下:动态数据结构是支持动态的更新操作,里面存储的数据是时刻在变化的,通俗一点讲,它不仅仅支持查询,还支持删除、插入数据。而且,这些操作都非常高效。如果不高效,也就算不上是有效的动态数据结构了。所以,这里的红黑树算一个,支持动态的插入、删除、查找,而且效率都很高。链表、队列、栈实际上算不上,因为操作非常有限,查询效率不高。那现在你再想一下还有哪些支持动态插入、删除、查找数据并且效率都很高的的数据结构呢??

    2018-11-16
    3
    83
  • 王争
    我看smallfly大牛好像对动态数据结构有些误解,可能其他同学也会有。所以,我解释一下:动态数据结构是支持动态的更新操作,里面存储的数据是时刻在变化的,通俗一点讲,它不仅仅支持查询,还支持删除、插入数据。而且,这些操作都非常高效。如果不高效,也就算不上是有效的动态数据结构了。所以,这里的红黑树算一个,支持动态的插入、删除、查找,而且效率都很高。链表、队列、栈实际上算不上,因为操作非常有限,查询效率不高。那现在你再想一下还有哪些支持动态插入、删除、查找数据并且效率都很高的的数据结构呢??
    2018-11-16
    65
  • allan
    看了这篇文章还是有很多疑惑,主要是 不理解红黑树满足的几个性质,为什么要那样要求?
    2018-12-02
    1
    53
  • fy
    老师,可以教我们刷下leetcode上的算法,毕竟讲了这么多,还是练习的。这样的提升才有巨大的帮助
    2018-11-18
    41
  • 蜗牛行天下
    我觉得红黑树对于我们初学者来说最大的疑惑是,红黑节点有什么区别,是怎么演化来的?老师讲的很好,但是这个问题并没有在文中解决,所以不能深刻地理解红黑树的存在价值。我找到一篇文章,在这方面讲的很清楚,可以作为这篇讲义的补充:https://www.cnblogs.com/tiancai/p/9072813.html
    2019-01-31
    6
    32
  • 失火的夏天
    动态数据结构有链表,栈,队列,哈希表等等。链表适合遍历的场景,插入和删除操作方便,栈和队列可以算一种特殊的链表,分别适用先进后出和先进先出的场景。哈希表适合插入和删除比较少(尽量少的扩容和缩容),查找比较多的时候。红黑树对数据要求有序,对数据增删查都有一定要求的时候。(个人看法,欢迎老师指正)

    作者回复: 👍 刚看错了。写的不错

    2018-11-16
    21
  • 不似旧日
    没明白红节点与黑节点的存在意义
    2019-01-03
    11
  • null
    红黑树的节点颜色,是如何确定的,如何知道在新增一个节点时,该节点是什么颜色?

    从红黑树需要满足的四个要求来看:
    1. 根节点为黑色
    2. 所有叶子节点为黑色,且不存储数据
    3. 相邻两个节点不能都为红色
    4. 从某节点到其所有叶子节点的路径中,黑色节点数相同

    从这四点要求,好像我一根树全是黑色,也是满足其定义的。这里用红黑两色区分各节点,意义是啥?

    谢谢老师

    作者回复: 新插入的节点都是红色的。全黑不可能的。红黑区分的意义你等下一节课看看能懂不

    2018-11-16
    10
  • 朱月俊
    动态数据结构比如本篇的平衡二叉查找树,还有就是跳表,跳表也支持动态插入,删除,查询,也很快,不同点是跳表还能支持快速的范围查询。比如leveldb中的memtable,redis都是使用跳表实现的,而也有用红黑树实现的memtable。
    除此之外,跳表还支持多写多读,而红黑树不可以,这些场景下显然用跳表合适。
    2018-11-17
    7
  • 有铭
    我除了看懂红黑树是一种“性能上比较均衡”的二叉树这个结论外,完全没搞懂它为啥能获得这个“比较平衡”的结果
    2018-11-16
    7
  • S.S Mr Lin
    很多讲红黑树的地方都没讲2-3-4树,其实如果看懂了2-3-4树,再来看红黑树就特别好理解了。我一般会问别人,红黑树的黑节点代表了什么?如果理解了,就会知道黑节点代表了近似平衡高度,所有黑节点的定义都是为了保证这一点。
    2019-03-22
    5
  • !null
    没太看懂去掉红色节点生成全黑四叉树,又把红色节点加进去的目的是什么?感觉不懂这个整个红黑树就没学懂。
    2018-11-21
    4
  • wean
    “我们从四叉树中取出某些节点,放到叶节点位置,四叉树就变成了完全二叉树”

    老师,这里的某些节点应该怎么取,才能让四叉树变成二叉树,不是很明白,希望老师讲解一下,谢谢
    2018-11-16
    4
  • 不能如期而至
    **基本数据结构:**

    1.数组:连续的内存空间,支持按下标随机访问O(1),删除和查找设计数据搬移效率是O(n) 试用场景:数据规模较小,不经常变动。

    缺点:对于内存连续性要求高。插入删除操作效率低。

    2.链表:查询效率不高O(n),插入和删除效率高O(1),并且内存申请可以不连续,适用场景是插入和删除多于查询操作。

    缺点:查找效率低,实际上删除之前先要查找,所以实际删除效率也不高。

    **动态数据结构:**

    1.散列表:可以说是利用数组和链表两个基本数据结构设计了一个高效的动态数据结构。利用了数组的随机访问特性,用于满足根据某个属性来随机访问元素。基于key查找效率很高O(1).同时借助链表进行散列冲突解决方案,删除和插入操作效率也可以接近O(1).试用场景:海量数据随机访问、防止重复、缓存等。

    缺点:需要设计合理的散列函数,并且要考虑散列冲突和动态扩容。

    2.跳表:尽管散列表效率很高,但是散列表是无序的,跳表效率和散列表类似,并且支持区间序列的输出(因为基于链表)。使用场景:对有序元素的快速查找、插入和删除。

    缺点:比较占用内存。

    3.红黑树:红黑树是平衡二叉查找树的一种近似实现。红黑树和跳表类似,但是实现方式有所差异。红黑树存在的价值是,它可以实现比较高效的查找,删除和插入。虽然相比高度平衡的AVL树效率有所下降,但是红黑树不用耗费太多精力维护平衡。相比跳表,红黑树除了内存占用较小,其他性能并不比跳表更优。但由于历史原因,红黑树使用的更广泛。

    缺点:实现比较复杂。
    2019-11-12
    3
  • 建强
    动态数据结构还包括以下几种:
    1.链表:
    优势:高效地数据插入、删除。
    缺点:随机查找元素效率较低。
    适用场景:适用于顺序访问数据,数据维护较频繁的场合。

    2.哈希链表
    优势:高效地数据插入、删除、随机查找元素。
    缺点:需要设计一个好的散列函数,把元素均匀分散到散列表中。
    适用场景:适用于在海量数据中随机访问数据的场合。

    3.跳表
    优势:高效地查找、插入、删除数据。
    缺点:需要额外的空间来构建索引链表
    适用场景:适用于需要高效查找数据的场合。

    4.二叉查找树
    优势:高效地查找、插入、删除数据,实现简单。
    缺点:需要动态地维护左右子树的高度平衡,否则数据查找会退化成链表的顺序查找。
    适用场景:适用于需要高效查找数据的场合。
    2019-07-07
    3
  • increasingly
    请问什么是单次操作时间非常敏感的场景呢

    作者回复: 比如有些系统只关注操作的平均执行时间,大部分操作都很快,比如1s,极个别操作可能花费很多时间10s,但平均下来,整体上都很快,所以也能接受。

    但是有的系统不仅仅关注平均执行时间,对单次操作的时间非常敏感,极个别的10s操作也是无法接受的。

    2019-02-21
    3
  • Laughing_Lz
    老师,你这里提到:我画了两个红黑树的图例,你可以对照着看下。
    这下面的两张图,左边第一个,四个叶子节点都是红色呀?我有点看不懂。。
    规则不是说叶子节点都是不存储数据的黑色空节点吗?这里是不是画错了?
    如果你是说省略了黑色叶子节点,那就是说这四个红色节点下其实还有叶子节点?但是这样又不能满足规则四:每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点...除非第三层的第三个黑色子节点下也有叶子节点?

    作者回复: 是的 都会有nil的黑色叶子节点的

    2018-12-02
    2
  • 丁卯兔
    动态的数据结构可能跳跃链表算一个,实现比红黑树简单,查询,删除,插入都可以;大顶堆,小顶堆应该也还行。
    2018-11-28
    2
收起评论
84
返回
顶部