树、二叉树、AVL树，B树基础学习

一、树的基本概念

树是一种数据结构，它是由n（n>1）个有限节点组成的一个具有层次关系的集合。

树的基本概念

1、双亲：若有一个结点有子树，那么该结点就称为子树根的“双亲”。

2、孩子结点：子树的根称为改子树双亲结点的“孩子结点”。

3、兄弟结点：有相同的双亲的结点称为“兄弟结点”。

4、结点的度：结点拥有的子树的数目。

5、叶子结点：度为0的结点。

6、分支结点：度不为0的结点

6、树的度：数中结点的最大的度

7、层次：根节点层次为1，其余节点的层次等于该节点的双亲节点的层次+1.

8、树的高度：数中结点的最大层次

9：森林：0个或多个不想交的树的组成。对森林加上一个根，森林即成为树；删去根，树即成为森林。

二、二叉树的基本概念

定义：二叉树是每个结点最多有两个子树的树的结构。通常子树被称作“左子树”和“右子树”。

二叉树特点

由二叉树定义以及图示分析得出二叉树有以下特点：

• 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

二叉树性质

• 在二叉树的第i层上最多有2i-1 个节点 。（i>=1）
• 二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
• n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。
• 在完全二叉树中，具有n个节点的完全二叉树的最小深度为[log2n]+1，其中[log2n]是向下取整。
• 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：

(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。
           

斜树

斜树：所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

满二叉树

满二叉树：在一棵二叉树中。如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树的特点有：

1）叶子只能出现在最下一层。出现在其它层就不可能达成平衡。

2）非叶子结点的度一定是2。

3）在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

完全二叉树：对一颗具有n个结点的二叉树按层编号，如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同，则这棵二叉树称为完全二叉树。

特点：

1）叶子结点只能出现在最下层和次下层。

2）最下层的叶子结点集中在树的左部。

3）倒数第二层若存在叶子结点，一定在右部连续位置。

4）如果结点度为1，则该结点只有左孩子，即没有右子树。

5）同样结点数目的二叉树，完全二叉树深度最小。

注：满二叉树一定是完全二叉树，但反过来不一定成立。

二叉树的遍历

1、先序遍历：

对于每一个结点都有：

（1）先访问根节点。

（2）再访问左子树。

（3）后访问右子树。

2、中序遍历

对于每一个结点都有：

（1）先访问左子树。

（2）再访问根节点。

（3）后访问右子树。

3、后序遍历

对于每一个结点都有

（1）先访问左子树。

（2）再访问右子树。

（3）后访问根结点。

二叉搜索树

定义

二叉搜索树又称二叉查找树，亦称为二叉排序树。设x为二叉查找树中的一个节点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个节点，则key[y] <= key[x]；如果y是x的右子树的一个节点，则key[y] >= key[x]。

性质

（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；

（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；

（3）左、右子树也分别为二叉搜索树；

如图为一颗二叉搜索树：

节点结构

二叉树的节点结构通常包含三部分，其中有：左孩子的指针，右孩子指针以及数据域。节点的图示如下：

创建二叉搜索树

现有序列：A = {61, 87, 59, 47, 35, 73, 51, 98, 37, 93}。根据此序列构造二叉搜索树过程如下：

（1）i = 0，A[0] = 61，节点61作为根节点；

（2）i = 1，A[1] = 87，87 > 61，且节点61右孩子为空，故81为61节点的右孩子；

（3）i = 2，A[2] = 59，59 < 61，且节点61左孩子为空，故59为61节点的左孩子；

（4）i = 3，A[3] = 47，47 < 59，且节点59左孩子为空，故47为59节点的左孩子；

（5）i = 4，A[4] = 35，35 < 47，且节点47左孩子为空，故35为47节点的左孩子；

（6）i = 5，A[5] = 73，73 < 87，且节点87左孩子为空，故73为87节点的左孩子；

（7）i = 6，A[6] = 51，47 < 51，且节点47右孩子为空，故51为47节点的右孩子；

（8）i = 7，A[7] = 98，98 < 87，且节点87右孩子为空，故98为87节点的右孩子；

（9）i = 8，A[8] = 93，93 < 98，且节点98左孩子为空，故93为98节点的左孩子；

创建完毕后如图中的二叉搜索树：

查找

查找流程：

  （1）如果树是空的，则查找结束，无匹配。

  （2）如果被查找的值和节点的值相等，查找成功。

  （3）如果被查找的值小于节点的值，递归查找左子树，

  （4）如果被查找的值大于节点的值，递归查找右子树，

插入

插入流程：

（1）先检测该元素是否在树中已经存在。如果已经存在，则不进行插入；

（2）若元素不存在，则进行查找过程，并将元素插入在查找结束的位置。

删除

（1）删除节点为叶子节点

  删除叶子节点的方式最为简单，只需查找到该节点，直接删除即可。例如删除图中的叶子节点37、节点51、节点60、节点73和节点93的方式是相同的。

（2） 删除的节点只有左子树

  删除的节点若只有左子树，将节点的左子树替代该节点位置。例如：删除图中的98节点：

（3）删除的节点只有右子树

  删除的节点若只有右子树，将节点的右子树替代该节点位置。这种情况与删除左子树处理方式类似，不再赘述。

（4） 删除的节点既有左子树又有右子树。

  若删除的节点既有左子树又有右子树，这种节点删除过程相对复杂。其流程如下：

 （1）遍历待删除节点的左子树，找到其左子树中的最大节点，即删除节点的前驱节点；

 （2）将最大节点代替被删除节点；

 （3）删除左子树中的最大节点；

 （4）左子树中待删除最大节点一定为叶子节点或者仅有左子树。按照之前情形删除即可。

注：同样可以使用删除节点的右子树中最小节点，即后继节点代替删除节点，此流程与使用前驱节点类似。

平衡二叉树

定义

平衡二叉树定义(AVL)：它或者是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1，且它的左子树和右子树都是一颗平衡二叉树。

一棵AVL树有如下必要条件:

1. 条件一：它必须是二叉查找树。
2. 条件二：每个节点的左子树和右子树的高度差至多为1。

图一中左边二叉树的节点45的左孩子46比45大，不满足二叉搜索树的条件，因此它也不是一棵平衡二叉树。

右边二叉树满足二叉搜索树的条件，同时它满足条件二，因此它是一棵平衡二叉树。

左边二叉树的节点45左子树高度2，右子树高度0，左右子树高度差为2-0=2，不满足条件二；

右边二叉树的节点均满足左右子树高度差至多为1，同时它满足二叉搜索树的要求，因此它是一棵平衡二叉树。

注：AVL树的查找、插入、删除操作在平均和最坏的情况下都是O（logn），这得益于它时刻维护着二叉树的平衡。

AVL树相关概念

平衡因子：将二叉树上节点的左子树高度减去右子树高度的值称为该节点的平衡因子BF(Balance Factor)。

最小不平衡子树：距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树.

在图三中，左边二叉树的节点45的BF = 1，插入节点43后，节点45的BF = 2。节点45是距离插入点43最近的BF不在[-1,1]范围内的节点，因此以节点45为根的子树为最小不平衡子树。

AVL树的平衡调整

整个实现过程是通过在一棵平衡二叉树中依次插入元素(按照二叉排序树的方式)，若出现不平衡，则要根据新插入的结点与最低不平衡结点的位置关系进行相应的调整。分为LL型、RR型、LR型和RL型4种类型，各调整方法如下(下面用A表示最低不平衡结点)：

1. LL型调整：

由于在A的左孩子(L)的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1增至2。下面图1是LL型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B顺时针旋转一样。

LL型调整的一般形式如下图2所示，表示在A的左孩子B的左子树BL(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。这种情况调整如下：①将A的左孩子B提升为新的根结点；②将原来的根结点A降为B的右孩子；③各子树按大小关系连接(BL和AR不变，BR调整为A的左子树)。

2.RR型调整：

由于在A的右孩子®的右子树®上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。图3是RR型的最简单形式。显然，按照大小关系，结点B应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡，A结点就好像是绕结点B逆时针旋转一样。

RR型调整的一般形式如下图4所示，表示在A的右孩子B的右子树BR(不一定为空)中插入结点(图中阴影部分所示)而导致不平衡( h 表示子树的深度)。这种情况调整如下：

• 将A的右孩子B提升为新的根结点
• 将原来的根结点A降为B的左孩子
• 各子树按大小关系连接(AL和BR不变，BL调整为A的右子树)。

  

  3. LR型调整

由于在A的左孩子(L)的右子树®上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由1变为2。图5是LR型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。

LR型调整的一般形式如下图6所示，表示在A的左孩子B的右子树(根结点为C，不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。这种情况调整如下：①将B的左孩子C提升为新的根结点；②将原来的根结点A降为C的右孩子；③各子树按大小关系连接(BL和AR不变，CL和CR分别调整为B的右子树和A的左子树)。

4. RL型调整：

由于在A的右孩子®的左子树(L)上插入新结点，使原来平衡二叉树变得不平衡，此时A的平衡因子由-1变为-2。图7是RL型的最简单形式。显然，按照大小关系，结点C应作为新的根结点，其余两个节点分别作为左右孩子节点才能平衡。

RL型调整的一般形式如下图8所示，表示在A的右孩子B的左子树(根结点为C，不一定为空)中插入结点(图中两个阴影部分之一)而导致不平衡( h 表示子树的深度)。这种情况调整如下：①将B的左孩子C提升为新的根结点；②将原来的根结点A降为C的左孩子；③各子树按大小关系连接(AL和BR不变，CL和CR分别调整为A的右子树和B的左子树)。

平衡二叉树实现的实例

选取一组数据分别为2，1，0，3，4，5，6，9，8，7的10个结点来构造平衡二叉树。

• 首先数据为2的结点作为根结点插入，接着插入1，仍是平衡的，再插入0是，2的平衡因子变为2，此时出现了不平衡，因此需要进行调整，最低不平衡结点为2，属于LL型，调整过程如图1所示。

  

• 接着插入3，是平衡的，再插入4，此时出现了不平衡，结点 1 和 2 的平衡因子都为

  -2，结点2为最低不平衡结点，属于RR型，调整过程如图2所示

  

• 接着插入5，此时结点 1 的平衡因子为 -2，导致不平衡，结点1为最低不平衡结点，属于RR型，调整如图3所示。

  

• 接着插入6，此时结点4的平衡因子为 -2，导致不平衡，结点4为最低不平衡结点，属于RR型，调整如图4所示。

  

• 接着插入9，是平衡的，再插入8，此时结点 3、5、6 的平衡因子都为 -2，导致不平衡，结点6为最低不平衡结点，属于RL型，调整如图5所示。

  

• 插入7，此时结点3、5的平衡因子为 -2，导致不平衡，最低不平衡结点为5，属于RL型，调整如图6所示。

  

B（B-）树

B-树，即为B树。因为B树的原英文名称为B-tree，而国内很多人喜欢把B-tree译作B-树，其实，这是个非常不好的直译，很容易让人产生误解。如人们可能会以为B-树是一种树，而B树又是一种树。而事实上是，B-tree就是指的B树，目前理解B的意思为平衡。

　　B树的出现是为了弥合不同的存储级别之间的访问速度上的巨大差异，实现高效的 I/O。平衡二叉树的查找效率是非常高的，并可以通过降低树的深度来提高查找的效率。但是当数据量非常大，树的存储的元素数量是有限的，这样会导致二叉查找树结构由于树的深度过大而造成磁盘I/O读写过于频繁，进而导致查询效率低下。另外数据量过大会导致内存空间不够容纳平衡二叉树所有结点的情况。B树是解决这个问题的很好的结构

概念

　　首先，B树不要和二叉树混淆，在计算机科学中，B树是一种自平衡树数据结构，它维护有序数据并允许以对数时间进行搜索，顺序访问，插入和删除。B树是二叉搜索树的一般化，因为节点可以有两个以上的子节点。[1]与其他自平衡二进制搜索树不同，B树非常适合读取和写入相对较大的数据块（如光盘）的存储系统。它通常用于数据库和文件系统。

定义

B树是一种平衡的多分树，通常我们说m阶的B树，它必须满足如下条件：

• 每个节点最多只有m个子节点。
• 每个非叶子节点（除了根）具有至少⌈ m/2⌉子节点。
• 如果根不是叶节点，则根至少有两个子节点。
• 具有k个子节点的非叶节点包含k -1个键。
• 所有叶子都出现在同一水平，没有任何信息（高度一致）。

什么是B树的阶 ？

B树中一个节点的子节点数目的最大值，用m表示，假如最大值为10，则为10阶，如图

所有节点中，节点【13,16,19】拥有的子节点数目最多，四个子节点（灰色节点），所以可以定义上面的图片为4阶B树。

什么是根节点 ？

节点【10】即为根节点，特征：根节点拥有的子节点数量的上限和内部节点相同，如果根节点不是树中唯一节点的话，至少有俩个子节点（不然就变成单支了）。在m阶B树中（根节点非树中唯一节点），那么有关系式2<= M <=m，M为子节点数量；包含的元素数量 1<= K <=m-1,K为元素数量。

什么是叶子节点？

节点【1,2】、节点【11,12】等最后一层都为叶子节点，叶子节点对元素的数量有相同的限制，但是没有子节点，也没有指向子节点的指针。特征：在m阶B树中叶子节点的元素符合（m/2）-1<= K <=m-1。

B树的插入

B树的插入是指插入一条记录，如果B树已存在需要插入的键值时，用新的值替换旧的值；若B树不存在这个值时，则是在叶子结点进行插入操作。

对高度为h的m阶B树，新结点一般插第h层。通过检索可以确定关键码应插入的位置，

1）若该结点中关键码个数小于m-1，则直接插入就可

2）若该结点中关键码个数等于m-1，则将引起结点的分裂，以中间的关键码为界将结点一分为二，产生了一个新的结点，并将中间关键码插入到父结点中；

重复上述过程，最坏情况一直分裂到根结点， 建立一个新的根结点，整个B树就增加一层。

举例如下：

》〉》〉下面以5阶B树举例，根据B树的定义，结点最多有4个值，最少有2个值。

序列（39，22，97，41，53，13，21，40，30，27，33，36，24，34，35，26，17，28，29，31，32）

a）在空树插入39，此时就有一个值，根结点也是叶子结点

b）继续插入22，97和41值，根结点变为4个值，符合要求

c）插入53值

插入之后发现超过结点最多只有4个值，所以要以中间值进行分开，分开后当前结点要指向父结点，分裂之后，发现符合要求

d）插入13，21，40，同样造成分裂，

e）紧接着插入30，27，33，36，24，34，35

f）将26再次插入进去

发现有5个值，超过B树的定义，需要以27为中心分裂，27进军父结点

发现父结点也超过4个，再次分裂

g）最后插入17，28，29，31，32的记录

B树的删除

B树删除：首先要查找该值是否在B树中存在，如果存在，判断该元素是否存在左右孩子结点，如果有，则上移孩子结点中的相近结点（左孩子最右边的结点或者有孩子最左边的结点）到父结点中，然后根据移动之后的情况；如果没有，进行直接删除；如果不存在对应的值，则删除失败。

1）如果当前要删除的值位于非叶子结点，则用后继值覆盖要删除的值，再用后继值所在的分支删除该后继值。（该后继值必须位于叶子结点上）

2）该结点值个数不小于Math.ceil(m/2)-1（取上线函数），结束删除操作，否则下一步

3）如果兄弟结点值个数大于Math.ceil(m/2)-1，则父结点中下移到该结点，兄弟的一个值上移，删除操作结束。

将父结点的key下移与当前的结点和他的兄弟姐妹结点key合并，形成一个新的结点，

有些结点可能有左兄弟，也有右兄弟，我们可以任意选择一个兄弟结点即可。

》〉》〉下面以5阶B树举例进行删除，根据B树的定义，结点最多有4个值，最少有2个值。

a）原始状态

b）在上面的B树删除21，删除之后结点个数大于等于2，所以删除结束

c）删除27之后为

27处于非叶子结点，用27的后继替换。也即是28替换27，然后在右孩子结点删除28，如上。

发现删除，当前叶子结点的记录的个数已经小于2，而兄弟结点中有3个记录我们可以从兄弟结点中借取一个key，父结点中的28就下移，兄弟结点中的26就上移,删除结束，结果如下

d）删除32

删除之后发现，当前结点中有key，而兄弟都有两个key，所以只能让父结点的30下移到和孩子一起合并，成为新的结点，并指向父结点，经拆封发现符合要求

哈夫曼树

哈夫曼树的构造

注意：哈夫曼树并不唯一，但带权路径长度一定是相同的。

（1）8个结点的权值大小如下：

（2）从19，21，2，3，6，7，10，32中选择两个权小结点。选中2，3。同时算出这两个结点的和5。

（3）从19，21，6，7，10，32，5中选出两个权小结点。选中5，6。同时计算出它们的和11。

（4）从19，21，7，10，32，11中选出两个权小结点。选中7，10。同时计算出它们的和17。

（BTW：这时选出的两个数字都不是已经构造好的二叉树里面的结点，所以要另外开一棵二叉树；或者说，如果两个数的和正好是下一步的两个最小数的其中的一个，那么这个树直接往上生长就可以了，如果这两个数的和比较大，不是下一步的两个最小数的其中一个，那么就并列生长。）

（5）从19，21，32，11，17中选出两个权小结点。选中11，17。同时计算出它们的和28。

（6）从19，21，32，28中选出两个权小结点。选中19，21。同时计算出它们的和40。另起一颗二叉树。

（7）从32，28， 40中选出两个权小结点。选中28，32。同时计算出它们的和60。

（8）从 40， 60中选出两个权小结点。选中40，60。同时计算出它们的和100。 好了，此时哈夫曼树已经构建好了。