学习笔记之红黑树

发表于 更新于 分类于

红黑树

  1. 红黑树 Vs AVL
  2. 红黑树的使用场景 ： Java的TreeMap和TreeSet， java8 hashmap （RB tree 取代链表）

二叉查找树的问题是斜树导致查找效率变低， \(\lfloor logn \rfloor\) 变成 n

基于二叉查找树存在的问题 -平衡二叉树

  • AVL
  • 红黑树

实现比较复杂，而且插入和删除性能差，在实际环境下的应用不如红黑树

红黑树（Red-Black Tree，以下简称RBTree）的实际应用非常广泛，比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等，各种语言的函数库如Java的TreeMap和TreeSet，C++ STL的map、multimap、multiset等。

另外，Java 8中HashMap的实现也因为用RBTree取代链表，性能有所提升。

定义

  1. 任何一个节点都有颜色， 红色或黑色
  2. 根节点是黑色
  3. 父子节点不能连续出现红色节点-每个红色结点的两个子结点都是黑色
  4. 任何一个节点向下遍历到子孙的叶子节点，所经过的黑色节点个数必须相等
  5. 空节点被认为是黑色

1

插入

BST插入 - 旋转 + 变色

新插入节点是红色，插入修复如果遇到父节点为黑则修复结束 - 只有父节点为红色时是需要修复的

插入修复分三种 （新插入节点的父节点为红色）

  1. 叔叔节点也为红色
  2. 叔叔节点为空，且祖父节点，父亲节点和新节点出于一条斜线
  3. 叔叔节点为空，且祖父节点，父亲节点和新节点不处于一条斜线

case1

case2

Case3

插入后的修复操作是一个向root节点回溯的操作，一旦牵涉的节点都符合了红黑树的定义，修复操作结束。之所以会向上回溯是由于case 1操作会将父节点，叔叔节点和祖父节点进行换颜色，有可能会导致祖父节点不平衡(红黑树定义3)。这个时候需要对祖父节点为起点进行调节（向上回溯）。

祖父节点调节后如果还是遇到它的祖父颜色问题，操作就会继续向上回溯，直到root节点为止，根据定义root节点永远是黑色的。在向上的追溯的过程中，针对插入的3中情况进行调节。直到符合红黑树的定义为止。直到牵涉的节点都符合了红黑树的定义，修复操作结束。

如果上面的3中情况如果对应的操作是在右子树上，做对应的镜像操作就是了。

删除

较复杂....

总结

作为平衡二叉查找树里面众多的实现之一，红黑树无疑是最简洁、实现最为简单的。红黑树通过引入颜色的概念，通过颜色这个约束条件的使用来保持树的高度平衡。作为平衡二叉查找树，旋转是一个必不可少的操作。通过旋转可以降低树的高度，在红黑树里面还可以转换颜色。

红黑树里面的插入和删除的操作比较难理解，这时要注意记住一点：操作之前红黑树是平衡的，颜色是符合定义的。在操作的时候就需要向兄弟节点、父节点、侄子节点借调和互换颜色，要达到这个目的，就需要不断的进行旋转。所以红黑树的插入删除操作需要不停的旋转，一旦借调了别的节点，删除和插入的节点就会达到局部的平衡（局部符合红黑树的定义），但是被借调的节点就不会平衡了，这时就需要以被借调的节点为起点继续进行调整，直到整棵树都是平衡的。在整个修复的过程中，插入具体的分为3种情况，删除分为4种情况。

整个红黑树的查找，插入和删除都是O(logN)的，原因就是整个红黑树的高度是logN，查找从根到叶，走过的路径是树的高度，删除和插入操作是从叶到根的，所以经过的路径都是logN。

红黑树与 AVL 区别

红黑树相比于AVL，牺牲了部分平衡性，以换取删除、插入更少量的旋转次数。整体性能优于AVL

红黑树插入效率比AVL树高，因为rebalance操作O(1)比AVL树O(logn)快，但是以牺牲search效率为代价的，AVL树在查询频繁的系统里比红黑树更高效，原因是avl树的平均高度比红黑树更小

*Difference*:

  1. AVL trees provide faster lookups than Red Black Trees because they are more strictly balanced.
  2. Red Black Trees provide faster insertion and removal operations than AVL trees as fewer rotations are done due to relatively relaxed balancing.
  3. AVL trees store balance factors or heights with each node, thus requires storage for an integer per node whereas Red Black Tree requires only 1 bit of information per node.
  4. Red Black Trees are used in most of the language libraries like map, multimap, multiset in C++ whereas AVL trees are used in databases where faster retrievals are required.

参考:

漫画：什么是红黑树？- 1 https://mp.weixin.qq.com/s/cnDx8lJ6fXHgLZWsqjWrag

漫画：什么是红黑树？ -2 https://mp.weixin.qq.com/s/waFh-_7Q3EiFdUfXawm4Ww

红黑树深入剖析及Java实现 https://zhuanlan.zhihu.com/p/24367771