红黑树
红黑树的特性
- 每个节点都是红色或者是黑色的
- 根节点是黑色的
- 每个叶子节点都是黑的(注意:红黑树的叶子节点是NIL节点,值为空,但有颜色)
- 如果一个节点是红色,则这个节点的两个子节点都是黑色
- 对于每一个节点,从该节点到其子孙的叶子节点的所有路径上包含相同数目的黑节点
图中是一颗红黑树
备注:图中树隐藏掉了叶子节点的NIL节点。可以看到该数据结构满足红黑树的五个特性,这是一颗红黑树。
红黑树的应用
- 定时器。比如Nginx网络模型中使用定时器,每个连接的socket都有自己的时间戳,采用红黑树保存socket的时间信息就可以依次对超时连接或者超时响应的socket做相应的操作处理。
- epoll。epoll中会将监控的fd通过红黑树的结构来描述。
- 进程调度。进程调度中的CFS调度方法利用红黑树来保证每个进程分配到公平的CPU时间片。
- C++中map、set、multimap、multiset的底层数据结构都用到红黑树。
为什么要有红黑树?
红黑树是一颗二叉搜索树(左子树上所有结点的值均小于它的根的值;右子树上所有结点的值均大于它的根结点的值),有排序、检索的功能。而这些功能在二叉搜索树、平衡二叉树这类数据结构中也可以完成。那为什么有红黑树呢?
1:二叉搜索树可以实现排序,顺序查找的功能,但是二叉搜索树可能会有如下的结构(类似链表):
该结构仍然是一个二叉搜索树,但是当从根节点(0001)搜索到节点0005时,这种情况就费时,比较糟糕。
2:平衡二叉树可以解决上面这个问题,
平衡二叉树会控制左右子树的高度差,因此不会产生上面类似链表这种情况。平衡二叉树即可以排序,又不会出现类似链表的情况.
但是在插入和删除节点时,该结构要通过旋转节点来调整,而其旋转操作次数不一定,可能会旋转很多次,性能会下降很多。
红黑树和平衡二叉树的比较
红黑树是平衡二叉树在平衡度和效率之间做的一种妥协,平衡二叉树相对红黑树来说更加平衡,因此在搜索操作中,平衡二叉树的效率会略快于红黑树。
但是红黑树用非严格的平衡来换取了增删节点旋转次数的减少,而平衡二叉树在增删节点时,旋转次数会比红黑树多得多。
红黑树在插入、删除节点时会通过变色,左旋、右旋来调整节点。插入节点时,红黑树和平衡二叉树均最多两次旋转就能达到平衡;删除节点时,红黑树其旋转次数不会超过三次,而平衡二叉树旋转的量级是O(logN)。整体统计性能来说红黑树是要好于平衡二叉树。
总结:实际应用中,如果搜索业务远远大于增删业务,那么可以选择平衡二叉树;如果搜索业务相对来说占比不多的话,还是用红黑树。
红黑树的时间复杂度
(假如有n个节点数据)
时间复杂度 | |
查找 | O(logn) |
删除 | O(logn) |
添加 | O(logn) |
无论是二叉树,红黑树等,树的时间复杂复杂度其实也就是树的高度。n个节点的数据放在红黑树中,树的高度就是logn,因此红黑树的时间复杂度也是O(logn)。