Java知识点回顾系列(Tree)

一、二叉树

1、二叉树的基本定义

二叉树是每个节点最多有两个子树的树结构。常见的基本形态有:
①二叉树可以是空集②跟可以有空的左子树或右子树③左右子树都为空

2、二叉树的五种基本性质

① 二叉树的第i层上的节点数最多为2^(i-1) i>=1
例如:第一层最多有2^(1-1)=1个节点,也就是跟节点
第三层最多有2^(3-1)=4个节点




② 深度为k的二叉树,至多包含(2^k)-1个节点 k>=1
如下图:
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

2、特别的二叉树
完全二叉树:对于深度为k,有n个节点的二叉树,当且仅当每一个节点都与深度为k的满二叉树中编号从1至n的节点都一一对应
在这里插入图片描述
满二叉树: 除了叶节点以外,每个节点都有左右子叶且叶子节点都处在最底层的二叉树
在这里插入图片描述
3、常见的存储方式
数组最大的特点是:内存是连续的,数组的下标通常是从0开始的,因此也有了它方便查询的性质,那怎样用一个数据存储二叉树呢?

在这里插入图片描述
为了表示节点之间的关系,引入链表结构,用左右两个指针分别指向左节点和右节点,这样就可以串联整个二叉树了。如下图所示:
在这里插入图片描述
4、二叉树的遍历
常见的有下面4中遍历方式:
①先序遍历:访问根节点,访问当前节点的左节点,若无左节点则访问右节点
在这里插入图片描述
②中序遍历:访问当前节点的左节点,跟节点,右节点
在这里插入图片描述
③后序遍历:从根节点开始,依次访问该节点的左右节点
在这里插入图片描述
④层级遍历:自顶向下一层一层遍历
在这里插入图片描述

二、二叉排序树

二叉排序树(Binary Sort Tree)又称二叉查找树、二叉搜索树。它或者是一棵空树;或者是具有下列性质的二叉树:
(1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(3)左、右子树也分别为二叉排序树;
在这里插入图片描述
其高度与树中结点个数n成对数关系,检索的时间开销为O(logn)。但是很有可能检索的时间将变成线性的情况。
在这里插入图片描述

三、哈夫曼树

哈夫曼树也叫做最优二叉树,一种带权路径长度最短的二叉树。那么什么是树的带权路径长度,它是树中所有的叶子节点的权值乘上其根节点的路径长度。
如何构造哈夫曼树?
在这里插入图片描述

四、平衡二叉树

二叉排序树出现了线性的情况,所以需要想办法避免那种情况发生。这样两位爷爷发明了平衡二叉排序树,又叫AVL树。那么是怎么定义的呢?平衡二叉排序树是一类特殊的二叉排序树,它或者为空树,或者其左右子树都是平衡二叉排序树,而且其左右的子数高度之差绝对值不超过1.为了保证相对平衡,每次插入元素都会做相应的旋转,那么下面来看看这几种情况。

1、平衡二叉树与非平衡二叉树
在这里插入图片描述
2、平衡调整
LL型调整:如下图,因为在A的左孩子的左孩子插入新的节点,导致A的平衡因子从1变为2,不在满足根本性质[-1,1],所以需要通过旋转。显然,按照大小关系,结点B应作为新的根结点,其余两个节点分别作为左右孩子节点才能平衡,这样看来,仿佛A结点绕结点B顺时针旋转一样。
在这里插入图片描述
RR型调整:如下图,因为在元素5的右孩子的右孩子插入新的节点,导致元素5的平衡因子从-1变为-2,不在满足根本性质[-1,1],所以需要通过旋转。显然,按照大小关系,结点元素7应作为新的根结点,其余两个节点分别作为左右孩子节点才能平衡,这样看来,仿佛节点元素5绕结点元素7逆时针旋转一样。
在这里插入图片描述

五、B树和B+树

小伙伴们有没有想过,为什么很多数据库中的索引采用B+树呢?以及为什么索引是放在磁盘上。
1、B树
如果使用二叉树作为索引的底层实现结构,树会变得很高,从而增加了磁盘的IO次数,从而影响数据查询时间。因此为了降低其高度,让一个节点有多个子节点,B树就诞生了。如图:
在这里插入图片描述
通常的,一个M阶的B树有如下性质:
在这里插入图片描述
上图为三阶图,查看磁盘3,关键字为20,30.三个孩子分别是(18,19),(22,25),(32,36).其中(18,19)小于20,(22,25)在(20,30)之间,(32,36)大于30.

那么在查找搜索的过程中,是怎样的访问过程呢?假设查找元素7
与根节点比较,得到指针p1
根据p1来到磁盘2,关键字为(9,15),发现小于9,得到指针p1
根据p1来到磁盘5,关键字为(7,8),发现正好有7.

2、B+树
前文介绍了二分查找方法为O(log2n),但是会出现深度非常大退化为链表,其查找数据的时间复杂度变为O(n)。从而就出现了平衡二叉树。
在这里插入图片描述
性质:
有m个孩子的节点就有m个关键字(孩子数量=关键字数),而在B树中孩子数量=关键字数+1

非叶子节点关键字也会出现在子节点中,而且子节点中为所有关键字的最大或最小
非叶子节点只是用来索引,不保存数据的记录。在B树中,非叶子节点既保存索引也保存数据记录。

所有关键字都存在于叶子节点,叶子节点构成有序链表,而且关键字按照从大到小或者从小到大顺序连接。
优点:
因为B+树中间节点没有关键字,所以同样大小的磁盘页可以容纳更多的节点元素,也就是说在相同的情况下,B+树更加的矮胖,这样的话,IO的次数也就比较少。
B+树的查询相比B树更加稳定,因为B+树的查询是必须到叶子节点,而B树有可能在中间节点,也可能非中间节点。
B+树叶子节点形成了有序链表,更加有利于范围的查询

那么其查询的过程是什么样的呢?我们假设查询元素13
首先与根节点的关键字(10,18,40)比较,13在10和18之间,此时得到P1指针
磁盘2中的关键字为(10,12,15),这时15大于13,所有磁盘6
关键字为(12,13),找到13

六、红黑树

虽然在大部分情况下,面试中不会让你写出来,在面试中还是经常会问原理的内容,所以了解了解更稳妥(比如c++中的很荣STL底层就是基于它),时间复杂度是O(lgn)。其基本概念如下。
红黑树的性质
首先红黑树的节点要么是红色,要么是黑色。

1 根节点是黑色的
2 每个叶子节点是黑色的且不存储数据
3 任何相邻的节点不能同时为红色
4 每个节点,从该节点到可达的叶子节点的所有路径,其黑色节点的数目相同。

坚持原创技术分享,您的支持将鼓励我继续创作!