Loading... # 树状结构的应用 ## 二叉树的排序与BinarySTree结构 ### 二叉排序树与 BinarySTree 结构 如果一棵二叉树的每个结点对应于一个关键码，在一般的二叉树中寻找关键码值为x的结点通常是困难的。如果二叉树中任何结点的左子树中所有结点的关键码值都小于该结点的关键码值，而右子树中所有结点的关键码值都大于该结点的关键码值。那么这样的二叉树称为二叉排序树（binary search tree），又称检索树。 在二叉排序树中查找值为x的结点，只需从根结点起，沿左或右子树向下接素。当x小于根结点的值，则沿着左子树下降搜索;当x大于根结点的值∶则沿着右子树下降搜索。继续上述搜索过程直到在二叉排序树中检索到值为 x 的结点或者检素到某一空子树，此时可判断 x 不在树中。 ### 二叉树的的检索，插入，删除运算 二叉排序树可看成是由依次插入一个关键码的序列构成的。在二叉排序树中插入一个结点通常并不指定位置，而只要求在插入后树仍具有左小右大的性质。 插入运算： * 若二叉排序树是空树，则新结点为二叉排序树的根结点； * 若二叉排序树非空，则将新结点的值与根结点的值比较，如果小于根结点的值，则插入到左子树中，否则插入到右子树中去。 删除运算： * 若待删除的结点没有左子树，则用右子树的根替换被删除的结点。 * 若待删除的结点有右子树，则用右子树的根替换被删除的结点，被删除结点的右子树作为被删除结点左子树对称序最后一个结点的右子树。 也可以： * 使用左子树对称序的最后一个结点或右子树对称序第一个结点来替换被删除结点 binarystree.h ```cpp #include "binarytreenode.h" struct binarySTree { BinaryTreeNode *root; }; typedef struct binarySTree BinarySTree; //void InitBinaryTreeNode(BinaryTreeNode *btree, ElementType e, BinaryTreeNode *l, BinaryTreeNode *r) //{ // btree->LeftChild=l; // btree->RightChild=r; // btree->data=e; //} /*插入新结点，多次插入*/ void ins_bst(BinaryTreeNode *p, BinaryTreeNode **q) { if(*q==NULL) *q=p; else if(p->data) ins_bst(p,&((*q)->LeftChild)); else ins_bst(p,&((*q)->LeftChild)); } /*从空树出发，依次插入结点 生成二叉排序树*/ void make_bst(BinaryTreeNode **r) { BinaryTreeNode *p,*q,*s; int x; *r =NULL; int endmark=-1;//原文中没定义，这里定义一下 printf("input x:"); scanf("%d",&x); if(x!=endmark) { p=CreateBTreeNode(x,NULL,NULL); * r =p; } printf("input x:"); scanf("%d",&x); while(x!=endmark) { q=CreateBTreeNode(x,NULL,NULL);//把结点创造出来 p=*r;//每次插入都要重新寻找 while(p!=NULL) { /*按非递归的方式插入一个新结点*/ s=p;//s代表上一个结点 if(q->data<p->data) p=p->LeftChild; else//寻找插入点 p=p->RightChild; } if(q->data<s->data) s->LeftChild=q; else//插入 s->RightChild=q; printf("input x:"); scanf("%d",&x); } } /*从树中删除一个结点*/ void dele_bst(BinaryTreeNode *root,BinaryTreeNode *p,BinaryTreeNode *f) { BinaryTreeNode *s; if(p->LeftChild==NULL)//无左子树 if(f==NULL) root=p->RightChild;//p是根结点 else if(f->LeftChild==p) f->LeftChild=p->RightChild;//被删除结点是其父母的左子女 else f->RightChild=p->RightChild;//被删除结点是其父母的右子女 else if(p->RightChild==NULL)//无右子女 if(f==NULL) root=p->LeftChild; else if(f->LeftChild==p) f->LeftChild==p->LeftChild; else f->RightChild=p->LeftChild; else { s=p->LeftChild; while(s->RightChild!=NULL) s=s->RightChild;//寻找左子树对称序的最后一个 if(f==NULL)//被删除结点是根 { root=p->LeftChild; s->RightChild=p->RightChild; } else if(f->LeftChild==p)//被删除结点是其父母的左子树 { f->LeftChild=p->LeftChild; s->RightChild==p->RightChild; } else { f->RightChild=p->LeftChild; s->RightChild=p->RightChild; } } } ``` ### 等概率查找对应的最佳二叉排序树 扩充二叉树：出现空子树就增加空树叶 原来二叉树的结点被称为内部结点，新加的叶结点被称为外部结点。这种外部结点是有意义的，例如图8.6（a）中的外部结点 A，代表其关键码值天于65 小于70的可能结点。  定义外部路径长度E为从扩充的二叉树的根结点到每个外部结点的路径长度之和，内部路径长度I为扩充二叉树的根结点到每个内部结点的路径长度之和。 一棵有n个内部结点的扩充二叉树，其外部结点有 n＋1个。用数学归纳法可证明对于含有n个内部结点的扩充二叉树，对应的E、I之间满足关系：E=I+2n。 本节仅考虑查找所有内部结点和外部结点概率和等时三文排序树的查找效率。在二叉排序树的查找过程中，每进行一次比较，就进入下一层。因此，对于成功的查找，比较次数就是关键码所在的层数，对于不成功的查找，被查找的关键码属于一个对应的外部结点代表的可能关键码集合，比较次数等于此外部结点的层数减1。在等概率的情况下，在二叉排序树里，查找一个关键码的平均比较次数为 $$ \begin{split} E(n)&=\frac1{2n+1}\left[\sum_{i=1}^nl_i+\sum_{i=1}^n(l_i'-1) \right]\\ &=\frac1{2n+1}\left[\sum_{i=1}^n(l_i'-1)+n+\sum_{i=1}^0(l_i'-1) \right]\\ & = \frac1{2n+1}(I+n+E)\\ & = \frac{2I+3n}{2n+1} \end{split} $$ 定义：E(n)最小的二叉排序树称为等概率查找对应的最佳二叉排序树（或称等情况下的最佳二叉排序树）。 显然，E（n）最小等价于I最小，即内部路径长度最小的二叉排序树为等概率情况下最佳二叉排序树。然而在一棵二叉排序树中，路径长度为0的结点最多一个，路径长度为1的结点最多2个……路径长度为k的结点最多$2^k$个$k=0,1,2,3,\cdots$，因此，对于n个结点的二叉排序树，I的最小值为序列 $0,1,1,2,2,2,2,3,3,3,3,3,3,3,3,4,\cdots$ 前n项的和 即 $I=\sum_{k=1}^n\lfloor log_2k\rfloor=(n+1)\lfloor log_2n\rfloor - 2^{\lfloor log_2n\rfloor +1} +2 $ 故 $$ \begin{split} E(n)&=\frac{2(n+1)\lfloor log_2n \rfloor-2^{\lfloor log_2n\rfloor+2}+4+2n}{2n+1}\\ &=O(log_2n) \end{split} $$ 可按折半查找法依次查找有序的关键码集合，按折半查找过程中遇到关键码的先后次序依次插入二叉排序树。  ## 平衡的二叉排序树 ### 平衡二叉排序树的定义 1. 空二叉树是一棵 AVL 树； 2. 若下为非空的二叉树，$T_L,T_R$分别为T的根结点的左、右子树，则T为 AVL 树当且仅当 1. $T_L,T_R$都为AVL树; 2. $|h_R-h_L|\le 1,h_R,h_L$分别为$T_L,T_R$的高度。 二叉树上的平衡因子定义为该结点的左子树高度减去它的右子树高度 ### 平衡二叉排序树的插入、删除 对于任意给定的一组关键码集合，构造的二叉排序树与关键码插人二叉排序树的先后次序有关，而且通常不一定是AVL树，为了保证得到AVL二叉排序树，插入过程需采用旋转来调整平衡。下面通过一个例子观察调整平衡时的旋转策略。 例8-2 构造对应于关键码序列{12，22，31，56，50}的 AVL二叉排序树，如图8.9 所示。 一般情况下，假设s为指向新插人结点的指针，当在原二叉排序树中已找到了新结点应插入的位置时，用指针变量a表示指向新结点的祖先中由下往上第一个平衡因子不为0的结点（也就是离s最近，且平衡因子不等于0的结点）；然后修改自 a 至s路径上所有结点的平衡因子值，当a结点的平衡因子的绝对值大于1时需要采用旋转方式调整平衡。  在a结点失去平衡后进行调整的规律可以归纳为下列四种情况（见图8.10）。 1. LL型单旋转：由于在a的左子树的左子树上插入结点，使a的平衡因子由1增至2而失去平衡，需进行一次顺时针旋转操作，如图 8.10（a）所示。 2. LR型双旋转：由于在a的左子树的右子树上插入结点，使a 的平衡因子由1增至2而失去了平衡，需先逆时针、后顺时针作两次旋转，如图8.10（b）所示。 3. RR 型单旋转∶由于在a的右子树的右子树上插入结点，使a 的平衡因子由一1 减至一2 而失去平衡，需进行一次逆时针旋转，如图 8.10（c）所示。 4. RL型双旋转∶由于在 a的右子树的左子树上插入结点，使a 的平衡因子由一1 减至一2而失去平衡，需进行先顺时针、后逆时针两次旋转，如图 8.10（d）所示。 上述四种调整 AVL 平衡树的旋转方法可用于 AVL 树中结点的插入，AVL 树的生长以及 AVL树结点的删除运算中。 删除： 1. 调用二叉排序树的删除算法删除结点 x； 2. 沿根到被删除结点的路线之逆向上返回时，修改有关结点的平衡因子； 3. 如果因删除结点使某子树高度降低并破坏平衡条件，就像插人那样，适当地旋转不平衡的子树，使之平衡。旋转之后，若子树的总高度依然降低，回溯不能停止，因而删除运算有可能引起多次旋转而不像插人那样至多旋转一次。  例：  ## $B$-树、$B^+$-树 定义8.3 一棵m阶的B-树，或为空树，或为满足下列特性的m叉树。 1. 树中每个结点(又称为页page)至多有m棵子树。 2. 若根结点不是叶序结点，则至少有2棵子树。 3. 除根之外的所有非终端结点至少有$\lceil\frac m2\rceil$棵子树。 4. 所有的非终端结点中包含下列信息∶ $(n,A_0,K_1,A_1,K_2,A_2,\cdots K_n,A_n)$ 其中，$K_i(i=1,\cdots,n )$ 为关键字（或称为元素），且 $k_i\lt k_{i+1}(i=1,\cdots ,n-1) $；$A_i(i=0,\cdots ,n)$ 为指向子树根结点的指针，且指针$A_{i-1}$所指子树中所有结点的关键字均小于$K_i(i=1,\cdots,n )$，$A_n$$所指子树中所有结点的关键字均大于$k_n$，为结点中关键字的个数($\lceil\frac m2\rceil-1\le n\le m-1 $)。 5. 所有叶子结点出现在同一层，且不含信息（外部结点）。 ### B-树的高度 设T为一棵高度为h的m阶的B-树，$d=\lceil \frac m2\rceil$，N为T中所含关键字的个数，则 1. $2d^{h-1}-1\le N\le m^h-1 $ 2. $log_n(N+1)\le h\le log_d\left(\frac{N+1}2\right)+1 $ ### B-树的检索插入，删除运算 在 B-树中查找元素 x 时，只需从根页起，每次把一个待查页从二级存储器调入内存（通常根页是常驻内存的），然后在该页中查找$x_0$，若找到了元素$x_0$。则检索成功，否则按下述方式继续查找，如果 1. $k_i\lt x\lt k_{i+1}(1\le i\lt n)$ 则准备查找 $A_i$页； 2. $x\lt k_1$，则准备查找$A_0$页； 3. $x\gt k_n$，则准备查找$A_n$页。 如果已遇到空页，则检索失败，说明 x不在 B-树中;否则重复上述1-3。 因为在内存中查找所需时间比把页调入内存的时间要少很多，所以一般的 B-树的m 值比树高要大很多。一般地，元素在页内是顺序存储（或采用二叉排序树形式），而检索算法用简单的顺序检索算法（m 较小时）或者菜用折平查找（m 较大时）。m的实用值大约在 100～500 之间。不难发现，若把B-树中的分支结点、叶结点都压缩到其祖先结点中，整个 B-树缩成一层，而且元素的值从左到右递增地排列着。这一性质正如对二叉排序树作对称序遍历那样，因此可以对 B-树作扩充的对称序遍历。 在B-树中插人新元素x，首先用检索算法查找插入位置，检索过程将终止于某一空树$A_i$，这时把x插在其父页（一定是叶页）的第i个位置。若插入x之后使该页上溢（页长大于m-1），需把该页分成两页，中间的那个元素递归地插入上一层页中（若m 是偶数，分页时会使两页元素差1，但通常m取奇数）。递归地插入会一直波及到根页。当根页上溢时，把根页一分为二，并将中间元素上移，而产生仅含一个元素的新根页。 > 最后这个递归插入波及到根叶没看懂  在上图中插入3、25后，下图给出了其变化图。  B-树的删除运算比插入运算更难实现。删除运算分两种情形实现∶ 1. 被删元素为叶页的元素，直接作删除； 2. 被删元素是非叶页的元素，这时需用该元素左子树下最大元素（或右子树下最小元素）与被删元素作交换，最后，待被删元素落在叶页上后再删除。 图8.13中删除元素 80后，用元素 80的右子树最小元素82替代 80再删除，删除后的7阶的 B-树如图8.14所示 以下仅讨论被删元素落在叶页上的 m 阶的 B-树中的删除运算，m 阶的 B-树中元素的删除可以归纳为下述三种情形∶ 1. 被删元素所在叶页的元素个数$\ge \lceil m/2\rceil $，则只需直接在该页中删除该元素。  2. 被删元素所在叶页中的元素个数$=\lceil m/2\rceil-1$，而与该结点相邻的右兄弟或左兄弟页中元素个数大于m/2-1，则需将其兄弟结点中的最小或最大的关键码（元素）上移至其父页中，而将父页中小于或大于该上移元素的元素下移至被删元素所在页中。 在图8.15中删除元素60，元素82上移至根页，根页中的元素 80下移至元素 60所在的页  3. 被删元素所在页及其相邻的页中元素的数目均等于$\lceil m/2\rceil-1$，假设该元素所在页有右兄弟，则将该元素所在页删除后剩下的元素和右兄弟页的元素连同父页中位于被删元素所在页和右兄弟页中的元素一起合并构成新页，这时，如果父页中的一个元素下移后可能引起下溢（即元素个数$\lt \lceil m/2\rceil-1$，则需采用1~3的办法再递归地调整 在图8.16中删除元素 70后，删除后的7阶 B-树如图8.17所示。  考虑 B-树的一种变形，该树中所有的信息仅存于树的叶页上，而非叶页仅含有便于查找的辅助信息，如本子树中结点关键码最小（或最大）值，这样的 B-树称为 $B^+$-树。$B^+$树是一种 B-树的变形树，一棵m 阶的 $B^+$ 树和 m 阶的 B-树的差异在于： 1. 有n棵子树的结点中含有n 个关键字; 2. 所有的叶子结点中包含了全部关键字的信息，以及指向含这些关键字记录的指针，且叶子结点本身依关键字的大小自小而大顺序链接; 聪部 3. 所有的非终端结点可以看成是索引部分，结点中仅含有其子树（根结点）中的最大（或最小）关键字。  ## 键树与2-3树 暂时不写，见书 ## Huffman最优树与树编码 ### Huffman最优树 引入扩充的二叉树。当二叉树里出现空的子树时，就增加新的、特殊的结点-—空树叶。对于原来二叉树里度数为1的分支结点，在它下面增加一个空树叶；对于原来二叉树的树叶，在它下面增加两个空树叶。这样扩充二叉树中的结点就分为内部结点和外部结点。外部路径长度 E 定义为从扩充的二叉树的根到每个外部结点的路径长度之和;内部路径长度I定义为扩充的二叉树里从根到每个内部结点的路径长度之和。 考虑带权的外部结点。结点的带权路径长度为从该结点到树根之间的路径长度与结点上权的乘积。带权外部路径长度为树中所有外部结点的带权路径长度之和，记为 $WPL=\sum_{k=1}^nw_kl_k $ $w_kl_k$分别为第k个外部结点的权和路径长度。 假设有n个权值$(w_1,w_2,\cdots,w_n) $试构造一棵存n个外部结点的二叉树，每个外部结 点带权为$w_i$，则其中带权外部路径长度 WPL 最小的二叉树称为最优二叉树或 Huffman （赫夫曼）树。 贪心算法构造最优二叉树 1. 首先在$w_1,w_2,\cdots,w_n $中找出两个最小的w值，比如 $w_1$和 $w_2$。（2）构造子树W+W2 飞 2. 构造子树$w_1——(w_1+w_2)——w_2 $ 3. 对 n-1个权$w_1+w_2,w_3,\cdots,w_n $构造 Huffman 树。 4. 重复1,2,3直到构造的扩充二叉树包括所有外部结点。 ```cpp struct huffmannode { int weight; int tag,LeftChild,RightChild; }; typedef struct huffmannode Huffmannode; void InitHuffmannode(Huffmannode *h,int t,int l,int r) { h->tag=t; h->LeftChild=l; h->RightChild=r; } struct huffmantree { int root; }; typedef struct huffmantree Huffmantree; void InitHuffmantree(Huffmantree *ht, int r) { ht->root=r; } void makeHuffmantree(Huffmantree *ht, int a[], Huffmannode b[], int n) { int i,j,m1,m2,x1,x2; /*逐步构造Huffman树*/ for(i=0;i<n;i++) b[i].weight=a[i]; for(i=1;i<n-1;i++) { m1=m2=32767;//m1m2是比任何树都大的整数 x1=x2=-1; for(j=0;j<n+1-1;j++) { if(b[j].weight<m1&&b[j].tag==0) { m2=m1;//m2次小，m1最小 x2=x1; m1=b[j].weight; x1=j; } else if(b[j].weight<m2&&b[j].weight) { m2=b[j].weight; x2=j; } } b[x1].tag=1; b[x2].tag=1;/*标记*/ /*构造子数*/ b[n-1+i].weight=b[x1].weight+b[x2].weight; b[n-1+i].LeftChild=x1; b[n-1+i].RightChild=x2; b[n-1+i].tag=0; } ht->root=2*n-2;//包含外部结点与内部结点总共n+n-1个结点 } ``` ### 树编码 设计不等长编码必须要求任一字符的编码都不是另一个字符编码的前缀，这种编码称为前缀编码；否则会出现所谓二义性。 用Huffman树表示一种编码方案，可克服上述二义性，而且总的编码长度最小。我们将待编码的字符对应 Huffman 树中的一个外部结点，给树中的分支作标记，使得指向左子女的分支标记0，指向右子女的分支标记为1。  ## 堆排序 堆的定义∶n个元素的序列$\{k_1,k_2,\cdots,k_n \} $满足F面两个条件之一，称为堆。 1. $k_i\le k_{2i},k_i\le k_{2i+1} i=1,2,\cdots,\lfloor\frac n2\rfloor $ 2. $k_i\ge k_{2i},k_i\ge k_{2i+1} i=1,2,\cdots,\lfloor\frac n2\rfloor $ 满足1的叫小根堆，满足2的叫大根堆 堆实质上是一棵完全二叉树结点的层次序列，堆的特性在此完全二叉树里解释为∶完全二叉树中任一结点的值小于（或大于）等于它的两个子女结点的值。 关于大根堆对应的完全二叉树有下面两条性质∶（1）根结点的值是堆中元素的最大值; （2）堆对应的完全二叉树的任何子树都具有堆性质。 下面研究堆中插入、删除一个结点的方法，规定删除运算总是对根结点进行。 插入  删除  反复删除堆中根结点，可使堆中结点排序，这就是堆排序的方法。对于任给一组关键码的集合，一般来说它不具有堆性质，堆排序的前提是需要将这组关键码的集合堆化，这就是建堆过程，建堆过程是反复应用筛选法的结果。 堆排序：(1)建堆；(2)反复删除堆中最大元素  ```cpp #include <stdio.h> #include <stdlib.h> #include <memory.h> struct maxHeap { int heapsize,Maxsize; int *heap; }; typedef struct maxHeap MaxHeap; int Size(MaxHeap *xheap) { return xheap->heapsize; } //返回堆顶元素 int Max(MaxHeap *xheap) { if(xheap->heapsize==0){ printf("underflow\n"); exit(1); } return xheap->heap[0]; } //初始化大根堆 void InitMaxHeap(MaxHeap *xheap, int MaxHeapsize) { xheap->Maxsize=MaxHeapsize; xheap->heap = (int *)malloc(sizeof(int) *xheap->Maxsize); xheap->heapsize=0; } //插入新元素 MaxHeap *Insert(MaxHeap *xheap, int x) { int i; if(xheap->heapsize==xheap->Maxsize) { printf("Overflow in MaxHeap\n"); exit(1); } i=xheap->heapsize++; while(i!=0&&x>xheap->heap[(i-1)/2]) {//比父母结点大，父母结点下移 xheap->heap[i]=xheap->heap[(i-1)/2]; i=(i-1)/2; } xheap->heap[i]=x; return xheap; } MaxHeap *DeleteMax(MaxHeap *xheap, int *x) {//删除堆顶的运算 int y; int i=0,ic=1; if(xheap->heapsize==0) { printf("underflow\n"); exit(1); } else { *x=xheap->heap[0]; y=xheap->heap[--xheap->heapsize];//最后一个先提取出来 while(ic<xheap->heapsize) { if((ic+1)<xheap->heapsize&&xheap->heap[ic]<xheap->heap[ic+1] ) //如果右边的条件成立，则右子女更大，使用右子女，否则继续使用左子女 ic++; if(y>=xheap->heap[ic]) break; xheap->heap[i]=xheap->heap[ic];//ic上移，相当于空位下称 i=ic;//i代表父母结点 ic=2*ic+1; } xheap->heap[i]=y; } return xheap; } void MakeHeap(MaxHeap *xheap, int a[], int size, int Arraysize) {//建立大根堆 int i,ic; int y; free(xheap->heap); xheap->heap=(int *)malloc(sizeof(int)*Arraysize); memcpy(xheap->heap,a,size*sizeof(int)); xheap->heapsize=size; xheap->Maxsize=Arraysize; for(i=(xheap->heapsize-2)/2;i>=0;i--) { y=xheap->heap[i]; ic=2*i+1; while(ic<xheap->heapsize) { if((ic+1)<xheap->heapsize&&xheap->heap[ic]<xheap->heap[ic+1] ) ic++; if(y>=xheap->heap[ic]) break; xheap->heap[(ic-1)/2]=xheap->heap[ic]; ic=2*ic+1; } xheap->heap[(ic-1)/2]=y; } } void Heapsort(int a[], int n) { MaxHeap * H=(MaxHeap *)malloc(sizeof(MaxHeap)); int x; int i; InitMaxHeap(H,n); MakeHeap(H,a,n,n); for(i=n-1;i>=0;i--) { DeleteMax(H,&x); a[i]=x; } } ``` 建堆算法复杂度分析  ## 判定树 ## 等价类和并查集 ## 红黑树 Last modification：January 20, 2023 © Allow specification reprint Like 如果觉得我的文章对你有用，请留下评论。