精选留言(136)

• 
  kakasi

  2018-12-02

  散列表：插入删除查找都是O(1), 是最常用的，但其缺点是不能顺序遍历以及扩容缩容的性能损耗。适用于那些不需要顺序遍历，数据更新不那么频繁的。 跳表：插入删除查找都是O(logn), 并且能顺序遍历。缺点是空间复杂度O(n)。适用于不那么在意内存空间的，其顺序遍历和区间查找非常方便。 红黑树：插入删除查找都是O(logn), 中序遍历即是顺序遍历，稳定。缺点是难以实现，去查找不方便。其实跳表更佳，但红黑树已经用于很多地方了。

  展开

  共 36 条评论

  499
• 
  🐱您的好友William...

  2018-11-16

  老师做图的软件用的是什么啊？我看了不少的极客时间的blog，感觉老师这个是最好看的哈哈。

  共 9 条评论

  235
• 
  王争

  2018-11-16

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

  展开

  共 5 条评论

  220
• 
  蜗牛行天下

  2019-01-31

  我觉得红黑树对于我们初学者来说最大的疑惑是，红黑节点有什么区别，是怎么演化来的？老师讲的很好，但是这个问题并没有在文中解决，所以不能深刻地理解红黑树的存在价值。我找到一篇文章，在这方面讲的很清楚，可以作为这篇讲义的补充：https://www.cnblogs.com/tiancai/p/9072813.html

  共 20 条评论

  181
• 
  Smallfly

  2018-11-16

  动态数据结构的动态是什么意思？ 动态是指在运行时该数据结构所占的内存会扩大或缩小。 数组是一种静态的数据结构，在创建时内存大小已经确定，不管有没有插入数据。而链表是动态的数据结构，插入数据 alloc 内存，删除数据 release 内存。 栈、队列、散列表、跳表、树都是抽象的数据结构，它们在内存中存在的形式都要依赖于数组或者链表。 如果用链表实现，很明显它们是动态的数据结构；如果用数组实现，那么在扩容的时候会创建更大内存的数组，原数组被废弃，从抽象角度看，它们仍旧是动态的。

  展开

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

  共 6 条评论

  135
• 
  allan

  2018-12-02

  看了这篇文章还是有很多疑惑，主要是 不理解红黑树满足的几个性质，为什么要那样要求？

  共 7 条评论

  76
• 
  fy

  2018-11-18

  老师，可以教我们刷下leetcode上的算法，毕竟讲了这么多，还是练习的。这样的提升才有巨大的帮助

  共 3 条评论

  74
• 
  S.S Mr Lin

  2019-03-22

  很多讲红黑树的地方都没讲2-3-4树，其实如果看懂了2-3-4树，再来看红黑树就特别好理解了。我一般会问别人，红黑树的黑节点代表了什么？如果理解了，就会知道黑节点代表了近似平衡高度，所有黑节点的定义都是为了保证这一点。

  共 2 条评论

  50
• 
  失火的夏天

  2018-11-16

  动态数据结构有链表，栈，队列，哈希表等等。链表适合遍历的场景，插入和删除操作方便，栈和队列可以算一种特殊的链表，分别适用先进后出和先进先出的场景。哈希表适合插入和删除比较少（尽量少的扩容和缩容），查找比较多的时候。红黑树对数据要求有序，对数据增删查都有一定要求的时候。（个人看法，欢迎老师指正）

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

  

  40
• 
  freesocean

  2019-11-12

  **基本数据结构：** 1.数组：连续的内存空间，支持按下标随机访问O(1)，删除和查找设计数据搬移效率是O(n) 试用场景：数据规模较小，不经常变动。 缺点：对于内存连续性要求高。插入删除操作效率低。 2.链表：查询效率不高O(n)，插入和删除效率高O(1)，并且内存申请可以不连续，适用场景是插入和删除多于查询操作。 缺点：查找效率低，实际上删除之前先要查找，所以实际删除效率也不高。 **动态数据结构：** 1.散列表：可以说是利用数组和链表两个基本数据结构设计了一个高效的动态数据结构。利用了数组的随机访问特性，用于满足根据某个属性来随机访问元素。基于key查找效率很高O(1).同时借助链表进行散列冲突解决方案，删除和插入操作效率也可以接近O(1).试用场景：海量数据随机访问、防止重复、缓存等。 缺点：需要设计合理的散列函数，并且要考虑散列冲突和动态扩容。 2.跳表：尽管散列表效率很高，但是散列表是无序的，跳表效率和散列表类似，并且支持区间序列的输出（因为基于链表）。使用场景：对有序元素的快速查找、插入和删除。 缺点：比较占用内存。 3.红黑树：红黑树是平衡二叉查找树的一种近似实现。红黑树和跳表类似，但是实现方式有所差异。红黑树存在的价值是，它可以实现比较高效的查找，删除和插入。虽然相比高度平衡的AVL树效率有所下降，但是红黑树不用耗费太多精力维护平衡。相比跳表，红黑树除了内存占用较小，其他性能并不比跳表更优。但由于历史原因，红黑树使用的更广泛。 缺点：实现比较复杂。

  展开

  共 1 条评论

  35
• 
  洲

  2019-12-23

  感觉红黑树老师讲的很急，对于没有基础的同学有点跳跃，我看了这个链接的文章搞明白了。https://blog.csdn.net/fei33423/article/details/79132930

  共 3 条评论

  31
• 
  null

  2018-11-16

  红黑树的节点颜色，是如何确定的，如何知道在新增一个节点时，该节点是什么颜色？ 从红黑树需要满足的四个要求来看： 1. 根节点为黑色 2. 所有叶子节点为黑色，且不存储数据 3. 相邻两个节点不能都为红色 4. 从某节点到其所有叶子节点的路径中，黑色节点数相同 从这四点要求，好像我一根树全是黑色，也是满足其定义的。这里用红黑两色区分各节点，意义是啥？ 谢谢老师

  展开

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

  共 3 条评论

  15
• 
  不似旧日

  2019-01-03

  没明白红节点与黑节点的存在意义

  共 3 条评论

  12
• 
  有铭

  2018-11-16

  我除了看懂红黑树是一种“性能上比较均衡”的二叉树这个结论外，完全没搞懂它为啥能获得这个“比较平衡”的结果

  共 3 条评论

  12
• 
  increasingly

  2019-02-21

  请问什么是单次操作时间非常敏感的场景呢

  作者回复: 比如有些系统只关注操作的平均执行时间，大部分操作都很快，比如1s，极个别操作可能花费很多时间10s，但平均下来，整体上都很快，所以也能接受。 但是有的系统不仅仅关注平均执行时间，对单次操作的时间非常敏感，极个别的10s操作也是无法接受的。

  

  9
• 
  朱月俊

  2018-11-17

  动态数据结构比如本篇的平衡二叉查找树，还有就是跳表，跳表也支持动态插入，删除，查询，也很快，不同点是跳表还能支持快速的范围查询。比如leveldb中的memtable，redis都是使用跳表实现的，而也有用红黑树实现的memtable。 除此之外，跳表还支持多写多读，而红黑树不可以，这些场景下显然用跳表合适。

  共 1 条评论

  8
• 
  wean

  2018-11-16

  “我们从四叉树中取出某些节点，放到叶节点位置，四叉树就变成了完全二叉树” 老师，这里的某些节点应该怎么取，才能让四叉树变成二叉树，不是很明白，希望老师讲解一下，谢谢

  

  8
• 
  注定非凡

  2019-12-28

  二叉查找树是常用的一种二叉树，他支持快速插入，删除，查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是O(logn) 在很多书籍中，但凡讲到平衡二叉查找树，就会那红黑树做为例子。在工程中，很多用到平衡二叉查找树的地方都会用红黑树。 一，什么是“平衡二叉查找树” 1，定义：二叉树中任意一个节点的左右子树的高度相差不能大于1。 所以：完全二叉树，满二叉树都是平衡二叉树，非完全二叉树也有可能是平衡二叉树。 2，平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。 3，发明平衡二叉查找树这类数据结构的初衷是解决普通二叉查找树在频繁的插入，删除等动态更新的情况下，出现时间复杂度退化的问题。 所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”，比较“平衡”，不要出现左子树很高，右子树很矮的情况。这样就能让整颗树的高度相对低一些，相应的插入，删除，查找等操作的效率高一些。 4，若设计一个新的平衡二叉查找树，只要树的高度不比log2n大很多（如树的高度仍然是对数量级的），尽管它不符合严格的平衡二叉查找树的定义，但它仍然可以被认为是一个合格的平衡二叉查找树。 二，如何定义一棵“红黑树” 1，平衡二叉查找树有很多，如：Splay Tree(伸展树)，Treap（树堆）等，但是我们提到平衡二叉查找树，听到的基本都是红黑树。他的出境率甚至要高于“平衡二叉查找树”这几个字，甚至在有些时刻，默认平衡二叉查找树就是红黑树 2，红黑树：英文“Red-Black-Tree”，简称R-B Tree，有如下特性： 它是一种不严格的平衡二叉查找树。 红黑树中的节点，一类别标记为黑色，一类被标记为红色。 根节点是黑色的； 每个叶子节点都是黑色的空节点（NIL）,也就是说，叶子节点不存储数据； 任何相邻的节点都不能同时为红色，即红色节点都是被黑色节点隔开的； 每个节点，从该节点到达其可达叶子节点的所有路径，都包含相同数目的黑色节点； 3，二叉查找树很多操作的性能都跟树的高度成正比，一课极其平衡的二叉树（满二叉树或完全二叉树）的高度大约是log2n,所以要证明红黑树是近似平衡的，我们只需要分析，红黑树的高度是否比较稳定地趋近log2n就好 。 4，红黑树的高度分析 ①：首先，若将红色节点从红黑树中去除，那单纯包含黑色节点的红黑树的高度比包含相同节点个数的完全二叉树的高度要小。所以去掉红色节点的“黑树”的高度也不会超过log2n。 ②：在红黑树中，红色节点不能相邻，即有一个红色节点就要至少有一个黑色节点，将它更其他红色节点隔开。 红黑树中包含最多黑色节点的路径不会超过log2n,所以加入红色节点之后，最长路径不会超过2log2n，即，红黑树的高度近似2log2n ③：红黑树的高度只比高度平衡的AVL树的高度（log2n）仅仅大了一倍，在性能上下降的并不多。 三：工程中大家都喜欢用红黑树这种平衡二叉查找树的原因： ①：Treap，Splay Tree，绝大部分情况下，它们操作的效率都很高，但是也无法避免极端情况下时间复杂度的退化。尽管这种情况出现概率不大，但是对于单次操作时间非常敏感的场景来讲，它们不适用。 ②：AVL树是一种高度平衡的二叉树，所以查找的效率非常高，但是，有利有弊，AVL树为了维持这种高度平衡，要付出更多代价，每次插入，删除都要做调整，就比较复杂，耗时。所以有频繁的插入，删除操作的数据集合，使用AVL树的代价就有点高了。 ③：红黑树只是做到了近似平衡，并不是严格的平衡，所以维护平衡的成本上，要比AVL树低。 所以，红黑树的插入，删除，查找各种操作性能都比较稳定。对于工程应用来说，结果状态可控可预期。

  展开

  

  8
• 
  Langzi233

  2019-08-10

  学习红黑树强烈推荐《算法》，这本书对红黑树的讲解非常精彩，各种数据结构和算法的书各有侧重点，可以选择着看。

  

  6
• 
  ！null

  2018-11-21

  没太看懂去掉红色节点生成全黑四叉树，又把红色节点加进去的目的是什么？感觉不懂这个整个红黑树就没学懂。

  

  6