红黑树的特性分析以及应用原理

简介: 红黑树的特性分析以及应用原理

红黑树

红黑树的特性

  • 每个节点都是红色或者是黑色的
  • 根节点是黑色的
  • 每个叶子节点都是黑的(注意:红黑树的叶子节点是NIL节点,值为空,但有颜色)
  • 如果一个节点是红色,则这个节点的两个子节点都是黑色
  • 对于每一个节点,从该节点到其子孙的叶子节点的所有路径上包含相同数目的黑节点

图中是一颗红黑树

备注:图中树隐藏掉了叶子节点的NIL节点。可以看到该数据结构满足红黑树的五个特性,这是一颗红黑树。

红黑树的应用

  1. 定时器。比如Nginx网络模型中使用定时器,每个连接的socket都有自己的时间戳,采用红黑树保存socket的时间信息就可以依次对超时连接或者超时响应的socket做相应的操作处理。
  2. epoll。epoll中会将监控的fd通过红黑树的结构来描述。
  3. 进程调度。进程调度中的CFS调度方法利用红黑树来保证每个进程分配到公平的CPU时间片。
  4. C++中map、set、multimap、multiset的底层数据结构都用到红黑树。

为什么要有红黑树?

红黑树是一颗二叉搜索树(左子树上所有结点的值均小于它的根的值;右子树上所有结点的值均大于它的根结点的值),有排序、检索的功能。而这些功能在二叉搜索树、平衡二叉树这类数据结构中也可以完成。那为什么有红黑树呢?

1:二叉搜索树可以实现排序,顺序查找的功能,但是二叉搜索树可能会有如下的结构(类似链表):

该结构仍然是一个二叉搜索树,但是当从根节点(0001)搜索到节点0005时,这种情况就费时,比较糟糕。

2:平衡二叉树可以解决上面这个问题,

平衡二叉树会控制左右子树的高度差,因此不会产生上面类似链表这种情况。平衡二叉树即可以排序,又不会出现类似链表的情况.

但是在插入和删除节点时,该结构要通过旋转节点来调整,而其旋转操作次数不一定,可能会旋转很多次,性能会下降很多。

红黑树和平衡二叉树的比较

红黑树是平衡二叉树在平衡度和效率之间做的一种妥协,平衡二叉树相对红黑树来说更加平衡,因此在搜索操作中,平衡二叉树的效率会略快于红黑树。

但是红黑树用非严格的平衡来换取了增删节点旋转次数的减少,而平衡二叉树在增删节点时,旋转次数会比红黑树多得多。

红黑树在插入、删除节点时会通过变色,左旋、右旋来调整节点。插入节点时,红黑树和平衡二叉树均最多两次旋转就能达到平衡;删除节点时,红黑树其旋转次数不会超过三次,而平衡二叉树旋转的量级是O(logN)。整体统计性能来说红黑树是要好于平衡二叉树。

总结:实际应用中,如果搜索业务远远大于增删业务,那么可以选择平衡二叉树;如果搜索业务相对来说占比不多的话,还是用红黑树。

红黑树的时间复杂度

(假如有n个节点数据)

时间复杂度
查找 O(logn)
删除 O(logn)
添加 O(logn)

无论是二叉树,红黑树等,树的时间复杂复杂度其实也就是树的高度。n个节点的数据放在红黑树中,树的高度就是logn,因此红黑树的时间复杂度也是O(logn)。

目录
相关文章
|
6月前
|
机器学习/深度学习 存储 算法
【算法与数据结构】复杂度深度解析(超详解)
【算法与数据结构】复杂度深度解析(超详解)
【算法与数据结构】复杂度深度解析(超详解)
|
6月前
|
存储 搜索推荐 关系型数据库
深度探讨数据库索引的数据结构及优化策略
深度探讨数据库索引的数据结构及优化策略
|
6月前
|
搜索推荐
搜索树基础:二叉搜索树(详解特性用途,图解实现过程)
搜索树基础:二叉搜索树(详解特性用途,图解实现过程)
|
6月前
|
算法 索引
【算法与数据结构】深入二叉树实现超详解(全源码优化)
【算法与数据结构】深入二叉树实现超详解(全源码优化)
110 1
数据结构(7)树形结构——红黑树(概念、插入过程、删除过程)
7.1.概述 平衡二叉树是要求任意结点的左右子树高度差不超过1,因此在AVL中用旋转来保证树的绝对平衡,但是这些旋转操作步骤繁多很耗时间,所以在面对经常会有数据插入的场景时,AVL不是一个性能优秀的选择。这时候反过来思考一个问题,旋转是为了保证树的绝对平衡,但是树的绝对平衡是必须的吗?显然不是,树的高度差只要不是太高从而退化成斜二叉树其实就能接受。
96 0
|
存储 算法 大数据
算法的特性和空间复杂度---数据结构
算法的特性和空间复杂度---数据结构
130 0
数据结构——红黑树的特性及实现(二)
数据结构——红黑树的特性及实现
93 0
 数据结构——红黑树的特性及实现(二)
|
存储 API
数据结构——红黑树的特性及实现(一)
数据结构——红黑树的特性及实现
121 0
数据结构——红黑树的特性及实现(一)
数据结构170-红黑树的变换之变化规则5
数据结构170-红黑树的变换之变化规则5
51 0
数据结构170-红黑树的变换之变化规则5
数据结构169-红黑树的变换之变化规则4
数据结构169-红黑树的变换之变化规则4
43 0
数据结构169-红黑树的变换之变化规则4