红黑树在不同场景的应用及其优势 
红黑树(平衡的排序二叉树)，满足以下性质： 1）每个结点要么是红的，要么是黑的。 2）根结点是黑的。 3）每个叶结点，即空结点（NIL）是黑的。 4）如果一个结点是红的，那么它的俩个儿子都是黑的。 5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点 根据性质5，我们得出：从根到叶子的最长的可能路径不多于最短的可能路径的两倍长 红黑树的关键性质: 内部保证有序，旋转开销小，整体相对平衡 红黑树的应用： 1、java8 hashmap中链表转红黑树。 优势：时间复杂度从O(n)–>O(logn) ，且自旋开销较其他树较低（不用整体平衡）。 2、epoll在内核中的实现，用红黑树管理事件块（文件描述符）。 优势： 1、因为内核态需要维护一个长久存放fd的数据结构，而fd变动十分频繁，且需要支持快速查询，且所以红黑树很适合。 2、红黑树可以判断是否是重复的fd —– 其实我感觉用hash表也可以 3、Java的TreeMap实现 相对与hashMap优势，内部key保持有序，且支持自定义排序比较器。 适用场景，对数据需要排序统计 4、linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块 CFS 背后的主要想法是维护为任务提供处理器时间方面的平衡（公平性）。这意味着应给进程分配相当数量的处理器 
任务存储在以时间为顺序的红黑树中（由 对象表示），对处理器需求最多的任务 （最低虚拟执行时vruntime）存储在树的左側，处理器需求最少的任务（最高虚拟执行时）存储在树的右側。 为了公平。调度器然后选取红黑树最左端的节点调度为下一个以便保持公平性。 任务通过将其执行时间加入到虚拟执行时， 说明其占用 CPU 的时间，然后假设可执行。再插回到树中。这样，树左側的任务就被给予时间执行了，树的内容从右側迁移到左側以保持公平。 因此，每一个可执行的任务都会追赶其它任务以维持整个可执行任务集合的执行平衡。 CFS 不直接使用优先级而是将其用作同意任务运行的时间的衰减系数。低优先级任务具有更高的衰减系数。而高优先级任务具有较低的衰减系数。 这意味着与高优先级任务相比，低优先级任务同意任务运行的时间消耗得更快。 这是一个绝妙的解决方式，能够避免维护按优先级调度的运行队列。 优势：优先级保证下没有O(1)出色，但之所以没有用队列是为了保证其公平性 其他：nginx中，用红黑树管理timer等 参考文章： https://blog.csdn.net/ywh147/article/details/8684486 https://www.cnblogs.com/mfrbuaa/p/4641240.html
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/22570.html
