25 | 红黑树（上）：为什么工程中都用红黑树这种二叉树？

精选留言(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