数据结构中的树有多种形式,如:二叉树,二叉搜索树,平衡二叉搜索树,红黑树,线段树,trie树,二叉堆等

每一种树结构都是由最基础的树演化而来,每种树的产生都是为了解决某些问题,所以学习的过程也是先学习基础树结构的概念,之后会按照演化顺序进行讲解

树是由有限个结点(假设为n)构成的集合

比如下面这棵树:

基础概念:

父节点:A是B的父节点,A也是C的父节点,B是D的父节点

子节点:B是A的子节点,C是A的子节点,G是C的子节点

兄弟节点:B,C拥有共同的父节点A,所以B和C叫兄弟节点

根节点:没有父节点的节点,叫做根节点,如图中的A就是根节点,一棵树只有一个根节点

叶子节点:没有子节点的节点,叫做叶子节点,如图中的D,E,F,G节点

二叉树

二叉树是众多树型结构中的一种

顾名思义,二叉树中的每个节点最多只能有两个节点,此为二叉,两个节点分别是左子节点和右子节点 ,每个子节点也可是一棵树,也可称为左子树和右子树

上图中的三棵树都属二叉树,而二叉树中又有两种比较特殊的树:满二叉树和完全二叉树

满二叉树:

​ 在一棵二叉树中,如果每个结点都存在左子节点和右子节点,并且所有的叶子节点都在同一层中,这种二叉树叫满二叉树,如上图中的树1

完全二叉树:

​ 在一棵二叉树中,如果叶子节点都在最底下两层,最后一层叶子节点都靠左排列,并且除了最后一层,其他层的节点个数都要达到最大,这种二叉树叫做完全二叉树,如上图中的树2

满二叉树也是一种特殊的完全二叉树

二叉树的存储

在了解了二叉树的概念之后,我们思考一下该使用何种数据结构如何进行二叉树的存储?

顺序存储结构

使用数组存储二叉树节点

以一颗完全二叉树为例,如果父节点的下标为i,则父节点的左子节点为2*i,右子节点为`2*i+1`,所以为了方便计算子节点,我们将数组0位置空置,树中节点从根节点开始从数组下标为1的位置进行顺序插入,这样进行节点计算时较为方便

完全二叉树的可以按顺序的填满数组,只浪费数组下标为0的那块内存,那我们接下来看下非完全二叉树的顺序存储

我们根据计算节点的公式,可以算出所有子节点对应数组的下标位置,树5这棵二叉树由于B节点没有左子节点,可以计算出这个缺失的节点下标位置为4,这样下标为4的内存就浪费了,如上图

对于这种内存的浪费,树5其实并不明显,可以想象一下如果一棵二叉树有大量的子节点缺失就会导致浪费大量的内存空间

所以如果二叉树是一颗完全二叉树,我们使用数组进行存储,是最节省内存的一种方式

链式存储

那非完全二叉树有没有什么好的存储方式那?

使用链表存储二叉树节点

使用链表存储节点的时候,链表的每个节点包括三个字段:二叉树的节点数据,二叉树节点的左子节点的引用,下图中简称左引用,二叉树节点的右子节点的引用,下图中简称右引用

使用链表方式存储比使用数组方式存储需要额外存储二叉树节点的左右子节点的引用,但是对于存储大量缺失子节点的二叉树,无疑是比数组更优的一种方法

二叉树的遍历

在已经了解了二叉树的存储方式后,我们看一下如何遍历二叉树

常见的遍历方式有四种:前序遍历,中序遍历,后序遍历,层次遍历

前序遍历

对于树中的任意节点来说,先打印这个节点,然后再打印它的左子节点,最后打印它的右子节点

以树6为例:

  1. 从根节点出发,首先输出这个节点,输出A
  2. 向左到达B,输出B,之后继续向左到达D,输出D,在到达H,输出H
  3. H是叶子节点,所以返回D,但是D已经输出过了,所以访问D的右子节点I,输出I
  4. I是叶子节点,所以继续返回到B,访问B的右子节点E,输出E
  5. 依照这种方式进行输出

输出结果为:A->B->D->H->I->E->C->F->G

中序遍历

对于树中的任意节点来说,先打印它的左子节点,然后再打印它本身,最后打印它的右子节点

以树6为例:

  1. 从根节点出发,先不输出他本身,继续向左访问到B,在向左访问到D,再到H
  2. H没有子节点,因此输出自己,再返回到D,输出D,之后访问D的右子节点I,输出I
  3. 之后再返回到D,因为D已经输出,在往上返回,到B,输出B,之后访问B的右子节点E,输出E
  4. 依照这种方式进行输出

输出结果为:H->D->I->B->E->A->F->C->G

后序遍历

对于树中的任意节点来说,先打印它的左子节点,然后再打印它的右子节点,最后打印这个节点本身

以树6为例:

  1. 从根节点出发,首先输出自己,继续向左访问到B,直到叶子节点H
  2. H无子节点,输出H,返回到D,继续访问D的右子节点I,I无子节点,输出I
  3. 再次返回到D,此时D的子节点都已输出,所以此时输出D,继续返回到B,访问B的右子节点E
  4. E无子节点,故输出E
  5. 依照这种方式进行输出

输出结果为:H->I->D->E->B->F->G->C->A

层次遍历

从二叉树的根结点开始,从上至下逐层遍历,在同一层,则按从左至右的顺序对每个结点逐个访问

以树6为例:

输出结果为:A->B->C->D->E->F->G->H->I

二叉搜索树

概念:在二叉搜索树中,任意一个节点,其左子树中的每个节点的值,都要小于这个节点的值,其右子树中的每个节点的值都大于这个节点的值

如下图:

查找操作

因为二叉搜索树中任意一个节点的左子树中的节点都小于这个节点的值,右子树中的节点都大于这个节点的值,查询时从根节点开始,如果查询的值小于根节点的值,就去左子树中查询,如果大于根节点的值,就去右子树中查询

在树7中以查找4为例:

插入操作

插入操作跟查找操作类似,都是根据二叉查找树的特性进行查询可以插入新节点的位置

在树7中以插入12为例:

删除数据

删除节点比较复杂,主要是根据要删除的子节点数量进行不同处理

情况1:删除的节点没有子节点,这种情况直接找到节点删除即可

比如删除节点4:

情况2:删除的节点有一个子节点,删除节点,移动其子节点

比如删除节点3:

情况3:删除的节点有两个子节点,首先需要找到右子树中最小的节点,将当前节点替换为最小节点,然后删除最小节点

比如删除节点5:

退化为链表

当二叉搜索树是满二叉树或完全二叉树时,其查找,添加,删除的时间复杂度是log(n),当一颗二叉搜索树极度不平衡时,其操作的时间复杂度退化为O(n)

比如向二叉搜索树中按顺序添加 1,2,3,4 ,其二叉搜索树的结构如下图:

这时二叉搜索树退化为链表,即便不是退化为链表这种极端情况,只要有左右两颗子树不平衡的情况在(实际上使用时绝大部分都是不平衡的),其操作的时间复杂度就会退化

平衡二叉搜索树(AVL)

为了解决将有顺序数据添加到二叉查找树时导致二叉搜索树性能变差的情况出现,就需要二叉搜索树可以自己进行自平衡操作,进而使二叉搜索树达到平衡状态,在进行自平衡操作之前,需要了解下平衡的概念

平衡二叉搜索树的平衡

对于任意一个节点,左右子树的高度之差的绝对值不超过1,那么这棵二叉搜索树是平衡的

节点高度:左右子树最高的节点高度+1

平衡因子:左右子树的高度差的绝对值,所以一个平衡二叉搜索树的任意一个节点的平衡因子不能大于1

在二叉搜索树的基础上,满足平衡条件的二叉树,就是平衡二叉搜索树,如下图:

使用这种方式,我们就可以计算出二叉搜索树是否是平衡的,树8的任意一个节点的平衡因子都在-1,0,1之间,所以树8是平衡二叉搜索树

平衡二叉搜索树的自平衡

一颗平衡二叉搜索树当添加节点的时候,必须更新其父节点的平衡因子,可分为两种情况:

  1. 递归更新父节点的平衡因子,直到根节点
  2. 当父节点的平衡因子为0时其祖先节点的平衡因子不会发生改变,停止更新

根据添加的节点位置可以分为4种情况:

情况1:添加的节点在左子树的左边,简称为LL

  1. 添加的节点F为D节点的左子节点
  2. 递归更新父节点的平衡因子,A节点额平衡因子为2
  3. 因此以A节点为根节点的子树需要进行自平衡操作
  4. 对A节点进行右旋转操作

此时自平衡操作完成,二叉搜索树重新变为平衡二叉搜索树

情况2:添加的节点在右子树的右边,简称为RR

  1. 添加节点F为E的右子节点
  2. 递归更新父节点的平衡因子,A节点额平衡因子为2
  3. 因此以A节点为根节点的子树需要进行自平衡操作
  4. 对A节点进行左旋转操作
情况3:添加的节点在左子树的右边,简称为LR

首先我们尝试使用LL解决方法,对A节点进行右旋转,不过很明显平衡之后的二叉搜索树肯定不是平衡的,B的平衡因子还是2

所以直接使用右旋转操作是行不通的

针对这种情况,需要先将LR转为LL,之后就可以进LL的自平衡操作了,具体流程如下

  1. 对B进行左旋转,使LR转化为LL
  2. 转化为LL后,使用处理LL的自平衡操作,对A进行右旋转

无论添加的节点F是E的左子节点还是右子节点,对以上整个自平衡的操作并无影响

情况4:添加的节点在右子树的左边,简称为RL

这种情况和LR情况类似,需要先将RL转为RR,之后进行RR的自平衡操作即可

  1. 对C进行右旋转,使RL转换为RR
  2. 转化为RR之后,使用RR的自平衡操作,对A进行左旋转
总结一下自平衡转换的规则

如果是LL,对不平衡的节点进行右旋转

如果是RR,对不平衡的节点进行左旋转

如果是LR,先左旋,变成LL,在右旋转

如果是RL,先右旋,变成RR,在左旋转

L对应右旋转,R对应左旋转

本来想一篇把开头写的二叉树,二叉搜索树,平衡二叉搜索树,红黑树,线段树,trie树,二叉堆等都讲明白,但是写到平衡二叉搜索树的时候发现篇幅太长了,所以剩下的树放到下一篇去写

画图不易,欢迎点赞

有问题可以评论,一起讨论