(23)--第6章 查找-平衡二叉树数据结构.ppt

《(23)--第6章 查找-平衡二叉树数据结构.ppt》由会员分享，可在线阅读，更多相关《(23)--第6章 查找-平衡二叉树数据结构.ppt（23页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第7章 查找平衡二叉树平衡二叉树引入n如何提高二叉排序树的查找效率？n尽量让二叉树的形状均衡内容1.平衡二叉树的定义2.平衡二叉树的插入3.平衡二叉树的性能 平衡二叉树(balancedbinarytree)是由阿德尔森一维尔斯和兰迪斯(Adelson-VelskiiandLandis)于1962年首先提出的，所以又称为AVL树。平衡二叉树定义 平衡二叉树(balancedbinarytree)是由阿德尔森一维尔斯和兰迪斯(Adelson-VelskiiandLandis)于1962年首先提出的，所以又称为AVL树。平衡二叉树定义平衡二叉树或是空树，或是满足如下性质的二叉树：1.平衡二叉树根结

2、点的左、右子树深度之差的绝对值 1；2.左子树是平衡二叉树3.右子树是平衡二叉树.所有结点的左、右子树深度之差的绝对值 1平衡二叉树定义将结点的左子树深度减去右子树深度的值，称为该结点的平衡因子(balance factor)。平衡因子v任一结点的平衡因子只能取：任一结点的平衡因子只能取：-1-1、0 0 或或 1 1；如果；如果树中任意一个结点的平衡因子的绝对值大于树中任意一个结点的平衡因子的绝对值大于1 1，则这棵二叉树就失去平衡，不再是则这棵二叉树就失去平衡，不再是AVLAVL树；树；v对于一棵有对于一棵有n n个结点的个结点的AVLAVL树，其树，其高度保持在高度保持在O(logO(l

3、og2 2n n)数量级，数量级，ASLASL也保持在也保持在O(logO(log2 2n n)量级。量级。平衡二叉树特点(a)(a)平衡树平衡树 (b)(b)不平衡树不平衡树0 00 00 01 11 1-1-1-1-12 2 2 20 00 00 01 1-1-1练习判断下列二叉树是否为AVL树如果在一棵AVL树中插入一个新结点，就有可能造成失衡，此时必须重新调整树的结构，使之恢复平衡。我们称调整平衡过程为平衡旋转。平衡二叉树的插入LL平衡旋转RR平衡旋转LR平衡旋转RL平衡旋转保证二叉排序树的次序不变平衡二叉树旋转类型若在A的左子树的左子树上插入结点，使A的平衡因子从1增加至2，需要进行

4、一次顺时针旋转。(以B为旋转轴）A A A AB B B BC C C CA A A AB B B BC C C CLL型若在A的右子树的右子树上插入结点，使A的平衡因子从-1增加至-2，需要进行一次逆时针旋转。(以B为旋转轴）A A A AB B B BC C C CA A A AB B B BC C C CRR型若在A的左子树的右子树上插入结点，使A的平衡因子从1增加至2，需要先进行逆时针旋转，再顺时针旋转。A AB BC CA AB BC CA AB BC CLR型若在A的右子树的左子树上插入结点，使A的平衡因子从-1增加至-2，需要先进行顺时针旋转，再逆时针旋转。A AB BC CA

5、AB BC CA AB BC CRL型0 024240 013130 037370 02424请请将下面序列构成一棵将下面序列构成一棵平衡二叉排序树平衡二叉排序树 （1313，2424，3737，9090，5353）0 013130 03737-1-113130 02424-1-12424-2-213需要需要RRRR型旋转型旋转0 09090-1-12424-1-137371 19090-2-237需要需要RLRL型旋转型旋转(先先顺后逆）顺后逆）练习0 053530 013130 037370 024240 09090-1-12424-1-137370 053531 19090-2-2370

6、 037370 090900 053530 037370 090900 05353请请将下面序列构成一棵将下面序列构成一棵平衡二叉排序树平衡二叉排序树 （1313，2424，3737，9090，5353）在下列所示的平衡二叉树中插入关键字48后得到一棵新平衡二叉树，在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是（）。13，4824，4824，5324，90ABCD提交单选题2分 问：含 n 个关键字的二叉平衡树可能达到的最大深度是多少？问：深度为 h 的二叉平衡树中所含结点的最小值 Nh 是多少？性能分析一般情况下Nh=Nh-1+Nh-2+1N0=0 N1=1深度为 h 的二叉平衡树中所含结点的最小值 Nh 问题一般情况下Nh=n Nh+1含 n 个关键字的二叉平衡树可能达到的最大深度为h问题若平衡二叉树的高度为6，且所有非叶节点的平衡因子均为1，则该平衡二叉树的节点总数为（）。10203233ABCD提交单选题2分总结1.熟练掌握平衡二叉树的定义2.熟练掌握四种调整类型，要求会根据关键字序列，构造平衡二叉树3.掌握公式Nh=Nh-1+Nh-2+1