7.3 动态表的查找 (1)

《7.3 动态表的查找 (1)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、539337244512一、什么是平衡二叉树平衡二叉树(BalancedBinaryTree)又称AVL树。它或是空树，或是具有下列性质的二叉排序树。它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。7.3.2平衡二叉树(AVL树)二、平衡因子（BalanceFactor)左子树的深度-右子树的深度即平衡二叉树中每一结点的平衡因子为：0，1，-1。0-1三、平衡二叉树的查找平衡二叉树的查找方法同与二叉排序树。0000四、平衡的二叉树的插入（1）找插入位置；（2）插入结点；（3）若插入后导致不平衡，则进行调整。45

2、90100781236137240100001-1-1插入504590100781236137240100001-10500四、平衡的二叉树的插入（1）找插入位置；（2）插入结点；（3）若插入后导致不平衡，则进行调整。4590100781236137240100001-1-1插入154590100781236137240100011-20500152五、平衡的二叉树的插入（1）找插入位置；（2）插入结点；（3）若插入后导致不平衡，则进行调整。4590100781236137240100110RR旋转4590100781236124370-1

3、00001-2050015250001500例：以{30,35,39,15,10,28,16,29,17}建立平衡二叉树。四、平衡旋转1、LL旋转（LL：表示新插入结点在危机结点的左子树的左子树上）AB+1h-10+2+1hh-1h-1LL旋转BLBRARBA0h0h-1h-1BLBRAR危机结点旋转前：高度为h+1中序序列：ABBLBRAR旋转后：高度为h+1中序序列：ABBLBRAR2、LR旋转（LR：表示新插入结点在危机结点的左子树的右子树上）情况A：AB+1h-10+2-1h-1LR旋转BLAR危机结点旋转前：高度为h+1中序序列：

4、CCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR旋转后：高度为h+1中序序列：ABBLARCCLCRAB+1h-10+2-1h-1LR旋转BLAR危机结点旋转前：高度为h+1中序序列：CCRCLh-1h-2h-20-1CB0h-1h-1BLARACRh-1CLh-2+10ABBLARCCRCL旋转后：高度为h+1中序序列：ABBLARCCRCL2、LR旋转（LR：表示新插入结点在危机结点的左子树的右子树上）情况B：T3T4Th-1Th-2Th:高度h结点个数最少的AVL树左子树为

5、Th－1右子树为Th－2五、平衡二叉排序树的查找分析:T2T1设以Nh表示深度为h的二叉平衡树中的最少结点数。显然，N0=0,N1=1,N2=2Nh=Nh-1+Nh-2+1可以证明，n个结点的AVL树的最大深度为：logΦ(√5(n+1))-2。其中，Φ=(1+√5)/27.3.3B-树一、B-树的定义m阶B_树满足或空，或满足（1）树中每个结点最多有m个子树；（2）若根结点不是叶子结点，则至少有2个子树；（3）除根结点外的所有非叶子结点至少有m/2个子树；（4）所有的非叶子结点中包含的数据信息为：(n,A0,K1,R1,A1,K2,R2,

6、A2,………,Kn,Rn,An）其中，n:关键字的个数Ki：关键字Ri：关键字=Ki的数据记录在硬盘中的地址Ai：>Ki且

7、4764F5819924378FFFFFFFFFFF如查找关键字为KEY的记录。从根开始查找，如果Ki=KEY则查找成功，Ri为关键字为KEY的记录的地址。若KiKn;查找An指向的结点。若找到叶子，则查找失败。类似于二叉树的查找。例1，查找47。二、B-树的查找13511811112713934764F5819924378FFFFFFFFFFF类似于二叉树的查找。例2，查找30。如查找关键字为KEY的记录。从根开始查找，如果Ki=KEY则查找成功，Ri为

8、关键字为KEY的记录的地址。若KiKn;查找An指向的结点。若找到叶子，则查找失败。三、B-