日拱算法之不能不知道的“红黑树”

这是我参与11月更文挑战的第28天，活动详情查看：2021最后一次更文挑战

不知道前端小伙伴们都了解“红黑树”吗？本瓜，之前听是听过，但是它到底是干嘛的，并不十分清楚。在认识了平衡二叉树、AVL 树之后，现在已经来到了这个节点，必须来看下“红黑树”了！

今天也不是植树节，却依旧要来种树！🌳🌳🌳

闲言少叙，冲！(ง •_•)ง

算法专栏 关于树的文章传送门：

• 《日拱算法之判断平衡二叉树》
• 《AVL 树旋转及 JS 实现，平衡树支棱起来~》
• 《大小堆解决【数据流中位数】问题，nice 图解~》

先来看下二叉查找树是为什么而诞生的！

我们都知道：数组适合查询这种静态操作(O(1))，不合适删除与插入这种动态操作(O(n)),而链表则是适合删除与插入，而查询效率则就比较慢了；

二叉查找树就是为了平衡这种静态操作（数组）与动态操作（链表）的差距而诞生的~

特性：

• 任意节点左子树不为空,则左子树的值均小于根节点的值；
• 任意节点右子树不为空,则右子树的值均大于于根节点的值；
• 任意节点的左右子树也分别是二叉查找树；
• 没有键值相等的节点；

为了避免如下图极端情况出现：

二叉查找树必须“平衡”，以防止单边层数过深；

于是就诞生了 AVL 树（平衡二叉树）！

实践复杂度被提升到 O(log2n)；

AVL树是带有平衡条件的二叉查找树，左右子树树高不超过1，它是严格的平衡二叉树；

不管我们是执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而 旋转是非常耗时的；

由此我们可以知道AVL树适合用于插入删除次数比较少，但查找多的情况。

为了权衡“平衡”和“旋转耗时”这两个特性，于是 “红黑树” 诞生了！！

红黑树是一种弱平衡二叉树！通过对任何一条从根到叶子的路径上各个节点着色的方式的限制确保：没有一条路径会比其它路径长出两倍；

相对于要求严格的AVL树来说,它的旋转次数变少；与之对应的，旋转带来的耗时也更小；

红黑树有很广泛的应用：

• C++的STL中,map和set都是用红黑树实现的；
• 著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块,进程的虚拟内存区域都存储在一颗红黑树上,每个虚拟地址区域都对应红黑树的一个节点,左指针指向相邻的地址虚拟存储区域,右指针指向相邻的高地址虚拟地址空间；
• IO多路复用epoll的实现采用红黑树组织管理sockfd，以支持快速的增删改查；
• ngnix中,用红黑树管理timer,因为红黑树是有序的,可以很快的得到距离当前最小的定时器.
• java中TreeMap的实现；

红黑是用非严格的平衡来换取增删节点时候旋转次数的降低，任何不平衡都会在三次旋转之内解决~~

欲了解更多，推荐阅读 b乎上的回答：

OK，本篇仅分享红黑树诞生的渊源、以及一些概念上的东西，后续带来在 JS 中的实现等等；

其实，空间换时间的概念在很多地方都可以见到，函数式编程更耗费内存，也是空间换时间；神奇~~

撰文不易，点赞鼓励👍👍👍

我是掘金安东尼，公众号同名，日拱一卒、日掘一金，再会~