红黑树(Red Black Tree)是一种平衡的排序二叉树,如图:
所有的红黑树都满足如下性质:
- 每个节点要么是红色,要么是黑色的;
- 根节点和叶子节点(即 NIL 空节点)一定是黑色;
- 红色节点的父节点,或者子节点一定为黑色;
- 对每个节点,从该节点到叶子节点的所有路径上,包含的黑节点数目相同。
根据性质4,我们可以得出:从根节点到叶子节点的可能路径,最长不超过最短路径的两倍。
红黑树的主要应用场景:
- java8 hashmap 中链表转红黑树优势:时间复杂度从O(n) –> O(logn),且自旋开销较其他树较低(不用整体平衡)。
- epoll 在内核中的实现,用红黑树管理 fd 文件描述符
优势:
- 因为内核态需要维护一个长久存放 fd 的数据结构,而 fd 的变动十分频繁,且需要支持快速查询,所以红黑树很适合
- 红黑树可以判断是否是重复的 fd
3.Linux 进程调度 Completely Fair Scheduler,用红黑树管理进程控制块;nginx 中,用红黑树管理 timer 等 。
© 版权声明
文章版权归作者所有,未经允许请勿转载。
THE END
暂无评论内容