数据结构讲义九：二叉排序树

1、动态查找 二叉排序树二叉排序树 平衡二叉树平衡二叉树 B-树（树（B+树）树） 键树键树二叉排序树二叉排序树 二叉排序树二叉排序树：或是一棵空二叉树，或是一棵具有下或是一棵空二叉树，或是一棵具有下列性质的二叉树：若左子树非空，则左子树上列性质的二叉树：若左子树非空，则左子树上所有所有结点的值均小于结点的值均小于根结点的值；若右子树非空，则右根结点的值；若右子树非空，则右子树上子树上所有结点的值均大于所有结点的值均大于根结点的值；并且其左、根结点的值；并且其左、右子树均是二叉排序树。右子树均是二叉排序树。类型定义为：类型定义为：typedef struct BSTNode intkey; 关键字

2、域关键字域 其它数据域其它数据域 struct BSTNode *lchild,*rchild;左、右孩子指针左、右孩子指针 BSTNode,*BSTree; 二叉排序树示例30125332394187189查找查找7171、5 5 二叉排序树的查找算法假定二叉排序树的根结点指针为 root ，给定的关键字值为 K ，则查找算法可描述为： 置初值： q root ； 如果 K q key ，则查找成功，算法结束； 否则，如果 K q key ，而且 q 的左子树非空，则将 q 的左子树根送 q ，转步骤；否则，查找失败，结束算法； 否则，如果 K q key ，而且 q 的右子树非空，则将 q

3、 的右子树根送 q ，转步骤；否则，查找失败，算法结束。int Bstree:Search(KeyType K) int flag=0; BstNode*q=root; while(q!=NULL)&(flag=0) if(q-key=K) cout查找成功，找到：查找成功，找到：keyendl; flag=1; else if(Kkey)q=q-lch; elseq=q-rch; if(flag=0)coutkey!=k) if(kkey) p=p-lchild; else p=p-rchild; return p;/SearchBST2 二叉排序树上结点的插入 步骤步骤： （1）若

4、二叉排序树是空树，则）若二叉排序树是空树，则k成为二叉排序成为二叉排序树的根；树的根；（2 2）若二叉排序树非空，则将）若二叉排序树非空，则将k与二叉排序树的与二叉排序树的根进行比较，如果根进行比较，如果k的值等于根结点的值，则停的值等于根结点的值，则停止插入；如果止插入；如果k的值小于根结点的值，则将的值小于根结点的值，则将k插入插入左子树；如果左子树；如果k的值大于根结点的值，则将的值大于根结点的值，则将k插入插入右子树。右子树。 插入算法void InsertBST(BSTree t,int k)/若二叉排序树若二叉排序树t中没有关键字中没有关键字k，则插入，否则直接返回，则插入，否则直

5、接返回 p=t; /p的初值指向根结点的初值指向根结点 while(p) /查找插入位置查找插入位置 if (p-key=k) return; /已有已有k，无需插入，无需插入 f=p; /f保存当前查找的结点保存当前查找的结点 p=(kkey)?p-lchild:p-rchild; /若若kkey，在左子树上查找，否则在右子树上查找，在左子树上查找，否则在右子树上查找 p=(BSTree)malloc(sizeof(BSTNode); p-key=k; p-lchild=p-rchild=NULL; if(t=NULL) t=p; else if (kkey) f-lchild=p; els

6、e f-rchild=p;/InsertBST 123532264520(g)二叉排序树的生成 (b)32(c)3226 (d)322645(a)32264535 (e)3226451235 (f)设序列为设序列为(32,26,45,35,12,20)(32,26,45,35,12,20)记录的关键码序列为：63，90，70，55，67，42，98，83，则构造一棵二叉排序树的过程如下：636390706390557063906755706390426755706390984267557063908398426755706390二叉排序树上结点的删除 假设要删除的结点为假设要删除的结点为*p，

7、结点，结点*p的双亲结的双亲结点为点为*f，并假设结点，并假设结点*p是结点是结点*f的左孩子的左孩子(右孩右孩子的情况类似子的情况类似)。下面分三种情况讨论：。下面分三种情况讨论：若若*p为叶子结点，则可直接将其删除：为叶子结点，则可直接将其删除：f-1childNULL; free(p)；若若*p结点只有左子树，或只有右子树，则可将结点只有左子树，或只有右子树，则可将*p的左子的左子树或右子树直接改为其双亲结点树或右子树直接改为其双亲结点*f的左子树，即：的左子树，即：f-1child=p-1child(或或f-1child=p-rchild); free(p)；FP*f*pP1FP1*f

8、FP*f*pPrFPr*f若若*p既有左子树，又有右子树。则：既有左子树，又有右子树。则： 令令*p结点的结点的直接前驱直接前驱（或直接后继）代替（或直接后继）代替*p，然后再从二叉排序树中，然后再从二叉排序树中删除它的直接前驱（或直接后继）。当以直接前驱删除它的直接前驱（或直接后继）。当以直接前驱*s代替代替*p时，由于时，由于*s只只有左子树有左子树SL，则在删去，则在删去*s之后，只要令之后，只要令SL为为*s的双亲的双亲*r的右子树即可的右子树即可RQ QqFSFRPRpQ QLrRLSLSRQ QqFPFRPRpQ QLrsRLSL二叉排序树上删除10或40或45或555845439

9、832405570639010void Delete(BSTree bst, keytype X) /在二叉排序树在二叉排序树bst上，删除其关键字为上，删除其关键字为X的结点。的结点。 BSTree f,p=bst; while (p & p-key!=X) /查找值为查找值为X的结点的结点 if (p-keyX) f=p; p=p-lchild; else f=p; p=p-rchild; if (p=null) printf(“无关键字为无关键字为X的结点的结点n”); exit(0); if p-lchild=null /被删结点无左子树被删结点无左子树 if (f-lchil

10、d=p) f-lchild=p-rchild;/将被删结点的右子树接到其双亲将被删结点的右子树接到其双亲上上 else f-rchild=p-rchild; else /被删结点有左子树被删结点有左子树 q=p; s=p-lchild; /s指向被删结点左子树的根指向被删结点左子树的根 while (s-rchild !=null) /查左子树中最右下的结点（中序最后结点）查左子树中最右下的结点（中序最后结点） q=s; s=s-rchild; p-key=s-key; /结点值用其左子树最右下的结点的值代替结点值用其左子树最右下的结点的值代替 if (q=p) p-lchild=s-lchi

11、ld;/被删结点左子树的根结点无右子女被删结点左子树的根结点无右子女 else q-rchild=s-lchild; /s是被删结点左子树中序最后一个结是被删结点左子树中序最后一个结点点 free(s); /算法结束算法结束 最佳二叉排序树 定义定义 ：平均查找长度最小的二叉排序树。平均查找长度最小的二叉排序树。 举例：举例：形如满二叉树或完全二叉树的形如满二叉树或完全二叉树的二叉排二叉排序树。序树。 非常难于构造。非常难于构造。 折中：平衡二叉树。折中：平衡二叉树。平衡二叉树 定义定义 ：它或者是一棵空二叉树，或者是二叉树它或者是一棵空二叉树，或者是二叉树中任一结点的左、右子树高度之差的绝对

12、值不中任一结点的左、右子树高度之差的绝对值不大于大于1，则称这棵二叉树为平衡二叉树，则称这棵二叉树为平衡二叉树 平衡因子平衡因子( (bfbf) )：结点的左、右子树高度差为该：结点的左、右子树高度差为该结点的平衡因子结点的平衡因子 平衡的二叉树示例01-1001-1101 00不平衡的二叉树示例210-1001-201 000平衡二叉树的类型定义typedef struct AVLNode int key; int bf; /结点的平衡因子结点的平衡因子 struct AVLNode *lchild,*rchild; /左、右孩子指针左、右孩子指针 AVLNode ,*AVLTree; 构造

13、平衡二叉树 方法方法：每当插入一个结点时，首先检查是否破每当插入一个结点时，首先检查是否破坏了树的平衡性，如果因插入结点而破坏了二坏了树的平衡性，如果因插入结点而破坏了二叉排序树的平衡，则找出其中叉排序树的平衡，则找出其中最小不平衡子树最小不平衡子树。所谓最小不平衡子树是指离插入结点最近，且所谓最小不平衡子树是指离插入结点最近，且平衡因子的绝对值大于平衡因子的绝对值大于1的结点，因为此结点的结点，因为此结点失去平衡，使得该结点的祖先结点也可能随之失去平衡，使得该结点的祖先结点也可能随之失去平衡。所以，失衡后应该调整以该结点为失去平衡。所以，失衡后应该调整以该结点为根的子树。根的子树。失去平衡的

14、四种情况 321223131132LL型型RR型型失去平衡的四种情况 312233121132LR型型RL型型二叉平衡树插入结点 ( 结点旁的数字为其平衡因子 ) 示例15152127152121271521154327关键字的插入顺序为关键字的插入顺序为(15(15，2121，2727，4343，3636，8 8，11)11) RR示例关键字的插入顺序为关键字的插入顺序为(15(15，2121，2727，4343，3636，8 8，11)11) 2127154336212715368432127154336示例关键字的插入顺序为关键字的插入顺序为(15(15，2121，2727，4343，3

15、636，8 8，11)11) 15211136827431521364327118(i)(j)LL型调整操作示意图BABRBLAR0BAARBLSBR21 (b)调整后恢复平衡调整后恢复平衡(a)插入结点插入结点S后失去平衡后失去平衡LL型调整的两个例子01613125031251251631002(a) BL、BR、AR 都是空树都是空树 (b) BL、BR、AR 都是非空树都是非空树9281631254728925163147281631254701010000010000210RR型调整操作示意图BBRAALBL (a) (a)插入结点插入结点* *s s后失去平衡后失去平衡(b)(b)

16、调整后恢复平衡调整后恢复平衡AAL-2BBRBL-1SRR型调整的两个例子(a) A(a) AL L、B BL L、B BR R 都是空树都是空树69-1314703147-1473169000-20025470-1-2-100473169254700-100000-1031766940402576316940(b) A(b) AL L、B BL L、B BR R 都是非空树都是非空树LR型调整操作示意图(b) (b) 调整后恢复平衡调整后恢复平衡 CACRAR0BBLCL00BAARCLCR2-1BLCS (a) (a) 插入结点插入结点* *s s后失去平衡后失去平衡 LR型调整的三个例子

17、281312503125-128253100020261628253147312547-10226281610031254700128160000000-10 (b) LR(L) (b) LR(L)型调整型调整(a) LR(0)(a) LR(0)型调整型调整LR型调整的三个例子312547-102302816-1003125470012816000301628253147001000(c) LR(R)(c) LR(R)型调整型调整RL型调整操作示意图 (b) (b)调整后恢复平衡调整后恢复平衡CBCRBRAALCLBAALBRCLSCCR (a) (a) 插入结点插入结点* *s s后失去平衡

18、后失去平衡 RL型调整的三个例子(a) RL(0) RL(0)型调整型调整40-13147031471403147000-20(b) RL(L)RL(L)型调整型调整31254701-236406910031254700-169400003625403147690000-10RL型调整的三个例子 (c) RL(R) (c) RL(R)型调整型调整31254701-24369400-1031254700-16940000432540314769001000AVLAVL树上结点的插入树上结点的插入 结点插入后，若平衡二叉树失去了平衡，结点插入后，若平衡二叉树失去了平衡，则要找到最小不平衡子树则要找

19、到最小不平衡子树 当插入树中后，修改有关结点的平衡因子当插入树中后，修改有关结点的平衡因子 如何判断根的子树是否失去平衡如何判断根的子树是否失去平衡 ，若失，若失去平衡则要作相应的处理去平衡则要作相应的处理AVLAVL树查找分析树查找分析 深度为深度为h h的平衡二叉树所具有的最少结点的平衡二叉树所具有的最少结点数数。 设以设以Nh表示深度为表示深度为h的平衡二叉树中含有的最少的平衡二叉树中含有的最少结点数。结点数。 N00，N1=1，N2=2，并且，并且NhNh-1+Nh-2+1。利用归纳法可证明：当利用归纳法可证明：当h0时，时，Nh=Fh+2-1。 含有含有n个结点的平衡二叉树的最大深度

20、，即在个结点的平衡二叉树的最大深度，即在AVL上进行查找的时间复杂度为上进行查找的时间复杂度为O(logn)。B-树 1970年Bayer提出B-树 多路平衡外查找树。 前面讨论的查找方法适用于组织规模较小、内存中能容纳的数据，是内查找方法内查找方法 B-B-树树是一种平衡平衡、有序有序、多路多路、动态动态的查的查找树找树，它是磁盘文件系统中索引技术常用的一种数据结构形式，如磁盘管理系统中的目录管理以及数据文件中的索引机构大多采用B-树B-树 B-树的定义 一棵一棵m阶的阶的B-B-树树，或为空树，或为满足下列特性的，或为空树，或为满足下列特性的m叉树：叉树： (1)树中每个结点至多有树中每个

21、结点至多有m棵子树；棵子树； (2)若根结点不是叶子结点，则至少有两棵子树；若根结点不是叶子结点，则至少有两棵子树； (3)除根结点之外的所有非终端结点至少有棵子树；除根结点之外的所有非终端结点至少有棵子树； ( 4 ) 所 有 的 非 终 端 结 点 中 包 含 下 列 信 息 数 据所 有 的 非 终 端 结 点 中 包 含 下 列 信 息 数 据（n,P0,K1,P1,K2,P2,Kn,Pn），其中：），其中：Ki(i=1,n)为关键字，且为关键字，且Kikey0=k; /设置哨兵，下面用顺序查找设置哨兵，下面用顺序查找key1.keynum for(i=t-keynum; kkeyi;

22、 i-); /从后向前找第从后向前找第1个小于等于个小于等于k的关键字的关键字 if(i0&t-keyi=k) /查找成功，返回查找成功，返回t及及i *pos=i; return t; /结点内查找失败，但结点内查找失败，但t-keyikkeyi+1下一个查找结点应为下一个查找结点应为soni if(!t-soni) /*t为叶子，在叶子中仍未找到为叶子，在叶子中仍未找到k，则查找过程失败，则查找过程失败 return NULL; DiskReadt-soni; /从磁盘上读入下一个查找的树结点到内存中从磁盘上读入下一个查找的树结点到内存中 return SearchBTree(t-

23、soni,k,pos);/递归的继续查找子树递归的继续查找子树t-soni/ SearchBTree B-树查找分析 在含有N个关键字的B-树上进行查找时，从根结点到关键字所在结点的路径上涉及的结点数不超过 1log212Nm若N=1,999,999, m=199，则查找次数至多为4。B-树查找长度分析 第一层至少有第一层至少有1个结点；个结点； 第二层至少有第二层至少有2个结点；个结点； 第三层至少有第三层至少有2* m/2 个结点，个结点，依次类推，依次类推; 第第L+1层至少有层至少有2*( m/2 )L-1个结点；个结点； 而而L+1层的结点为叶子结点层的结点为叶子结点,数量为数量为N

24、+1; N+1=2*( m/2 )L-1 ; 即即L=log m/2 (N+1)/2)+1 。2/m附：S=N+1的推导设设B-树某结点的子树数为树某结点的子树数为Ci，则该结点的关键字数，则该结点的关键字数Ni=Ci-1。对于有。对于有k个结点的个结点的B-树，有树，有 Ni=(Ci-1)=Ci-k（1ik） （1） 因为因为B树上的关键字数，即树上的关键字数，即Ni=N （1ik） （2） 而而B-树上的子树数可这样计算：每个结点（除根结点）树上的子树数可这样计算：每个结点（除根结点）都是一棵子树，设叶子（子树）数为都是一棵子树，设叶子（子树）数为S；则；则 Ci=(k-1)+S （1ik

25、） （3） 综合（综合（1）（）（2）（）（3）式，有）式，有s=n+1。证毕。证毕。B-树的插入 插入操作先要通过查找确定插入的位置，然后可按以下插入操作先要通过查找确定插入的位置，然后可按以下三种情形分别进行处理：三种情形分别进行处理： 情形情形2：插入关键字的结点在插入后，关键字的个数超过：插入关键字的结点在插入后，关键字的个数超过m-1，则，则进行分裂处理。假设当前处理的结点由进行分裂处理。假设当前处理的结点由q指向，以指向，以 为界，将结为界，将结点点*q分裂成两个结点，前面分裂成两个结点，前面 - -1个关键字组成一部分仍由个关键字组成一部分仍由q指指向，其余后面的一部分由向，其余

26、后面的一部分由q1指向，而中间的一个关键字指向，而中间的一个关键字 带着带着指针指针ql被被“上挤上挤”到双亲结点中到双亲结点中。 2/m2/m2/mK情形情形3：在执行情形：在执行情形2的的“上挤上挤”处理后，双亲结点中的关键字个数处理后，双亲结点中的关键字个数也超过了也超过了m- -1个，则必须以该双亲结点为当前结点，进行相同的处个，则必须以该双亲结点为当前结点，进行相同的处理，也就是说要继续理，也就是说要继续“上挤上挤”直至根结点。一旦根结点中的关键字直至根结点。一旦根结点中的关键字个数超过了个数超过了m- -1个，对根结点进行分裂处理后，整个个，对根结点进行分裂处理后，整个B-树的层数

27、即树的层数即增加一层增加一层 情形情形1：插入关键字的结点在插入后，关键字的个数不超过：插入关键字的结点在插入后，关键字的个数不超过m-1，则将给定的关键字插入到该结点的相应位置，插入过程即完成。则将给定的关键字插入到该结点的相应位置，插入过程即完成。插入结点后的分裂 插入后插入后：m,P0,(K1,P1,),(Km,Pm); KiKi+1 (1=im) 分成分成*p和和*q两个结点两个结点: p: m/2 -1,P0,(K1,P1),(K m/2 -1 ,P m/2 -1) q: m- m/2 ,P m/2 ,(K m/2 +1,P m/2 +1),(Km,Pm) K m/2 和和p一起插入

28、到一起插入到P结点中。结点中。B-树上插入结点3阶阶B-树上插入结点树上插入结点5618 24q2031q1(c)561881(e)18 56 81bt(d)561820 24 31q(b)24 315618(a)插入结点示例5618 3572(a)5618 3572 83(b)5672 8318 21 35(c)21 561872 8335(d)插入结点示例21 56183569 72 83(e) 56217218356983(g)(f) 21 56 7218356983B-B-树的删除树的删除 在在B-B-树树上删除一个关键字，则首先要找到该关上删除一个关键字，则首先要找到该关键字所在的结

29、点，并从中删除之。若该结点为键字所在的结点，并从中删除之。若该结点为最下层的非终端结点，且其中的关键字个数不最下层的非终端结点，且其中的关键字个数不少于少于 ，则删除完成。否则要进行，则删除完成。否则要进行“合并合并”结点的操作。假如所删除的关键字不是最下层结点的操作。假如所删除的关键字不是最下层的某个非终端结点的某个非终端结点Ki，则可以指针，则可以指针Pi所指子树中所指子树中的最下层的非终端结点中的最小关键字的最下层的非终端结点中的最小关键字y与与Ki互互换，然后在相应的结点中删除换，然后在相应的结点中删除Ki。因此只需讨。因此只需讨论删除最下层的非终端结点中的关键字的情形。论删除最下层的非终端结点中的关键字的情形。它可分三种情形分别进行处理它可分三种情形分别进行处理: :2/mB-B-树的删除树的删除情形情形1：被删关键字所在结点中的关键字数目不小于：被删关键字所在结点中的关键字数目不小于 ，则只需从，则只需从该结点中删去该关键字该结点中删去该关键字K，及相