AVL树

顺序表查找快,链表增删快,有没有一种数据结构能将二者的优点都结合起来呢?有,那就是平衡二叉树。平衡二叉树的左子树中的节点都小于根节点,右子树中的节点都大于根节点,假设左右子树相等,搜索时只需判断一次大小就排除了一半的数据,这不就是二分查找么!!!所以查找的复杂度为O(\log_2 n),又因为平衡二叉树是由指针构造的逻辑结构,所以增删节点只需要O(1)

查找 增删(已知节点位置) 增删(先查询节点位置)
有序顺序表 O(\log_2 n) O(n) O(\log_2 n)+O(n) = O(n)
链表 O(n) O(1) O(n)+O(1) = O(n)
平衡二叉树 O(\log_2 n) O(1) O(\log_2 n)+O(1) = O(\log_2 n)

初学时会觉得O(\log_2 n)又不是常数,也没有改善多少嘛,和O(n)有多少区别呢?

举个例子,假如从2^{50}\approx 一千亿条数据中搜索,O(n)大概需要搜索一千亿次,而O(\log_2 n)是二分查找的效率,每次减半,只需要搜索50次。优化效果恐怖如斯,即便是世界上最大的数据库也可以在50次内完成搜索。

AVL树在失衡的时候需要左旋或右旋来重平衡,而左旋、右旋的操作和记忆都比较麻烦,比较好的方法是“3+4重构”,因为调整的目的就是为了平衡,所以我们只需将失衡的节点按照平衡时的样子重新组装,无需关注如何旋转。
image

“3+4重构”的难点在于确定T0、T1、T2、T3,例如:
image
添加关键字48,如何“3+4重构”?

第一步确定根,添加48后不会导致53不平衡,会导致24不平衡,所以53不是根,24是根。

第二步确定a、b、c,节点添置在37上,所以24、53、37是a、b、c,其余是T0、T1、T2、T3。

伸展树

有没有比平衡二叉树更快的搜索方法?有的,不过只能保证大多数情况。平衡二叉树复杂度中的\log_2 n其实就是平衡二叉树的高度,树越高复杂度越大,那么就想办法降低树高呗!计算机中有个局部性原理,常用的数据只占很小一部分,例如我们计算机中有那么多文件,你常用的是不是就那么几个?伸展树就是利用这个原理,将常用的数据提到树顶,而其它大量的数据又不常用,这相当于无形中降低了树的高度,将原来高度为h的树将为常用数据组成的高度为k的树。伸展树不是平衡的二叉树,在最差的情况复杂度会退化为O(n),不过伸展树不会连续出现这种情况。
image

B树

以上所提到的数据结构都是基于内存的,但是如果数据大到一定程度就需要将数据存储到硬盘中,考察硬盘的特点:

  1. 硬盘的速度比内存慢的多,假如访问内存需要1秒,那么访问硬盘就需要一天。
  2. 从硬盘中读1B和1KB速度几乎是一样的。

B树就是根据硬盘的特点设计出来的m路平衡搜索树
image
它相当于将二叉树的多个节点结合成一个节点,目的是为了尽量少的访问硬盘,一旦访问硬盘则多读取一些数据。B树还有一个特点就是叶节点的高度完全一致。

B树中任何节点的子节点数量范围为[\lceil\mathrm{m} / 2\rceil,m],换言之B树中任何节点的关键字数量最小为[\lceil\mathrm{m} / 2\rceil-1,m-1],其中m被称为B树的阶。

考研中B树的高度是不包括最下层没有任何关键字的叶节点的(有些书中包括)。

B+树

B+树是B树的扩展,与B树有如下几处不同:

  1. 在B树中,含n个关键字的“超级节点”有n+1个孩子;在B+树中含n个关键字的“超级节点”有n个孩子。
  2. 在B树中,每个节点的关键字个数范围是[\lceil m / 2\rceil-1,m-1];在B+树中每个节点的关键字个数范围是[\lceil m / 2\rceil,m]
  3. 在B树中,非叶节点包含信息,每个关键字在树中仅会出现一次;在B+树中只有叶节点包含信息,而非叶节点只起到索引的作用,所以有些关键字会出现多次。
  4. B+树的叶节点相互串联,便于顺序查找。

image

多叉树

多叉树有一个重要的公式,高度为h的m叉树至多有\color{red}{(m^h-1)/(m-1)}个节点,反过来具有n个节点的m叉树的最小高度为\lceil \log_m(n(m-1)+1)\rceil

节点的分支树就是该节点的度。所有节点的度数等于所有节点数减1。

任何一棵多叉树都可以转换为二叉树吗?是的。因为,树有多种存储方式,其中一种是孩子兄弟表示法,如果你将多叉树转换为孩子兄弟表示法,从结构上看它就是一颗“二叉树”。
image

多叉树转换为二叉树的规则:每个节点左指针指向它的第一个孩子,右指针指向它在树中的相邻的右兄弟,这个规则又称为“左孩子右兄弟”。

image

树、森林与二叉树的转换

树转换为二叉树:
image
每个结点左指针指向它的第一个孩子,右指针指向它在树中的相邻右兄弟,这个规则又称“左孩子石兄弟”。

森林转换为二叉树:
image
先将森林中的每颗树转换为二叉树,再将二叉树的根节点相连即可。

线索树二叉树

在含有n个节点的二叉树中,含有n+1个空指针。我们可以用这些空指针指向其遍历序列的前驱节点和后继节点。这种树被称作线索二叉树。根据遍历序列的不同,线索树也分为中序线索树、先序线索树、后续线索树。

若无左子树,lchild指向前驱节点;若无右子树,rchild指向其后继节点。为此我们还有添加两个标识,以区分指向的是孩子还是线索。

哈夫曼树

节点的带权路径长度 = 节点的权值 x 该节点的路径长度
树的带权路径长度 = 所有叶节点的带权路径长度之和

image
上述3棵树的带权路径长度分别为:
WPL = 7x2 + 5x2 + 2x2 + 4x2 = 36
WPL = 4x2 + 7x3 + 5x3 + 2x1 = 46
WPL = 7x1 + 5x2 + 2x3 + 4x3 = 35

带权路径长度最小的树称为哈夫曼树。

给定n个权值分别为w_1,w_2,...,w_n的结点,构造哈夫曼树的算法描述如下:
1)将这n个结点分别作为n棵仅含一个结点的二叉树,构成森林F。
2)构造一个新结点, 从F中选取两棵根结点权值最小的树作为新结点的左、右子树,并且将新结点的权值置为左、右子树上根结点的权值之和。
3)从F中删除刚才选出的两棵树,同时将新得到的树加入F中。
4)重复步骤2)和3),直至F中只剩下一棵树为止。

哈夫曼编码

哈夫曼编码是哈夫曼树的重要应用之一。在数据通信中,对高频字符赋以短编码,对低频字符赋以较长编码,这样可以缩短平均编码长度。若没有一个编码是另一个编码的前缀,则称这样的编码为前缀编码。前缀编码的解码是唯一的。例如:若A、B、C的编码为0,101,100,则编码00101100的解码为AABC。若A、B、C、D的编码为0,101,100,00,则编码00101100的解码不唯一。

由哈夫曼树可以得到平均编码长度最短的前缀编码。我们可以根据以往数据通信中字符的频率构造出哈夫曼树,传输数据时根据哈夫曼树进行编码,解码根据哈夫曼树进行解码。

优先级队列 && 堆

优先级队列希望将队列里的元素按照优先级排序,显然AVL树以优先级为关键字肯定能实现需求。不过,大多数情况,我们只关心优先级最高或最低的元素,用AVL树有点杀鸡用牛刀之嫌,是能够完成这个任务的一个更精简的数据结构。

在逻辑上可以看作是一颗遵循堆序性的完全二叉树,堆序性是指任何节点的关键字都不大于(小于)它的父亲。在物理存储上是用顺序表存储的,因为完全二叉树除了最后一层,每一层都是满的,所以可以由位置关系将完全二叉树与顺序表相对应。
image
因为堆序性,堆中的最大元素(最小元素)必然在堆顶。

当插入节点时,仅需将其插入到末尾,如果违反堆序性递归的将其与其父亲交换位置,目标节点一直往上走,所以这一过程称为上滤。

当删除元素时,用末元素填补空位,然后递归的将其与更大(小)的孩子交换,目标节点一直往下走,这一过程被称为下滤。

初始化堆

将长度为n的顺序表初始化成堆,逻辑上相当于为完全二叉树增加堆序性。有两种简明的做法,一是对所有元素做上滤,二是对所有元素做下滤。两种方法都可以为每个元素增加堆序性。然而这两种方法的效率是完全不同的。
image

下滤时,节点走的距离是节点的高度,上滤时,节点走的距离是节点的深度,而树形结构下面的节点远比上面的节点多,这就造成了所有节点的深度之和要大于所有节点的高度之和。所以对所有节点上滤的复杂度为O(n\log n),对所有节点下滤的复杂度为O(n)。所以初始化堆时应选择对所有节点下滤。

posted @ 2020-11-10 18:49:36
评论加载中...

发表评论