• 欢迎来到我的博客
  • [email protected]

红黑树(工程二叉树)

学习笔记 tianlan 2年前 (2020-04-09) 757次浏览 0个评论 扫描二维码
文章目录[隐藏]

引入

我们提到平衡二叉树是最理想的二叉排序树,性能最好,也最稳定,但是缺点是维护成本高,需要在插入和删除节点时维护新树的平衡性,所以工程实践中,我们倾向于使用另一种二叉排序树 —— 红黑树

定义

红黑树(Red-Black Tree)是每个节点都带有颜色属性的二叉排序(查找)树,具备以下特性:

  • 节点是红色或黑色;
  • 根节点是黑色的;
  • 每个叶子节点都是黑色的空节点(NIL),也就是说,叶子节点不存储数据;
  • 任何相邻的节点都不能同时为红色,也就是说,红色节点是被黑色节点隔开的;
  • 每个节点,从该节点到达其可达叶子节点的所有路径,都包含相同数目的黑色节点;

下面是一个典型的红黑树示例:

红黑树(工程二叉树)

这些约束保证了红黑树的关键特性:红黑树无论怎么插入、删除节点大致上也是平衡的。

红黑树的算法复杂度

我们上面提到由于红黑树的特性,可以确保即使在最差情况下,红黑树也是大致平衡的,下面我们来简单推导下红黑树的时间复杂度。

前面我们讲二叉排序树的时候说到二叉排序树的时间复杂度和树的高度成正比,红黑树是红黑相间的,我们可以先把红色的节点去掉,剩下的黑色节点就可能变成四叉树了,比如我们上面示例的那个红黑树。由于红黑树每条路径上黑色节点相同,所以可以继续把这个四叉树转化为完全二叉树,假设黑色节点的数量为 m,这样,这棵树的时间复杂度就是 O(logm) 了;然后我们把红色节点塞回来,红色节点的总数目肯定是小于等于黑色节点的,我们不妨假设等于黑色节点,这样,树的高度就增加一倍,对应的时间复杂度就是 2O(logm) 了,m≈n/2,由于在计算时间复杂度的时候,常量可以舍弃,所以红黑树的时间复杂度也是 O(logn)。虽然这里面都是估算的,但是由于前面提到的红黑树的特性约束,数量级上是没问题的。

为什么工程上大多使用红黑树

红黑树维护成本比平衡二叉树低,性能上也能大致做到 O(logn),且比较稳定,可以应付最差的情况。下一篇我们就来简单介绍下红黑树的实现。·

参考网站

https://xueyuanjun.com/post/21019


天蓝, 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:红黑树(工程二叉树)
喜欢 (0)
[[email protected]]
分享 (0)

您必须 登录 才能发表评论!