12 最佳和平衡二叉排序树

《12 最佳和平衡二叉排序树》由会员分享，可在线阅读，更多相关《12 最佳和平衡二叉排序树（54页珍藏版）》请在金锄头文库上搜索。

1、算法与数据结构算法与数据结构 第十二讲第十二讲 最佳和平衡二叉排序树最佳和平衡二叉排序树 1 面向21世纪课程教材 普通高等教育“十一五”国家级规划教材 北京市高等教育精品教材 教育部普通高等教育精品教材 张乃孝等编著张乃孝等编著 算法与数据结构算法与数据结构C C语言描述语言描述 7 7 高级字典结构高级字典结构 7.4 最佳二叉排序树 7.5 平衡二叉排序树 2 7.4 7.4 最佳二叉排序树最佳二叉排序树 对同一关键码集合, 不 同的元素插入顺序, 可 能构造n!个不同(高度 和形态)的二叉排序树! 哪种二叉排序树 的检索效率最高？ 具有最小平均比 较次数！ 3 4 扩充的二叉排序树扩充

2、的二叉排序树 扩充的二叉排序树的对称序周游序列: 从最左下(记号为0)的外部结点开始; 以最右下(记号为n)的外部结点结束; 所有内/外部结点都是交叉排列: 第第i i个内部结点位于第个内部结点位于第i i- -1 1个外部结点和第个外部结点和第i i个外部结点之间个外部结点之间; ; 外部结点代表位于其相邻的两个内部结点关键码之间的所外部结点代表位于其相邻的两个内部结点关键码之间的所 有不属于当前字典的关键码集合有不属于当前字典的关键码集合. . 对检索来说: 如果被检索结点位于二叉树中第i层, 比较次数为 i+1; 如果该结点不存在,只有找到一个外部结点时确定检 索失败, 比较次数为此外部

3、结点的层数. 5 平均比较次数平均比较次数 在扩充的二叉排序树里，检索一个关键码的平平 均比较次数均比较次数为: 其中li是第i个内部结点的层数, li是第i个外部结 点的层数, pi是检索第i个内部结点关键码的频率频率, qi 是被检索的关键码属于第i个外部结点关键码集合的频频 率率, qi,pi也叫结点的权. pi /w是检索第i个内部结点关键码的概率概率, qi /w是被 检索的关键码属于第i个外部结点关键码集合的概率概率. . ( )() 10 1 1 nn iii i ii E np lql w = =+ 10 nn ii ii wpq = =+ 6 最佳二叉排序树最佳二叉排序树 最

4、佳二叉排序树最佳二叉排序树: E(n)最小的二叉排序 树。 根结点的关键码确定, 左右子树的关键码集 合也惟一确定; 左右子树也是最佳二叉排序树。 如何构造最佳二叉排序树? 等概率的检索 不等概率的检索 7 等概率的检索等概率的检索 ( )() 12 012 1 . 21 123 , 2121 n nn keykeykey pqqpp wwwwwn IPLn E nIPLnEPL nn IPLEPL rlink; b-rlink = a; a-bf = b-bf = 0; return b; /* b指向调整后子树的根 */ PAVLNode rR(PAVLNode a, PAVLNode b

5、) a-rlink = b-llink; b-llink = a; a-bf = b-bf = 0; return b; 33 LR LR 型调整型调整: : ()()B B(C C)A A()= ()= (B B)C C(A A) 在在A A的左子结点的左子结点(L)(L)的右子树的右子树(R)(R)中插入新结点中插入新结点, ,使使A A的平的平 衡因子由衡因子由- -1 1变成变成- -2, 2, 打破平衡。打破平衡。 调整规则调整规则: : 设设C C是是A A的左子结点的右子结点的左子结点的右子结点, , 将将A A的孙子结点的孙子结点C C提升为新二叉树的根提升为新二叉树的根; ;

6、 原来原来C C的父结点的父结点B B连同其左子树连同其左子树向左下旋转成为新根向左下旋转成为新根C C的左子的左子 树树; ; 原来原来C C的左子树的左子树 成为成为B B的右子树的右子树; ; 原根原根A A连同其右子树连同其右子树向右下旋转成为新根向右下旋转成为新根C C的右子树的右子树; ; 原来原来C C的右子树的右子树成为成为A A的左子树。的左子树。 若若 , , , , , , 全为空树全为空树,C,C就是新插入的结点就是新插入的结点, , 记为记为LR(0);LR(0); 新结点插在新结点插在C C的左的左(resp. (resp. 右右) )子树中子树中, ,记为记为LR

7、(L) (resp. LR(L) (resp. LR(R)LR(R)。 34 C 0 h-1 h-1 -1 A h h 0 B C -1 hh-1 -2 A h h 1 B C 0 h-1 1 A h h 0 B h 插入 LR调整 35 C 51 27 0 B -1 A 10 0 5 0 0 18 37 0 0 17 19 00 4966 0 0 C 51 27 0 B -2 A 10 1 5 0 -1 18 37 0 0 17 19 -1 0 4966 0 0 15 51 27 0 B1A 10 0 5 0 0 18 37 0 0 17 19 -1 0 4966 0 0 15 C 0 插入

8、15 LR(L)调整 36 PAVLNode lR(PAVLNode a, PAVLNode b) PAVLNode c = b-rlink; a-llink = c-rlink; b-rlink = c-llink; c-llink = b; c-rlink = a; switch (c-bf) case 0: /* LR(0)型调整型调整 */ a-bf = b-bf = 0; break; case -1: /* 新结点在新结点在*c左子树，左子树，LR(L)型调整型调整 */ a-bf = 1; b-bf = 0; break; case 1: /* 新结点在新结点在*c右子树，右子树

9、，LR(R)型调整型调整 */ a-bf = 0; b-bf = -1; break; c-bf = 0; return c; 37 RL RL 型调整型调整: : ( ( )A()A( C C )B()B( )=()=( A A )C()C( B B ) ) 在A的右子女(R)的左子树(L)中插入新结点,使 A的平衡因子由1变成2, 打破平衡。 调整规则: 设C是A的右子女的左子女, 将A的孙子结点C提升为新二叉树的根； 原来C的父结点B连同其右子树向右下旋转成为新 根C的右子树； 原来C的右子树成为B的左子树； 原根A连同其左子树向左下旋转成为新根C的左子 树； 原来C的左子树成为A的右子

10、树。 38 h-1 h-1 C 0 h-1 1 B h h 0 A h 插入 C 0 0 B h h 1 A C -1 -1 B h h 2 A hh-1 RL调整 39 0 C 51 27 0 B 1 A 10 0 5 0 0 18 3248 00 36 66 0 5699 00 0 C 51 27 -1 B 2 A 10 0 5 0 0 18 3248 10 36 66 -1 5699 00 33 0 0 0 C 51 27 1 B 0 A 10 0 5 0 0 18 36 66 0 5699 0 0 32 1 33 48 0 插入33 RL调整 40 PAVLNode rL(PAVLNo

11、de a, PAVLNode b) PAVLNode c = b-llink; a-rlink = c-llink; b-llink = c-rlink; c-llink = a; c-rlink = b; switch (c-bf) case 0: /* *c本身就是插入结点，RL(0)型调整 */ a-bf = 0; b-bf = 0; break; case -1: /* 插在*c的左子树中，RL(L)型调整 */ a-bf = 0; b-bf = 1; break; case 1: /* 插在*c的右子树中，RL(R)型调整 */ a-bf =- 1; b-bf = 0; break;

12、 c-bf = 0; return c; 41 调整平衡的模式调整平衡的模式小结小结 上面的几种情况在经过平衡旋转处理后： 原来的最小不平衡子树变成了平衡二叉排序树， 其高度与插入之前这棵子树的高度相同。 当平衡二叉排序树因插入结点而失衡时,仅需仅需 对最小不平衡子树进行旋转处理对最小不平衡子树进行旋转处理, ,就可以恢复 整棵树的平衡。 调整完全是局部的,可以高效实现。 42 AVLAVL树的实现树的实现 采用llink-rlink法表示, 在结点结构中增加一个字段bf存储结点的 平衡因子. struct AVLNode; typedef struct AVLNode * PAVLNode;

13、 struct AVLNode KeyType key;/* 结点的关键码*/ int bf; /* 结点的平衡因子*/ PAVLNode llink, rlink; /* 左、右指针 */ ; typedef struct AVLNode *AVLTree; typedef AVLTree *PAVLTree; 在在AVLAVL树中的检索算法与一般二叉排序树中的检索算法一样。树中的检索算法与一般二叉排序树中的检索算法一样。 43 AVLAVL树的插入运算树的插入运算 在AVL树中插入结点的算法框架与一般的二 叉排序树的插入算法类似, 但要考虑插入后 调整平衡: (1)(1)新结点插入后新结点

14、插入后, , 若二叉树失去了平衡若二叉树失去了平衡, ,则要找到则要找到 最小不平衡子树最小不平衡子树: : 令令 node_a node_a 指向离插入位置最近的平衡因子不为指向离插入位置最近的平衡因子不为 0 0的结点的结点, ,不存在这种结点时不存在这种结点时 node_anode_a指向树根；指向树根； 若插入后若插入后AVLAVL树失衡，则树失衡，则* *node_a node_a 就是最小不平就是最小不平 衡子树的根衡子树的根; ; parent_aparent_a指向指向* *node_anode_a的父结点。的父结点。 44 AVLAVL树的插入运算树的插入运算(Cont.)(

15、Cont.) (2)新结点插入后新结点插入后, ,要修改从要修改从 * *node_a node_a 的子结点到新结的子结点到新结 点的路径中各结点的平衡因子：点的路径中各结点的平衡因子： 插入前这段路径里的结点的平衡因子均为插入前这段路径里的结点的平衡因子均为0 0； 插入后从插入后从 * *node_a node_a 的子结点开始扫描路径上的的子结点开始扫描路径上的 结点结点* *p p，若新结点插入，若新结点插入 * *p p 左子树，则左子树，则 * *p p 平衡平衡 因子变为因子变为- -1 1；否则变为；否则变为 1 1。 45 AVLAVL树的插入运算树的插入运算(Cont.)(Cont.) (3)检查以检查以 * *node_anode_a 为根的子树是否失衡为根的子树是否失衡: : 若若 * * node_anode_a 平衡因子为平衡因子为0, 0, 则插入后不会失衡则插入后不会失衡, ,修改修改 平衡平衡因子因子； 若若 * * node_anode_a平衡因子为平衡因子为- -1 1且新结点插入且新结点插入 * *node_anode_a 的左的左 子树则出现失衡子树则出现失衡: : 若新结点插入若新结点插入* * node_anode_a的左子女的