关于Java的二叉树、红黑树、B+树详解

目录
  • 1、二叉查找树
  • 2、平衡二叉查找树
  • 3、红黑树:
  • 4、 B树:
  • 5、 B+树
  • 6、红黑树 VS B+树

数组和链表是常用的数据结构,数组虽然查找快(有序数组可以通过二分法查找),但是插入和删除是比较慢的;而链表,插入和删除很快(只需要改变一些引用值),但是查找就很慢,需要从头开始遍历; 那么有没有一种数据结构能同时具备数组查找快的优点以及链表插入和删除快的优点呢,那就是接下来要介绍的——树。

1、二叉查找树

特性:

  • 1、左子树上所有节点的值均小于它的根节点的值;
  • 2、右子树上所有节点的值均大于它的根节点的值;
  • 3、左、右子树也分别为二叉排序树。

2、平衡二叉查找树

特性:

  • 1、在二叉树的基础上,要求两个子树的高度差不能超过1;
  • 2、每次增删都会通过一次或多次旋转来平衡二叉树;

调整平衡的基本思想:

当在二叉排序树中插入一个节点时,首先检查是否因插入而破坏了平衡,若破坏,则找出其中的最小不平衡二叉树,在保持二叉排序树特性的情况下,调整最小不平衡子树中节点之间的关系,以达到新的平衡。 所谓最小不平衡子树,指离插入节点最近且以平衡因子的绝对值大于1的节点作为根的子树。

先插入指定节点,记录下当前节点的信息,LH,EH或者RH。

  • 若左子树高LH,查看其左子树根节点的信息,若是LH,则一次右旋;若是RH,则一次左旋+一次右旋
  • 若右子树高RH,查看右子树根节点的信息,若是RH,则一次左旋;若是LH,则一次右旋+一次左旋
  • 调整改变的节点信息

虽然平衡树解决了二叉查找树退化为近似链表的缺点,能够把查找时间控制在 O(logn),不过却不是最佳的,因为平衡树要求每个节点的左子树和右子树的高度差至多等于1,这个要求实在是太严了,导致每次进行插入/删除节点的时候,几乎都会破坏平衡树的第二个规则,进而我们都需要通过左旋和右旋来进行调整,使之再次成为一颗符合要求的平衡树,且随着树的高度的增加,动态插入和删除的代价也越来越大,为了解决优化插入和删除性能,红黑树出现了。

显然,如果在那种插入、删除很频繁的场景中,平衡树需要频繁着进行调整,这会使平衡树的性能大打折扣,为了解决这个问题,于是有了红黑树,红黑树具有如下特点:

3、红黑树:

特性:

1、根节点是黑色;

2、每个节点或者是黑色,或者是红色;

3、每个叶子节点是黑色。 [注意:这里叶子节点,是指为空的叶子节点!;

4、如果一个节点是红色的,则它的子节点必须是黑色的,也就是说一个红节点的父节点只能是黑色

5、从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点,也就是说确保没有一条路径会比其他路径长出俩倍;

红黑树(Red Black Tree) 是一种自平衡二叉查找树 红黑树和AVL树类似,都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡,从而获得较高的查找性能。 二叉平衡树的严格平衡策略以牺牲建立查找结构(插入,删除操作)的代价,换来了稳定的O(logN) 的查找时间复杂度 它虽然是复杂的,但它的最坏情况运行时间也是非常良好的,并且在实践中是高效的: 它可以在O(log n)时间内做查找,插入和删除,这里的n 是树中元素的数目。

红黑树的操作代价:

  • 查找代价:由于红黑树的性质(最长路径长度不超过最短路径长度的2倍),可以说明红黑树虽然不像平衡二叉查找树一样是严格平衡的,但平衡性能还是要比二叉查找树要好。其查找代价基本维持在O(logN)左右,但在最差情况下(最长路径是最短路径的2倍少1),比平衡二叉查找树要略逊色一点。
  • 插入代价:RBT插入结点时,需要旋转操作和变色操作。但由于只需要保证RBT基本平衡就可以了。因此插入结点最多只需要2次旋转,这一点和平衡二叉查找树的插入操作一样。虽然变色操作需要O(logN),但是变色操作十分简单,代价很小。
  • 删除代价:红黑树的删除操作代价要比平衡二叉查找树要好的多,删除一个结点最多只需要3次旋转操作。

RBT 效率总结 : 查找效率最好情况下时间复杂度为O(logN),但在最坏情况下比平衡二叉查找树要差一些,但也远远好于二叉查找树。 插入和删除操作改变树的平衡性的概率要远远小于AVL(RBT不是高度平衡的)。因此需要的旋转操作的可能性要小,而且一旦需要旋转,插入一个结点最多只需要旋转2次,删除最多只需要旋转3次(小于AVL的删除操作所需要的旋转次数)。虽然变色操作的时间复杂度在O(logN),但是实际上,这种操作由于简单所需要的代价很小。

红黑树能够以O(log2(N))的时间复杂度进行搜索、插入、删除操作。此外,任何不平衡都会在3次旋转之内解决。这一点是平衡二叉查找树所不具备的。

调整平衡的基本思想:

  • 变色:为了重新符合红黑树的规则,尝试把红色节点变为黑色,或者把黑色节点变为红色。
  • 左旋转:逆时针旋转红黑树的两个节点,使得父节点被自己的右孩子取代,而自己成为自己的左孩子。说起来很怪异,大家看下图:

  • 右旋转:顺时针旋转红黑树的两个节点,使得父节点被自己的左孩子取代,而自己成为自己的右孩子。大家看下图:

场景:HashMap TreeSet TreeMap

4、 B树:

设计缘由:

数据库索引是存储在磁盘上的,当数据量比较大的时候,索引的大小可能有十几个G,甚至更多。当我们利用索引查询的时候,能把整个索引全部加载到内存吗?显然不可能,能做的只有逐一加载每一个磁盘页,这里的磁盘页对应着索引树的节点。

如果我们利用二叉查找树作为索引结构,那么最坏(每个节点数据在不同磁盘页上)的情况下,磁盘IO次数等于索引树的高度。 所以,为了减少磁盘IO次数,我们就需要把原本“瘦高”的树结构变得“矮胖”(节点数变少了)。这就是B树的特征之一

B树是一种多路平衡查找树,它的每一个节点最多包含m个孩子,m被称为B树的阶,m的大小取决于磁盘页的大小。——一个节点最多包含一个磁盘页的数据

也就是说,当B树变得矮胖以后,每个节点可以包含多个数据(数据量大小由磁盘页的大小决定),同样的数据,B树比二叉树/红黑树节点少。所以,B树在查询时,磁盘IO次数变少了,从而可以提升查找性能。

特征:

一个m阶的B树具有如下几个特征:

1.根结点至少有两个子女。
2.每个中间节点都包含k-1个元素和k个孩子,其中 m/2 <= k <= m
3.每一个叶子节点都包含k-1个元素,其中 m/2 <= k <= m
4.所有的叶子结点都位于同一层。
5.每个节点中的元素从小到大排列,节点当中k-1个元素正好是k个孩子包含的元素的值域分划

场景:

B树主要应用于文件系统以及部分数据库索引,比如著名的非关系型数据MongoDB。 而大部分关系型数据库,比如mysql,则使用B+树作为索引

5、 B+树

B+树是B树的一种变体,但是又有所不同,

特征:

一个m阶的B+树具有如下几个特征:

  • 1.有k个子树的中间节点包含有k个元素(B树中是k-1个元素),每个元素不保存数据,只用来索引,所有数据都保存在叶子节点。
  • 2.所有的叶子结点中包含了全部元素的信息,及指向含这些元素记录的指针,且叶子结点本身依关键字的大小自小而大顺序链接。
  • 3.所有的中间节点元素都同时存在于子节点,在子节点元素中是最大(或最小)元素。

这里特别要注意有两点:

其一:每个父节点的元素都出现在子节点中,是子节点的最大(或最小)元素;因此所有叶子节点包含了全量元素信息;

其二:每个叶子节点都带有指向下一个节点的指针,形成了一个有序链表;

其三:只有叶子节点带有卫星数据,其余中间节点仅仅是索引,没有任何数据关联,如下图,所谓卫星数据,指的是索引元素所指向的数据记录,比如数据库中的某一行,在B树种,无论中间节点还是叶子节点都带有卫星数据。

设计优势

B+树的好处主要体现在查询性能上,由于B+树的中间节点没有卫星数据,所以同样大小的磁盘页可以容纳更多的节点元素,这就意味着,一次性加载到内存中的节点元素更多,从而使得查询时IO次数也更少。(举个简单的例子,一个磁盘页可以加载B树的100个节点元素,但是可以加载B+树的1000个节点元素,那么对于查找999这个数来说,B数需要10次IO,B+数只需要1次IO)

B+树相对B树的优点:

  • IO一次读数据是从磁盘上读的,磁盘容量是固定的,取数据量大小是固定的,非叶子节点不存储数据,节点小,磁盘IO次数就少。
  • B+树查询性能稳定,因为B+树的查询必须最终查找到叶子节点; 而B树,只要找到匹配元素即可,无论匹配元素处于中间节点,还是叶子节点。所以B树的查询性能并不稳定,最好情况是只查根节点,最坏情况是查到叶子节点
  • B+树的所有Data域在叶子节点,一般来说都会进行一个优化,就是将所有的叶子节点用指针串联起来(可以认为是链表),遍历叶子节点就能获取全部数据,这样就能进行区间访问了。 B树做范围查询,只能繁琐的遍历,但是B+树,只需要查到查找到范围下限以后,遍历叶子节点(有序链表)就可以了。

综合起来,B+树比B树的优势有三个:1、IO次数更少;2、查询性能更佳;3、范围查询简便

场景:Mysql索引

6、红黑树 VS B+树

红黑树的深度比B+树大,当数据量小时,可以把数据完全放到内存中,红黑树的时间复杂度比B树低(不用每次都查到叶子节点),如linux中进程的调度用的是红黑树,Java中HashMap、TreeMap、TreeSet(都在内存中操作)也都是用红黑树实现;

但是,当数据量大时,不能一次性把数据放到内存时,红黑树往往出现由于树的深度过大而造成磁盘IO读写过于频繁,进而导致效率低下;而B树因其读磁盘次数少,具有更快的速度。

到此这篇关于关于Java的二叉树、红黑树、B+树详解的文章就介绍到这了,更多相关Java二叉树、红黑树、B+树内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • Java数据结构之树和二叉树的相关资料

    目录 什么是树? 简单认识树 树的概念 树的表示形式 二叉树 二叉树的概念 特殊的二叉树 二叉树的性质 二叉树性质相关习题 实现二叉树的基本操作 了解二叉树的存储结构 简单构造一棵二叉树 二叉树的前序遍历 二叉树的中序 获取二叉树节点的个数 获取二叉树叶子节点个数 获取第k层的节点个数 获取二叉树的高度 检测值为value的元素是否存在 层序遍历 判断一棵二叉树是否为完全二叉树 什么是树? 简单认识树 在生活中,有杨树,石榴树,枣树,而在计算机中的树呢,是一种非线性结构,是由 n(n>=0) 个

  • java面试题解LeetCode27二叉树的镜像实例

    目录 正文 解题思路 方法一:递归法 方法二:辅助栈(或队列) 正文 LeetCode27. 二叉树的镜像 请完成一个函数,输入一个二叉树,该函数输出它的镜像. 例如输入: 4 /2 7 / \ /1 3 6 9 镜像输出: 4 /7 2 / \ /9 6 3 1 示例 1: 输入:root = [4,2,7,1,3,6,9] 输出:[4,7,2,9,6,3,1] 限制: 0 <= 节点个数 <= 1000 解题思路 方法一:递归法 根据二叉树镜像的定义,考虑递归遍历(dfs)二叉树,交换每个

  • 红黑树的插入详解及Javascript实现方法示例

    红黑树的性质 一棵满足以下性质的二叉搜索树是一棵红黑树 每个结点或是黑色或是红色. 根结点是黑色的. 每个叶结点(NIL)是黑色的. 如果一个结点是红色的,则它的两个子结点都是黑色的. 对每个结点,从该结点到其所有后代叶结点的简单路径上,均包含相同数目的黑色结点. 性质1和性质2,不用做过多解释. 性质3,每个叶结点(NIL)是黑色的.这里的叶结点并不是指上图中结点1,5,8,15,而是指下图中值为null的结点,它们的颜色为黑色,且是它们父结点的子结点. 性质4,如果一个结点是红色的(图中用白

  • 红黑树的使用详解

    (学习的参考资料主要是<算法导论>) 首先是红黑树的性质.一棵二叉查找树满足以下的红黑性质,则为一棵红黑树. 1)每个结点或是红的,或是黑的. 2)根结点是黑的. 3)每个叶结点(NIL)是黑的. 4)红结点的两个孩子都是黑的. 5)对任意结点,从它到其子孙结点所有路径上包含相同数目的黑结点. 初学时并不在意,但是仔细研究相关算法就会知道,算法都是围绕保持这些性质来进行的.性质5)保证了红黑树使用时的高效.定理证明了n个内结点的红黑树高度至多为2lg(n+1). 不同于一般二叉查找树,红黑树一

  • Java数据结构之红黑树的真正理解

    真正的帮助大家理解红黑树: 一.红黑树所处数据结构的位置: 在JDK源码中, 有treeMap和JDK8的HashMap都用到了红黑树去存储 红黑树可以看成B树的一种: 从二叉树看,红黑树是一颗相对平衡的二叉树 二叉树-->搜索二叉树-->平衡搜索二叉树--> 红黑树 从N阶树看,红黑树就是一颗 2-3-4树 N阶树-->B(B-)树 故我提取出了红黑树部分的源码,去说明红黑树的理解 看之前,理解红黑树的几个特性,后面的操作都是为了让树符合红黑树的这几个特性,从而满足对查找效率的O

  • Java数据结构之红黑树的原理及实现

    目录 为什么要有红黑树这种数据结构 红黑树的简介 红黑树的基本操作之旋转 红黑树之添加元素 红黑树之删除结点 删除结点没有儿子的情况 删除结点仅有一个儿子结点的情况 删除结点有两个儿子结点 红黑树动态可视化网站 红黑树参考代码 为什么要有红黑树这种数据结构 我们知道ALV树是一种严格按照定义来实现的平衡二叉查找树,所以它查找的效率非常稳定,为O(log n),由于其严格按照左右子树高度差不大于1的规则,插入和删除操作中需要大量且复杂的操作来保持ALV树的平衡(左旋和右旋),因此ALV树适用于大量

  • java算法实现红黑树完整代码示例

    红黑树 定义 红黑树(英语:Red–black tree)是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用途是实现关联数组. 红黑树的另一种定义是含有红黑链接并满足下列条件的二叉查找树: 红链接均为左链接:没有任何一个结点同时和两条红链接相连:该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同. 满足这样定义的红黑树和相应的2-3树是一一对应的. 旋转 旋转又分为左旋和右旋.通常左旋操作用于将一个向右倾斜的红色链接旋转为向左链接.对比操作前后,可以看出,该操作

  • Java数据结构之线段树详解

    目录 介绍 代码实现 线段树构建 区间查询 更新 总结 介绍 线段树(又名区间树)也是一种二叉树,每个节点的值等于左右孩子节点值的和,线段树示例图如下 以求和为例,根节点表示区间0-5的和,左孩子表示区间0-2的和,右孩子表示区间3-5的和,依次类推. 代码实现 /** * 使用数组实现线段树 */ public class SegmentTree<E> { private Node[] data; private int size; private Merger<E> merge

  • Go Java算法之二叉树的所有路径示例详解

    目录 二叉树的所有路径 方法一:深度优先遍历搜索(Java) 方法二:广度优先遍历(Go) 二叉树的所有路径 给你一个二叉树的根节点 root ,按 任意顺序 ,返回所有从根节点到叶子节点的路径. 叶子节点 是指没有子节点的节点. 示例 1: 输入:root = [1,2,3,null,5] 输出:["1->2->5","1->3"] 示例 2: 输入:root = [1] 输出:["1"] 提示: 树中节点的数目在范围 [1,

  • Java编程思想对象的容纳实例详解

    Java提供了容纳对象(或者对象的句柄)的多种方式,接下来我们具体看看都有哪些方式. 有两方面的问题将数组与其他集合类型区分开来:效率和类型.对于Java来说,为保存和访问一系列对象(实际是对象的句柄)数组,最有效的方法莫过于数组.数组实际代表一个简单的线性序列,它使得元素的访问速度非常快,但我们却要为这种速度付出代价:创建一个数组对象时,它的大小是固定的,而且不可在那个数组对象的"存在时间"内发生改变.可创建特定大小的一个数组,然后假如用光了存储空间,就再创建一个新数组,将所有句柄从

  • Java集合框架之Set和Map详解

    目录 Set接口 HashSet TreeSet Map接口 HashMap TreeMap Set接口 set接口等同于Collection接口,不过其方法的行为有更严谨的定义.set的add方法不允许增加重复的元素.要适当地定义set的equals方法:只要俩个set包含同样的元素就认为它们是相同的,而不要求这些元素有相同的顺序.hashCode方法的定义要保证包含相同元素的俩个set会得到相同的散列码. --Java核心技术 卷一 public interface Set<E> exte

  • java集合类源码分析之Set详解

    Set集合与List一样,都是继承自Collection接口,常用的实现类有HashSet和TreeSet.值得注意的是,HashSet是通过HashMap来实现的而TreeSet是通过TreeMap来实现的,所以HashSet和TreeSet都没有自己的数据结构,具体可以归纳如下: •Set集合中的元素不能重复,即元素唯一 •HashSet按元素的哈希值存储,所以是无序的,并且最多允许一个null对象 •TreeSet按元素的大小存储,所以是有序的,并且不允许null对象 •Set集合没有ge

随机推荐

其他