data structure

1.二叉树排序

1.1 二叉排序树的定义

二叉排序树(BST),也称二叉查找树。二叉排序树或者是一棵空树,或者是一棵具有下列特性的非空二叉树。

  1. 若左子树非空,则左子树上所有结点关键字值均小于根结点的关键字值。
  2. 若右子树非空,则右子树上所有结点关键字值均大于根结点的关键字值。
  3. 左、右子树本身也分别是一棵二叉排序树。

可以看出,二叉排序树是一个递归的数据结构,可以方便地使用递归算法对二叉排序树进行各种运算。

根据定义,利用中序遍历可以得到一个递增的有序序列。

1.2 二叉排序树的查找

从根结点开始,若等于结点关键字值查找成功,小于结点关键字值往左找,大于结点关键字值往右找。

可以很简单地实现非递归和递归算法(首选非递归)

1.3 二叉排序树的插入

二叉排序树作为一个动态集合,其特点是树的结构通常不是一次生成的,而是在查找过程中,当树中不存在关键字值等于给定值的结点时再进行插入的。

由于二叉排序树是递归定义的,因此插入结点的过程如下:若原二叉排序树为空,则直接插入结点;否则,若关键字 k 小于根结点关键字,则插入左子树,若关键字 k 大于根结点关键字,则插入右子树。

1.4 二叉排序树的构造

依次将数据元素插入即可

1.5 二叉排序树的删除

在二叉树中删除一个结点时,不能把以该结点为根的子树上的结点都删除,必须先把被删除结点从存储二叉树的链表上摘下,将因删除结点而断开的二叉链表重新链接起来,同时确保二叉排序树的性质不会丢失。分三种情况

  1. 若被删除结点是叶结点,则直接删除,不会破坏二叉排序树的性质。
  2. 若结点 z 只有一棵左子树或右子树,则让 z 的子树成为 z 父结点的子树,替代 z 的位置。
  3. 若结点 z 有左、右子树,则令 z 的直接后继(或直接前驱)替代 z ,然后从二叉排序树中删除这个直接后继(或直接前驱),这样就转换成了第一或第二种情况。

1.6 二叉排序树的查找效率分析

对于高度为 h 的二叉排序树,其插入和删除操作的运行时间都是 O(h)。但在最坏情况下,即构造二叉排序树的输入序列是有序的,则会形成一个倾斜的单支树,此时二叉排序树的性能显著变坏,树的高度也增加为元素个数 n。所以,二叉排序树查找查找算法的平均查找长度与二叉树的形态有关。

若二叉树是一个只有右(左)孩子的单支树(类似于有序的单链表),则其平均查找长度和单链表相同,为 O(n) 。若二叉树的左右子树的高度之差的绝对值不超过 1,则这样的二叉排序树称为平衡二叉树。它的平均查找长度达到 O(log2n) 。

从查找过程看,二叉排序树与二分查找相似。就平均时间性能而言,二叉排序树上的查找和二分查找差不多。但二分查找的判定树唯一,而二叉排序树的查找不唯一,相同的关键字其插入顺序不同可能产生不同的二叉排序树。

就维护表的有序性而言,二叉排序树无须移动结点,只需修改指针即可完成插入和删除操作,平均执行时间为 O(log2n)。二分查找的对象是有序顺序表,若有插入和删除结点的操作,所花的代价为 O(n) 。当有序表是静态查找表(元素个数固定)时,宜用顺序表作为其存储结构,而采用二分查找实现其查找操作;若有序表是动态查找表,则应选择二叉排序树作为其逻辑结构。

2. 平衡二叉树

2.1 平衡二叉树的定义

为避免树的高度增长过快,降低二叉排序树的性能,我们规定在插入和删除二叉树结点时,要保证任意结点的左、右子树高度差的绝对值不超过 1,将这样的二叉树称为平衡二叉树(Balanced Binary Tree),简称平衡树(AVL)。定义结点左子树和右子树的高度差为该结点的平衡因子,则平衡二叉树结点的平衡因子的值只可能是 -1,0 或 1 。

2.2 平衡二叉树的插入

二叉排序树保证平衡的基本思想如下:每当在二叉排序树中插入(或删除)一个结点时,首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡,则先找到插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点 A,再对以 A 为根的子树,再保持二叉排序树特性的前提下,调整各结点的位置关系,使之重新达到平衡。

注意:每次调整的对象都是最小不平衡子树,即以插入路径上离插入结点最近的平衡因子的绝对值大于 1 的结点作为根的子树。

平衡二叉树的插入过程的前半部分与二叉排序树相同,但在新结点插入后,若造成查找路径上的某个结点不再平衡,则需要做出相应的调整。一般可将结点 A 失去平衡后进行调整的规律归纳为下列 4 种情况。

  1. LL 平衡旋转

    结点 A 的左孩子 (L)的左子树 (L)上插入新结点 。导致最左边太高

  2. RR 平衡旋转

    结点 A 的右孩子(R)的右子树(R)上插入新结点。导致最右边太高

  3. LR 平衡旋转

    结点 A 的左孩子(L)的右子树(R)上插入新结点。导致左孩子的右子树(子树根结点是 C)太高

  4. RL 平衡旋转

    结点 A 的右孩子(R)的左子树(L)上插入新结点。导致有孩子的左子树(子树根结点是 C)太高

注意 :LR 和 RL 旋转时,新结点究竟是插入 C 的左子树还是插入 C 的右子树不影响旋转过程 。

2.3 平衡二叉树的查找

在平衡二叉树上进行查找的过程与二叉排序树的相同。因此,在查找过程中,与给定值进行比较的关键字个数不超过树的深度。假设以 nh 表示深度为 h 的平衡树中含有的最少结点数。显然,有 n0=0,呢 n1=1,n2=2,并且有 nh = n_(h-1) + n_(h-2) +1 。可以证明,含有 n 个结点的平衡二叉树的最大深度为 O(log^2n) ,因此平衡二叉树的平均查找长度为 O(log2n)。

注意:该结论可用于求解给定结点数的平衡二叉树的查找所需的最多比较次数(或树的最大高度)。在含有 12 个结点的平衡二叉树中查找某个结点的最多比较次数是 5 次。

3. 哈夫曼树和哈夫曼编码

3.1 哈夫曼树的定义

在许多实际应用中,树中结点常常被赋予一个表示某种意义的数值,称为该结点的权。从树根结点到任意结点的路径长度(经过的边数)与该结点权值的乘积,称为该结点的带权路径长度。树中所有叶结点 (说明不包括非终端结点)的带权路径长度之和称为该树的带权路径长度,记为

WPL=Σw_i×l_i

式中 w_i 是第 i 个叶子所带的权值,l_i 是该叶结点到根结点的路径长度。

在含有 n 个带权叶子结点的二叉树中,其中带权路径长度(WPL)最小的二叉树称为哈夫曼树,也称最优二叉树。

3.2 哈夫曼树的构造

给定 n 个权值分别为 w1,w2,… ,wn 的结点,通过哈夫曼算法可以构造出最优二叉树,算法描述如下

  1. 将这 n 个结点分别作为 n 棵仅含一个结点的二叉树,构成森林 F
  2. 构造一个新结点,从 F 中选取两棵根结点权值最小的树作为新结点的左 、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和。
  3. 从 F 中删除刚才选出的两棵树,同时将新得到的树加入 F 中
  4. 重复 2 和 3 ,直至 F 中只剩一棵树为止

从上述构造看出

  1. 每个初始结点最终都成为叶结点,且权值越小的结点到根结点的路径长度越长
  2. 构造过程中共新建了 n-1 个结点(双分支结点),因此哈夫曼树中的结点总数为 2n-1
  3. 每次构造都选择 2 棵树作为新结点的孩子,因此哈夫曼树中不存在度为 1 的结点

3.3 哈夫曼编码

对于待处理的一个字符串序列,若对每个字符用同样长度的二进制位表示,则称这种编码方式为固定长度编码。若允许对不同字符用不等长的二进制表示,则这种方式称为可变长度编码。可变长度编码比固定长度编码好得多,其特点是对频率高的字符赋以短编码,而对频率较低的字符则赋以较长一些的编码,从而可以使字符平均编码长度较短,起到压缩数据的效果。哈夫曼编码是一种被广泛应用而且非常有效的数据压缩编码。

若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码。对前缀编码的解码很简单,因为没有一个码是其他码的前缀。所以,可以识别出第一个编码,将它翻译为原码,再对余下的编码文件重复同样的解码操作。

由哈夫曼树得到哈夫曼编码是很自然的过程。首先将每一个出现的字符当作一个独立的结点,其权值为它出现的频度(或次数),构造出对应的哈夫曼树,显然,所有字符结点都出现在叶结点中。我们可将字符的编码解释为从根置该字符的路径上边标记的序列,其中边标记为 0 表示 “转向左孩子”,标记为 1 表示 “转向右孩子” 。

英文序列的 WPL 可视为最终编码得到二进制编码的长度 。利用哈夫曼树可以设计出总长度最短的二进制前缀编码。

注意:0 和 1 究竟表示左子树还是表示右子树没有明确规定。因此,左、右结点的顺序是任意的,所以构造出的哈夫曼树并不唯一,但各哈夫曼树的带权路径长度相同且为最优。