美文网首页
第二十五节-红黑树

第二十五节-红黑树

作者: wean_a23e | 来源:发表于2018-12-05 01:19 被阅读23次

什么是“平衡二叉查找树”

平衡二叉树的严格定义:二叉树中任意一个节点的左右子树高度相差不能大于 1。而平衡二叉查找树,就是在平衡二叉树的基础上,满足二叉查找树的特定的树。

但是很多平衡二叉查找树并没有严格符合上面平衡的定义。比如红黑树,它从根节点到各个叶子节点的最长路径,有可能会比最短路径长一倍。

所以,平衡二叉查找树中“平衡”的意思,其实就是让整棵树左右看起来比较“对称”、比较“平衡”,不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些,相应的插入、删除、查找等操作的效率高一些。

红黑树的定义

红黑树是一种不严格的平衡二叉查找树。它要满足一下五个要求:

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

为什么红黑树是“近似平衡”的

追根溯源,我们使用平衡二叉查找树的原因,就是为了解决二叉查找树动态更新导致的性能退化问题。所以,“平衡”的意思可以等价为性能不退化。“近似平衡”就等价为性能不会退化的太严重。

一颗极其平衡的的二叉树的高度大约是 log2n。故,只要证明红黑树的高度是近似 log2n,即可说明红黑树是“近似平衡”的。

土方法推导过程如下:

  1. 首先,将红色节点从红黑树中去掉,那单纯包含黑色节点的红黑树的高度比 log2n 还低:

去除红色节点后,有些节点就没有父节点了,它们会直接拿这些节点的祖父节点作为父节点,所以,之前的二叉树就变成四叉树。

从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从四叉树中取出某些节点,放到叶节点位置,四叉树就变成了完全二叉树。所以,仅包含黑色节点的四叉树的高度,比包含相同节点个数的完全二叉树的高度还要小。&oq=从任意节点到可达的叶子节点的每个路径包含相同数目的黑色节点。我们从四叉树中取出某些节点,放到叶节点位置,四叉树就变成了完全二叉树。所以,仅包含黑色节点的四叉树的高度,比包含相同节点个数的完全二叉树的高度还要小。

而上一届我们说过,完全二叉树的高度近似 log2n,所以,红黑树的高度不会超过 2log2n,同样是 log2n 的数量级。

为什么工程中喜欢用红黑树?

使用平衡查找树是为了获得性能较好的插入、查找、删除操作。不使用 AVL 树是因为它太高度平衡,每次调整的代价太大,相比之下红黑树就是一种比较折中的选择。

相关文章

  • 第二十五节-红黑树

    什么是“平衡二叉查找树” 平衡二叉树的严格定义:二叉树中任意一个节点的左右子树高度相差不能大于 1。而平衡二叉查找...

  • 数据结构—树—红黑树

    红黑树概述 红黑树的插入 红黑树的删除

  • TreeMap

    需要先了解红黑树,这是之前分析红黑树的文章。之前在分析红黑树时,我认为红黑树=二叉查找树+红黑平衡,关于二叉查找树...

  • 数据结构与算法-AVL 红黑树

    AVL树AVL树 算法红黑树红黑树 B站

  • [转载]红黑树

    https://zhuanlan.zhihu.com/p/24367771红黑树简介红黑树插入红黑树删除

  • 拿下红黑树

    红黑树 红黑树、2-3树的简单定义: 实现红黑树的基本结构以及添加操作(维护定义,左旋、右旋、颜色反转) 红黑树与...

  • 红黑树

    啥是红黑树,红黑树 = 二叉树

  • 彻底理解红黑树(二)之 插入

    彻底理解红黑树(一)之 二叉搜索树彻底理解红黑树(二)之 插入彻底理解红黑树(三)之 删除 前言 红黑树的插入情况...

  • 彻底理解红黑树(三)之 删除

    彻底理解红黑树(一)之 二叉搜索树彻底理解红黑树(二)之 插入彻底理解红黑树(三)之 删除 前言 红黑树的删除情况...

  • Golang红黑树

    红黑树 红黑树是每个节点都带有颜色属性(红色或黑色)的二叉查找树。红黑树也属于自平衡二叉查找树。 红黑树具有如下性...

网友评论

      本文标题:第二十五节-红黑树

      本文链接:https://www.haomeiwen.com/subject/wmpbcqtx.html