下载掌阅APP，畅读海量书库
立即打开
树（Tree）是n（n≥0）个结点组成的有限集合。当n=0时，称为空树。当n>0时，称为非空树。
非空树的特性如下：
（1）有且仅有一个根（Root）结点。
（2）当n>1时，除根结点以外的其他结点可以分为m（m>0）个互不相交的有限集合S1,S2,S3,...,Sm，每个集合本身也是一棵树，这些树称为根结点的子树。
从以上非空树的特性可知，树结构是一个递归的过程。根结点拥有子树，子树中的每个结点也可以拥有子树。如图2-32所示为一棵普通的树。
图2-32 普通树示意图
树实现有多种，其中有一些通用的概念。
结点拥有的子树的数量称为结点的度。在图2-32所示的树中，根结点A的度是2，结点B的度是3，结点C的度是2。
结点子树的根结点称作该结点的子结点（也可以称作孩子结点）。相应地，该结点称作孩子结点的父结点（也可以称作双亲结点）。在图2-32所示的树中，结点B和结点C都是结点A的孩子结点。结点A称为结点B和结点C的父结点。
同一个父结点的所有子结点之间互相称作兄弟结点。在图2-32所示的树中，结点B和结点C互为兄弟结点。
从根结点开始，根结点称为第1层，根结点的孩子称为第2层，以此类推。结点的层次如图2-33所示。
图2-33 结点的层次示意图
树中结点的最大层次称为树的高度（或者称为深度）。在图2-33所示的树中，树的高度为4。
如果一个结点没有任何子结点，那么称这个结点为叶结点。在图2-33所示的树中，结点D、结点E、结点F、结点H、结点I、结点J都是叶结点。
二叉树是n（n≥0）个结点组成的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的子树组成，这两棵子树分别称为根结点的左子树和右子树。二叉树如图2-34所示。
图2-34 二叉树示意图
二叉树的特点如下：
（1）二叉树中每个结点最多有两棵子树，即二叉树中不存在度大于2的结点。
（2）二叉树是区分左子树和右子树的，左子树和右子树不能随意颠倒。
（3）即使二叉树中某个结点只有一棵子树，这棵子树也是要区分左子树和右子树的。
（4）在二叉树中，第i层最多有2 i-1 个结点（i≥1）。
（5）高度为h的二叉树，最多有2 h -1个结点（h≥1）。
（6）n0=n2+1，其中n0表示度为0的结点数，n2表示度为2的结点数。
斜树的定义是基于二叉树的，即斜树仍然是一棵二叉树。斜树分为两种：
（1）左斜树：是一种所有的结点都只有左子树的二叉树或者没有子树的一种特殊的二叉树。
（2）右斜树：是一种所有的结点都只有右子树或者没有子树的一种特殊的二叉树。
斜树如图2-35所示。
图2-35 左斜树和右斜树示意图
所有结点都存在左子树和右子树，并且所有的叶子结点都在同一层上的二叉树，称为满二叉树。
满二叉树的特点如下：
（1）所有的叶子必须出现在最后一层。
（2）非叶子结点的度一定是2。
（3）在同样高度的二叉树中，满二叉树的总结点数最多，满二叉树的叶子结点数最多。
满二叉树如图2-36所示。
图2-36 满二叉树示意图
完全二叉树是由满二叉树引出的。对一棵高度为h，具有n个结点的二叉树，当且仅当每个结点都与深度为h的满二叉树中编号为1～n的结点一一对应时，称这棵二叉树为完全二叉树。
完全二叉树的特点如下：
（1）叶子结点只能在最后一层或者倒数第二层。
（2）最下层的叶子结点集中在完全二叉树的左边。
（3）倒数第二层如果存在叶子结点，那么一定集中在完全二叉树的右边。
（4）如果结点的度为1，那么该结点只能有左子树，没有右子树。
（5）同样结点数目的二叉树，完全二叉树高度最小。
（6）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。
完全二叉树如图2-37所示。
图2-37 完全二叉树示意图
二叉树的存储可以使用顺序存储结构和链式存储结构。
二叉树的顺序存储结构使用一维数组存储二叉树中的结点，并且通过数组下标表示结点在二叉树中的位置。
对一棵完全二叉树采用如图2-38所示的方式进行编号。
图2-38 完全二叉树编号示意图
图2-38所示的完全二叉树可以使用图2-39所示的一维数组存储。
图2-39 完全二叉树顺序存储示意图
对一棵非完全二叉树进行编号（图中虚线框中的结点为不存在的结点），如图2-40所示。
图2-40 非完全二叉树编号示意图
图2-40所示的非完全二叉树顺序存储结构如图2-41所示。
图2-41 非完全二叉树顺序存储示意图
图2-41中一维数组空出的位置4、8和9并没有存储元素，此时顺序存储结构出现空间浪费。当用顺序存储结构存储左斜树或者右斜树时，将会造成更大的空间浪费。因此，顺序存储结构仅适用于完全二叉树的存储。
使用如图2-42所示的数据结构表示二叉树的一个结点。其中，data表示结点的数据域，leftChild表示结点的左子树的引用，rightChild表示结点的右子树的引用。
图2-42 自定义结构表示二叉树结点
使用图2-42的数据结构存储二叉树，如图2-43所示。
图2-43 二叉树链式存储结构示意图
二叉树的遍历指从二叉树的根结点出发，按照某种次序依次访问二叉树中所有结点的过程。
（1）二叉树前序遍历
前序遍历的顺序是：首先遍历根结点，然后递归遍历左子树，最后递归遍历右子树。
图2-38所示的二叉树前序遍历结果为：ABDHIEJCFG。
（2）二叉树中序遍历
中序遍历的顺序是：首先递归遍历左子树，然后遍历根结点，最后递归遍历右子树。
图2-38所示的二叉树中序遍历结果为：HDIBJEAFCG。
（3）二叉树后序遍历
后序遍历的顺序是：首先递归遍历左子树，然后递归遍历右子树，最后遍历根结点。
图2-38所示的二叉树后序遍历结果为：HIDJEBFGCA。
（4）二叉树层次遍历
层次遍历是按照树的层次自上而下遍历二叉树中的所有结点。
图2-38所示的二叉树层次遍历结果为：ABCDEFGHIJ。
二叉排序树又称二叉查找树或二叉搜索树。二叉排序树是一种特殊的二叉树，需要满足以下条件：
（1）如果左子树非空，那么左子树上所有结点的值都小于根结点的值。
（2）如果右子树非空，那么右子树上所有结点的值都大于根结点的值。
（3）每个结点的左子树和右子树都必须是二叉排序树。
（4）二叉树的所有结点中没有值相等的结点。
二叉排序树的查找过程如下：
（1）判断根结点的值是否等于查找的值，如果相等，就返回，否则执行（2）。
（2）如果查找的值小于结点的值，就递归查找左子树。
（3）如果查找的值大于结点的值，就递归查找右子树。
（4）二叉排序树中不存在值相等的结点。
在如图2-44所示的二叉排序树查找值为4的元素。
图2-44 二叉排序树查找元素示意图
二叉排序树的查找过程的时间复杂度是O(log 2 n)。
二叉排序树添加元素需要经历查找过程，通过二叉排序树的查找过程找到待添加元素的合适的位置，以保证添加元素后仍满足二叉排序树的要求。
二叉排序树删除元素分为3种情况，下面分别介绍。
（1）删除的结点是叶子结点
在二叉排序树中删除叶子结点不会破坏二叉排序树的结构，可以直接删除。在图2-44所示的二叉排序树中，需要删除叶子结点1。找到结点1所在的位置，直接删除。删除过程如图2-45所示。
图2-45 二叉排序树删除叶结点示意图
（2）删除的结点只有左子树或者右子树
在二叉排序树中删除的结点仅有左子树或者右子树，使用左子树或者右子树的根结点替换删除的结点，删除指定的结点。
在图2-44所示的二叉排序树中，删除元素5，需要将结点4移动到结点5的位置，然后删除结点5。删除过程如图2-46所示。
图2-46 二叉排序树删除仅有一个子结点的结点示意图
（3）删除的结点有左子树和右子树
删除的结点有左子树和右子树，删除该结点后，需要对二叉排序树进行调整。调整的方式有两种，下面分别介绍。
【方案1】 从删除的结点的左子树中，找到左子树最右边的结点，即左子树中最大的结点，替换删除的结点；然后进行后续的调整。删除过程如图2-47所示。
图2-47 二叉排序树删除有左右子结点的结点方案1示意图
【方案2】 从删除的结点的右子树中，找到右子树最左边的结点，即右子树中最小的结点，替换删除的结点；然后进行后续的调整。删除过程如图2-48所示。
图2-48 二叉排序树删除有左右子结点的结点方案2示意图
删除二叉排序树的3种情况中，第3种情况可以转化为前两种情况。
当找到删除结点的左子树中的最大结点或者右子树中的最小结点后，对删除的结点进行替换。替换后，替换结点只可能有一棵左子树，或者没有子树，即是叶子结点。
在图2-47中，用于替换的结点5不可能有右子树，如果有，就应该是结点5的右子结点替换结点6。
在图2-48中，用于替换的结点7不可能有左子树，如果有，就应该是结点7的左子结点替换结点6。
二叉排序树的代码实现如下：
创建二叉排序树的测试类，验证二叉排序树的功能。测试代码如下：
执行测试代码，执行结果如下：
----------二叉排序树中序遍历结果----------
1 2 3 4 5 6 7 8 9 10
----------二叉排序树先序遍历结果----------
6 3 2 1 5 4 8 7 10 9
----------二叉排序树后序遍历结果----------
1 2 4 5 3 7 9 10 8 6
-----二叉排序树删除元素8后中序遍历结果------
1 2 3 4 5 6 7 9 10
AVL树本质上是一棵自平衡的二叉排序树。AVL树具有以下特点：
（1）AVL树是一棵空树或它的左右两棵子树的高度差的绝对值不超过1。
（2）AVL树每个结点的左右两棵子树都是一棵平衡二叉树。
平衡二叉树和非平衡二叉树对比如图2-49所示。
图2-49 平衡二叉树和非平衡二叉树对比示意图
AVL树中有一个重要的概念叫作平衡因子。平衡因子指左子树与右子树高度差的绝对值。计算公式如下：
平衡因子=|左子树高度-右子树高度|
AVL树的平衡因子的取值范围是：-1≤平衡因子≤1。
普通的二叉排序树在一些极端的情况下可能会退化成链式结构，例如图2-50所示的结点1～5组成的二叉排序树。
图2-50 退化成链式结构的二叉排序树示意图
当二叉排序树退化成为链表时，此时访问其中的元素的时间复杂度从O(log 2 n)退化为O(n)。即便是在构建二叉排序树时尽量避免如图2-50所示的情况，但是随着在使用过程中不断地对二叉排序树进行添加和删除操作，还是会造成二叉排序树向左倾斜或者向右倾斜，造成二叉排序树的平衡性被破坏。
AVL树的插入和删除可能会破坏AVL树的平衡性。在插入或删除元素后，从变更的结点开始向根结点回溯，遇到的第一个不平衡的结点称为“最低失衡根结点”。从最低失衡根结点向下分析，不平衡的情况可以分为4种情况：
（1）导致失衡的结点出现在最低失衡根结点的左子树的左子树中。
（2）导致失衡的结点出现在最低失衡根结点的左子树的右子树中。
（3）导致失衡的结点出现在最低失衡根结点的右子树的右子树中。
（4）导致失衡的结点出现在最低失衡根结点的右子树的左子树中。
分析解决不平衡的情况之前，先介绍两种调整AVL树使之平衡的基本操作。
①左旋转
当向AVL树插入元素后，右子树的高度减去左子树的高度大于1，此时发生左旋转，即AVL树向左旋转，如图2-51所示。
图2-51 左旋转示意图
②右旋转
当向AVL树插入元素后，左子树的高度减去右子树的高度大于1，此时发生右旋转，即AVL树向右旋转，如图2-52所示。
图2-52 右旋转示意图
下面分别对各种不平衡的情况进行分析。
（1）LL情况旋转
LL（Left-Left）旋转即导致失衡的结点出现在最低失衡根结点的左子树的左子树中而发生结点旋转的情况。旋转方式是找到最低失衡根结点，将最低失衡根结点右旋转，如图2-53所示。
图2-53 导致失衡的结点出现在最低失衡根结点的左子树的左子树中示意图
如图2-53所示，最低失衡根结点是结点5，失衡是因为结点1的存在，而结点1位于结点5左子树的左子树中，需要一次右旋转即可达到平衡。具体的方法是：LL旋转的对象是最低失衡根结点（结点5），找到结点5的左孩子（结点3），将结点3的右孩子结点4变成结点5的左孩子，最后将结点5变成结点3的右孩子，调整后的AVL树如图2-54所示。
图2-54 LL情况旋转示意图
（2）LR情况旋转
LR（Left-Right）旋转即导致失衡的结点出现在最低失衡根结点的左子树的右子树中而发生旋转的情况。旋转方式是找到最低失衡根结点，先对最低失衡根结点的左孩子进行左旋转，然后对最低失衡根结点进行右旋转，如图2-55所示。
图2-55 导致失衡的结点出现在最低失衡根结点的左子树的右子树中示意图
图2-55的情况的调整过程：首先对最低失衡根结点5的左孩子结点2进行左旋转，然后对最低失衡根结点5进行右旋转。调整过程如图2-56所示。
图2-56 LR情况旋转示意图
（3）RR情况旋转
RR（Right-Right）旋转即导致失衡的结点出现在最低失衡根结点的右子树的右子树中而发生旋转的情况。旋转方式是找到最低失衡根结点，将最低失衡根结点左旋转，如图2-57所示。
图2-57 导致失衡的结点出现在最低失衡根结点的右子树的右子树中示意图
如图2-57所示，最低失衡根结点是结点2，失衡是结点6导致的，而结点6位于结点2右子树的右子树，需要一次左旋转即可达到平衡。旋转的对象是最低失衡根结点（结点2），找到结点2的右孩子结点4，将结点4的左孩子结点3变成结点2的右孩子，最后将结点2变成结点4的左孩子，旋转后的结果如图5-58所示。
图2-58 RR情况旋转示意图
（4）RL情况旋转
RL（Right-Left）旋转即导致失衡的结点出现在最低失衡根结点的右子树的左子树中而发生旋转的情况。旋转方式是找到最低失衡根结点，先对最低失衡根结点的右孩子进行右旋转，然后对最低失衡根结点进行左旋转，如图2-59所示。
图2-59 导致失衡的结点出现在最低失衡根结点的右子树的左子树中示意图
图2-59的情况的调整过程：首先对最低失衡根结点2的右孩子结点5进行右旋转，然后对最低失衡根结点2进行左旋转。调整过程如图2-60所示。
图2-60 RL情况旋转示意图
AVL树的代码实现如下：
创建AVL树的测试类，验证AVL树的功能。在测试代码中，通过数组中的1～16共16个数字创建了一个如图2-61所示的AVL树。
图2-61 测试类创建的AVL树示意图
AVL树的测试类代码如下：
执行测试代码，执行结果如下：
----------中序遍历AVL树----------
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
----------先序遍历AVL树----------
7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16
----------后序遍历AVL树----------
1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7
--------在AVL树查找元素12--------
12
--------在AVL树查找元素20--------
-1
--------在AVL树删除元素12--------
--------删除元素12后遍历AVL树--------
----------中序遍历AVL树----------
1 2 3 4 5 6 7 8 9 10 11 13 14 15 16
----------先序遍历AVL树----------
7 4 2 1 3 6 5 13 10 9 8 11 15 14 16
----------后序遍历AVL树----------
1 3 2 5 6 4 8 9 11 10 14 16 15 13 7
2-3-4树是一棵单个结点可以存储多个元素值的完美平衡（Perfect Balance）的查找树。所谓完美平衡，指的是从2-3-4树的根结点到每个叶子结点的路径的高度都是相等的。2-3-4树是一种进阶的二叉树，是一种自平衡的数据结构，它可以保证O(log 2 n)的时间内完成查找、插入和删除操作。2-3-4树具有以下性质：
（1）每个结点可以存储1个、2个或者3个元素值，相应的称这些结点为2（孩子）结点、3（孩子）结点、4（孩子）结点。
（2）根结点到所有的叶子结点的路径长度相等。
（3）每个结点的元素值从左到右保持了从大到小的顺序。两个元素值之间的子树中所有结点的元素值一定大于其父结点的左边的元素值，小于其父结点的右边的元素值。
（4）2结点的左子树上的所有元素值小于其父结点的元素值。2结点右子树上的所有元素值大于其父结点的元素值。
（5）3结点的左子树的所有元素值小于其父结点最小的元素值。3结点中间子树的所有元素值大于其父结点最小的元素值，小于其父结点最大的元素值。3结点的右子树上的所有元素值大于其父结点的最大元素值。同理，4结点也满足这样的性质。
2-3-4树示意图如图2-62所示。
图2-62 2-3-4树示意图
2-3-4树查找元素的过程与二叉排序树类似，首先比较查找的元素值与根结点的大小，如果元素值不存在于根结点中，就选择元素值所在的子树，递归上述过程，直至找到元素。2-3-4树的查找过程如图2-63所示。
图2-63 2-3-4树查找元素示意图
2-3-4树添加元素的步骤如下：
（1）如果2-3-4树中已存在当前插入的key，就会插入失败，否则通过查找过程找到合适的位置，在叶子结点中进行插入操作。
（2）如果待插入的结点不是4结点，那么直接在该结点插入新元素即可。
（3）如果待插入的结点是4结点，那么应该先分裂该结点再插入。一个4结点可以分裂成一个根结点和两个子结点（这3个结点各含一个元素值），然后在子结点中插入，可以把分裂形成的根结点中的元素值看成向上层结点插入的一个元素值。
（4）重复第2步和第3步，直至2-3-4树达到完美平衡。
下面分别对2-3-4树的各种插入情况进行分析。
（1）向一个2结点插入元素
直接将2结点变成一个3结点即可。例如向图2-63所示的2-3-4树中插入元素12，插入结果如图2-64所示。插入元素12，将2结点【15】变成一个3结点。
图2-64 2-3-4树2结点插入元素示意图
（2）向一个3结点插入元素
将3结点变成一个4结点即可。例如向图2-63所示的2-3-4树中插入元素20，插入结果如图2-65所示。插入元素20，将3结点【17，19】变成一个4结点。
图2-65 2-3-4树3结点插入元素示意图
（3）向一个4结点插入元素
4结点已经是最大的结点了，无法再插入元素。首先将4结点分裂成一个根结点和两个2子结点，向父结点中插入这个刚刚分裂出来的根结点。如果父结点也是一个4结点，就递归父结点的父结点直至2-3-4树达到平衡。例如向图2-65所示的2-3-4树中插入元素18，则插入过程可以分解为以下两个步骤。
（1）将4结点【17，19，20】分裂成3个2结点。分裂过程如图2-66所示。
图2-66 2-3-4树4结点分裂示意图
（2）将元素18插入2-3-4树中，调整2-3-4树使之达到平衡。
在如图2-65所示的2-3-4树中，4结点【17，19，20】的父结点【10，16，21】也是一个4结点，当4结点【17，19，20】分裂后，结点19会进入父结点【10，16，21】，因此父结点也需要进行图2-66所示的分裂。
向图2-65所示的2-3-4中插入元素18的详细过程如下：
首先通过2-3-4树的查找过程找到元素18合适的位置，如图2-67所示。
图2-67 查找元素18合适的位置示意图
4结点【17，19，20】进行分裂，元素19会进入父结点中，分裂结果如图2-68所示。
图2-68 4结点【17，19，20】分裂示意图
由于元素19的进入造成4结点【10，16，21】进行分裂，分裂结果如图2-69所示。
图2-69 4结点【10，16，21】分裂示意图
达到图2-69所示的状态后，2-3-4树已经达到完美平衡，不需要再进行调整，此次插入元素18结束。
（4）带有预分裂的插入
上述的向4结点插入元素的操作在某些情况下需要不断回溯来调整树的结构以达到平衡。为了消除回溯过程，在插入操作过程中可以采取预分裂的操作，即在插入操作搜索过程中，遇到4结点就分裂（分裂后形成的根结点的元素要上移，与父结点中的元素合并），这样可以保证查找到需要插入的结点时可以直接插入（该结点一定不是4结点）。
在图2-65所示的2-3-4树中，当查找元素18的存储位置时，遇到4结点【10，16，21】进行预分裂，如图2-70所示。
图2-70 4结点【10，16，21】预分裂示意图
在图2-70所示的2-3-4树中，继续向下查找元素18的存储位置，当遇到4结点【17，19，20】时进行预分裂，如图2-71所示。
图2-71 4结点【17，19，20】预分裂示意图
此时寻找到结点17可以存储元素18，直接将元素18插入即可。插入后的结果见图2-69。
2-3-4树删除元素的步骤如下：
（1）如果删除的元素不存在于2-3-4树中，就会删除失败。
（2）删除的元素不存在于叶子结点，用后继结点替代删除的结点。
（3）删除的元素位于叶子结点，如果叶子结点不是2结点，那么直接删除元素即可。如果删除的元素是2结点，那么删除该结点后需要进行如下调整：
①如果兄弟结点不是2结点，就将父结点中的一个元素值下移到该结点，兄弟结点中的一个元素值上移到父结点。
②如果兄弟结点是2结点，父结点是3结点或者4结点，父结点中的元素值就与兄弟结点中的元素值合并。
③如果兄弟结点是2结点，父结点是2结点，父结点中的元素值就与兄弟结点中的元素值合并，形成一个新的3结点，以新的3结点作为当前结点，重复①和②的步骤进行调整。
以图2-62为例，删除元素55的过程如下：
首先通过2-3-4树的查找过程找到元素55所在的结点位置，删除结点55，如图2-72所示。
图2-72 查找并删除元素55示意图
由于删除的结点位于叶子结点，满足第（3）点的第③小点，需要将父结点和兄弟结点合并，如图2-73所示。
图2-73 父结点60和兄弟结点70合并示意图
调整后的结点【60，70】的兄弟结点和父结点都是2结点，继续合并兄弟结点和父结点，如图2-74所示。
图2-74 父结点75和兄弟结点88合并示意图
调整后的结点【75，88】的父结点和兄弟结点都是2结点，继续合并父结点和兄弟结点，如图2-75所示。
图2-75 父结点50和兄弟结点23合并示意图
从2-3-4树删除和调整结点的过程可知，如果2-3-4树的删除导致了根结点参与合并， 2-3-4树的高度就会降低一层。例如上述删除元素55的过程中，2-3-4树的高度从4降到了3。
与2-3-4树插入元素的过程相对应的，2-3-4树可以使用预合并的删除操作避免删除过程中的回溯。在搜索过程中（除根结点，因为根结点没有兄弟结点和父结点），遇到当前结点是2结点，如果兄弟结点也是2结点就合并（该结点的父结点中的元素值下移，与自身和兄弟结点合并）；如果兄弟结点不是2结点，那么父结点的元素值下移，兄弟结点中的元素值上移。这样可以保证，找到需要删除的元素值所在的结点时可以直接删除（要删除的元素值所在的结点一定不是2结点）。
在图2-62所示的2-3-4树中，当查找元素55的存储位置时，遇到2结点75，其兄弟结点也是2结点，需要预合并，如图2-76所示。
图2-76 查找到2结点75示意图
对2结点75及其兄弟结点23和父结点50进行预合并，预合并结果如图2-77所示。
图2-77 2结点23、2结点50和2结点75预合并示意图
继续向下搜索，找到2结点60，其兄弟结点【35，48】是3结点，父结点中的元素值下移，兄弟结点中的元素值上移，如图2-78所示。值得注意的是，除了这种调整方式以外，还可以将父结点的元素值75与结点88合并，这两种方式都可以使2-3-4树达到平衡。
图2-78 父结点元素值50下移，兄弟结点元素值48上移示意图
找到元素55所在的结点后，结点55是一个2结点，其兄弟结点是2结点，父结点【50，60】中的元素值下移，与结点55和结点70进行预合并，合并结果如图2-79所示。
图2-79 父结点元素值60与兄弟结点55和兄弟结点70预合并示意图
删除结点55后的结果如图2-80所示。
图2-80 删除结点55后2-3-4树示意图
下面分析2-3-4树的执行效率。
（1）2-3-4树高度的最坏情况（全是2结点），相当于演变成了平衡二叉树，其查询的时间复杂度为O(log 2 n)。
（2）2-3-4树高度的最好情况（全是4结点），O(log 4 n )= 1/2 O(log 2 n)（但这种情况是不可能出现的，因为4结点的父结点或者子结点不能是4结点）。
（3）对于100万个结点，2-3-4树的高度为10～20。
（4）对于10亿的结点，2-3-4树的高度为15～30。
由此来看，2-3-4树的效率比平衡二叉树要好，但是问题在于2-3-4树并不好实现。
首先，需要用3种不同类型的结点代表2结点、3结点和4结点。
其次，在插入结点时，可能需要进行大量的切分4结点的工作，也可能需要频繁地在3种结点之间进行转换。
为了更好地利用2-3-4树平衡高度的特点，同时又便于实现，于是诞生了红黑树。
红黑树是与2-3-4树一一对应的树形结构，由于大部分编程语言直接实现2-3-4树很烦琐，因此一般是通过红黑树来实现2-3-4树的。红黑树同样可以保证在O(log 2 n)时间内完成查找、插入和删除操作。
红黑树是每个结点都带有红色或黑色属性的平衡二叉排序树。红黑树除了满足一般二叉排序树的要求外，红黑树还需要满足以下要求：
（1）每个结点必须带有颜色，红色或者黑色。
（2）根结点一定是黑色。
（3）每个叶子结点都带有两个空的黑色子结点（NIL结点，又称为黑色哨兵）。
（4）每个红色结点的两个子结点都是黑色结点，即从根结点到叶子结点的所有路径上，不存在两个连续的红色结点。
（5）从任一结点到其所能到达的叶子结点的所有路径含有相同数量的黑色结点。
红黑树是一个基本平衡的二叉排序树，红黑树并没有像AVL树一样保持绝对平衡，但是同样数量的结点组成的红黑树比AVL树少了很多旋转操作，且红黑树的删除效率比AVL树更高。
红黑树与2-3-4树的等价关系如下：
（1）3结点与红黑树的对应关系
2-3-4树的一个3结点可以使用红黑树的一个红色结点加一个黑色结点表示。如图2-81所示是红黑树表示的2-3-4树的一个3结点。
图2-81 2-3-4树3结点与红黑树对应关系示意图
（2）4结点与红黑树的对应关系
2-3-4树的一个4结点可以使用红黑树的两个红色结点加一个黑色结点表示。如图2-82所示是红黑树表示的2-3-4树的一个4结点。
图2-82 2-3-4树4结点与红黑树对应关系示意图
一棵完整的2-3-4树对应的红黑树如图2-83所示。
图2-83 2-3-4树与红黑树对应关系示意图
根据图2-83所示的红黑树，参照上述红黑树的5个特性进行分析。
（1）红黑树中每个结点都有颜色，结点的颜色只能为红色或者黑色。
（2）红黑树的根结点是黑色结点。如图2-83所示的结点8为黑色。
（3）红黑树的每个叶子结点带有两个空的黑色子结点，如图2-83所示的NIL结点。
（4）红黑树的每个红色结点的两个子结点都是黑色结点。
（5）红黑树的根结点到每个黑色子结点NIL的路径上包含的黑色结点数目都是3个。
因此，图2-83中的红黑树就是一棵标准的红黑树。
一棵红黑树对应一棵唯一形态的2-3-4树，但是一棵2-3-4树可以对应多种形态的红黑树，原因在于2-3-4树的3结点对应两种不同形态的红黑树，如图2-81所示。
红黑树的查找操作与二叉排序树类似。下面将重点分析红黑树添加元素操作和删除元素操作。
红黑树添加元素的过程如下：
（1）如果红黑树中已存在待插入的值，那么插入操作失败，否则一定是在叶子结点进行插入操作，执行步骤（2）。
（2）插入一个新结点后，将该结点涂红（涂红操作，从2-3-4树的角度来看，就是向上层结点进位一个元素值），由于插入操作可能破坏了红黑树的平衡性，因此需要不断回溯，进行调整。调整过程就是颜色变换和旋转操作，而这些操作都可以结合2-3-4树来理解。
插入新结点时，可以分为以下几种情况：
（1）父结点是黑色结点
如果父结点是黑色结点，插入新结点后，给结点涂红色即可，如图2-84所示。
图2-84 插入结点的父结点是黑色示意图
图2-84中箭头指向的结点表示插入的位置，图中的虚线表示可以有该结点，也可以没有该结点，如果有，那么该结点一定是红色的。这种插入场景还有可能存在另一种对称的情况，即在父结点的右子树上插入，操作方式是一样的，由于不涉及旋转操作，因此不再赘述。
这个操作相当于在2-3-4树中插入的叶子结点是2结点（红黑树中的黑色父结点没有子结点）或者3结点（红黑树中的黑色父结点有一个红色子结点），此时不会造成2-3-4树结点分裂，因此此时的红黑树不需要进行调整。
（2）父结点是红色的且叔叔结点是黑色的
这种情况需要对当前的红黑树进行相应的调整，以使红黑树恢复平衡。这种情况相当于2-3-4树中，容纳进位的父结点为3结点，还有空间可以容纳新的元素值，所以到这里就不用继续回溯了。
这种情况分别有以下4种形态：
①不平衡的红色结点是左子树中红色父结点的左孩子，如图2-85所示。
图2-85 红色结点是左子树中红色父结点的左孩子示意图
②不平衡的红色结点是左子树中红色父结点的右孩子，如图2-86所示。
当出现图2-86的形态时，需要进行一次左旋转，左旋转后转化为图2-85所示的形态，继续进行后续的调整。
图2-86 红色结点是左子树中红色父结点的右孩子示意图
以上两种形态还有其对应的镜像形态，即发生在右子树上。
③不平衡的红色结点是右子树中红色父结点的右孩子，如图2-87所示。
图2-87 红色结点是右子树中红色父结点的右孩子示意图
④不平衡的红色结点是右子树中红色父结点的左孩子，如图2-88所示。
图2-88 红色结点是右子树中红色父结点的左孩子示意图
当出现图2-88的形态时，需要进行一次右旋转，右旋转后转化为图2-87所示的形态，继续进行后续的调整。
（3）父结点是红色的且叔叔结点是红色的
这种情况相当于2-3-4树中，向上进位的父结点为4结点，所以先分裂，再插入新的元素并继续回溯，把分裂出的父结点看成向更上一层进位的结点继续回溯。
这种情况分别有以下4种形态：
①不平衡的红色结点是左子树中红色父结点的左孩子，如图2-89所示。
图2-89 红色结点是左子树中红色父结点的左孩子示意图
②不平衡的红色结点是左子树中红色父结点的右孩子，如图2-90所示。
图2-90 红色结点是左子树中红色父结点的右孩子示意图
以下两种形态是与上面两种形态对应的镜像形态，即发生在右子树上。因不涉及旋转操作，可以复用以上两种形态的代码实现，所以不进行区分。
③不平衡的红色结点是右子树中红色父结点的右孩子。
④不平衡的红色结点是右子树中红色父结点的左孩子。
红黑树删除操作的过程如下：
（1）如果在红黑树中不存在要删除的元素值，就会删除失败，否则执行（2）。
（2）如果删除的结点不是叶子结点，就用删除结点的后继结点替换，颜色不需要改变。
删除结点可以分为以下几种情况：
（1）要删除的结点为红色叶子结点
如果要删除的结点为红色叶子结点，那么直接删除该结点即可，如图2-91所示。
图2-91 删除红色叶子结点示意图
（2）要删除的结点是一个黑色结点且只有一个孩子结点
如果要删除的结点只有一个孩子结点，那么这个孩子结点一定是红色结点。删除此结点后，孩子结点上移并涂黑色。这种情况如图2-92和图2-93所示。
图2-92 删除黑色结点拥有红色左孩子示意图
图2-93 删除黑色结点拥有红色右孩子示意图
（3）要删除的结点是一个黑色叶子结点
删除黑色叶子结点后需要对红黑树进行调整，使之重新达到平衡。调整的情况分为以下a、b、c和d所示的4种。其中未着色的结点可以为红色或黑色。
1）删除的结点的兄弟结点为黑色结点且侄子结点为红色，这种情况分为以下1、2、3和4这四种不同的情况。
①删除的黑色叶子结点是父结点的右子结点，且其兄弟结点为黑色结点，且左侄子结点为红色的情况。删除黑色叶子结点10的调整过程如图2-94所示。
图2-94 删除右子结点10，兄弟结点4为黑色的，左侄子结点2为红色的示意图
②删除的黑色叶子结点是父结点的右子结点，且其兄弟结点为黑色结点，且右侄子结点为红色的情况。删除黑色叶子结点10的调整过程如图2-95所示。
图2-95 删除右子结点10，兄弟结点4为黑色的，右侄子结点6为红色的示意图
③删除的黑色叶子结点是父结点的左子结点，且其兄弟结点为黑色结点，且右侄子结点为红色的情况。删除黑色叶子结点4的调整过程如图2-96所示。
图2-96 删除左子结点4，兄弟结点10为黑色的，右侄子结点12为红色的示意图
④删除的黑色叶子结点是父结点的左子结点，且其兄弟结点为黑色结点，且左侄子结点为红色的情况。删除黑色叶子结点4的调整过程如图2-97所示。
图2-97 删除左子结点4，兄弟结点10为黑色的，左侄子结点9为红色的示意图
2）删除的结点的兄弟结点为黑色结点，且侄子结点为黑色结点，且父结点是红色结点（侄子结点只能是NIL结点，因为删除的结点是叶子结点）。删除结点4的调整过程如图2-98所示。删除结点10与删除结点4类似，删除结点10的过程不再赘述。
图2-98 删除黑色结点4，兄弟结点10为黑色的，父结点8为红色的示意图
3）删除的结点的兄弟结点、侄子结点、父结点都是黑色结点（侄子结点只能是NIL结点，因为删除的结点是叶子结点）。删除结点4的调整过程如图2-99所示。删除结点10与删除结点4类似，删除结点10的过程不再赘述。
图2-99 删除黑色结点10，兄弟结点4为黑色的，父结点8为黑色的示意图
4）删除的结点的兄弟结点是红色结点，父结点是黑色结点。对结点4的调整过程如图2-100所示，旋转完成后转换成了③中的情况。
图2-100 调整黑色结点4，兄弟结点10为红色的，父结点8为黑色的
红黑树的代码实现如下：
在测试类中创建了一颗红黑树，如图2-101所示。
图2-101 在测试类中创建的红黑树示意图
删除元素60后的红黑树如图2-102所示。
图2-102 在测试类中创建的红黑树删除元素60后示意图
红黑树测试类代码如下：
执行测试代码，执行结果如下：
----------红黑树中序遍历结果----------
0:红色 5:黑色 10:红色 20:黑色 30:黑色 40:黑色 50:红色 60:红色 70:黑色
----------红黑树中序遍历结果----------
0:红色 5:黑色 10:红色 20:黑色 30:黑色 40:黑色 50:红色 70:黑色
哈夫曼树（Huffman Tree）又称最优二叉树，是一种带权路径长度最短的树。
假设有这样一个场景：某学校期末考试成绩分为5个等级，分别是：成绩大于等于90分的为A，成绩大于等于80分且小于90分的为B，成绩大于等于70分且小于80分的为C，成绩大于等于60分且小于70分的为D，成绩未达到60分的为E。
上述场景可以使用一棵二叉树来表示，如图2-103所示。
图2-103 二叉树表示学生成绩示意图
假设该校有10 000名学生，成绩分布情况为：5%的学生取得成绩E，15%的学生取得成绩D，40%的学生取得成绩C，30%的学生取得成绩B，10%的学生取得成绩A。因此，在10 000个学生的样本中，在图2-103所示的二叉树中，查询每个学生的成绩需要查询的次数如下：
（5%×1 + 15%×2 + 40%×3 + 30%×4 + 10%×4）× 10000 = 31500次
将图2-103所示的二叉树调整为图2-104所示的二叉树，重新计算查询次数。
图2-104 学生成绩二叉树修正示意图
在图2-104所示的二叉树中，查询每个学生的成绩需要查询的次数如下：
（5%×3 + 15%×3 + 40%×2 + 30%×2 + 10×2）× 10000 = 22000次
由以上计算结果可知，哈夫曼树就是这样一种效率最高的判别树。
若给二叉树中的结点赋予一个有意义的数值，则这个数值称为该结点的权。从根结点到该结点的路径长度与该结点的权的乘积称为结点的带权路径长度。
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。
在权为w1,w2,…,wn的N个叶子结点组成的所有二叉树中，带权路径长度WPL最小的二叉树称为哈夫曼树或最优二叉树。
哈夫曼树具有以下特性：
（1）满二叉树不一定是哈夫曼树。
（2）哈夫曼树中权越大的叶子离根越近。
（3）相同带权结点生成的哈夫曼树不唯一。
（4）哈夫曼树的结点的度数为0或2，没有度为1的结点。
（5）包含n个叶子结点的哈夫曼树中共有2n–1个结点。
（6）包含n棵树的森林要经过n–1次合并才能形成哈夫曼树，共产生n–1个新结点。
下面通过权值集合{7,19,2,6,32,3,21,10}阐述哈夫曼树的构造过程。
（1）根据权值集合构建N棵二叉树的集合，其中每棵二叉树只有一个结点，如图2-105所示。
图2-105 构建哈夫曼树步骤（1）示意图
（2）在步骤（1）中选择两棵根结点权值最小的二叉树作为左右子树，构造一颗新的二叉树，将新的二叉树的根结点的权值设置为左右子树根结点的权值之和，将左右子树从二叉树集合中删除，新的二叉树加入二叉树集合。合并根结点为2和3的两棵二叉树，如图2-106所示。
图2-106 构建哈夫曼树步骤（2）示意图
（3）重复步骤（2），在图2-106所示的二叉树集合中，合并根结点为5和6的这两棵二叉树，如图2-107所示。
图2-107 构建哈夫曼树步骤（3）示意图
（4）合并根结点为7和10的这两棵二叉树，如图2-108所示。
图2-108 构建哈夫曼树步骤（4）示意图
（5）合并根结点为11和17的这两棵二叉树，如图2-109所示。
图2-109 构建哈夫曼树步骤（5）示意图
（6）合并根结点为19和21的这两棵二叉树，如图2-110所示。
（7）合并根结点为28和32的这两棵二叉树，如图2-111所示。
图2-110 构建哈夫曼树步骤（6）示意图
图2-111 构建哈夫曼树步骤（7）示意图
（8）合并根结点为40和60的这两棵二叉树，如图2-112所示。
图2-112 构建哈夫曼树步骤（8）示意图
哈夫曼树的应用很广，哈夫曼编码就是哈夫曼树在电信通信中的应用之一。哈夫曼树广泛地用于数据文件压缩，其压缩率通常为20%～90%。在电信通信业务中，通常用二进制编码来表示字母或其他字符，并用这样的编码来表示字符序列。
下面通过案例说明使用哈夫曼树设计哈夫曼编码的过程。
如需传送的电文为“ABACCDA”，即：A、B、C、D的频率（权值）分别为0.43、0.14、0.29、0.14，尝试构造电文的哈夫曼编码。
以电文中的字符作为叶子结点构造哈夫曼树。然后将哈夫曼树中的结点引向其左孩子的分支标记“0”，引向其右孩子的分支标记“1”，每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。电文为“ABACCDA”生成的哈夫曼树如图2-113所示。
图2-113 电文生成的哈夫曼树示意图
在构造哈夫曼树的过程中，每次调整都是合并权重值最小的两个结点。因此，在本书的哈夫曼树的实现过程中，使用继承Comparable接口的Node结点，方便对结点进行排序，读者亦可选择其他算法代替。
创建哈夫曼树的测试类，用于验证哈夫曼树的功能：
测试类中维护了一棵如图2-114所示的哈夫曼树。
图2-114 电文生成的哈夫曼树示意图
执行测试代码，执行结果如下：
----------哈夫曼树中序遍历----------
1 3 2 6 3 15 4 9 5
----------哈夫曼编码结果----------
1被编码成000
2被编码成001
3被编码成01
4被编码成10
5被编码成11
（1）二叉树的概念。
（2）二叉树的存储。
（3）二叉树的遍历。
· 前序遍历。
· 中序遍历。
· 后序遍历。
· 层次遍历。
（4）二叉排序树的实现及其优缺点。
（5）AVL树的优缺点。
（6）红黑树的原理及JDK对红黑树的应用。
（7）哈夫曼的编码及解码。