数据结构与算法10.ppt

《数据结构与算法10.ppt》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构与算法二叉平衡树二叉平衡树又称AVL树，其或者是一棵空二叉树，或者是具有下列性质的二叉树：它的左，右子树高度之差的绝对值不超过1它的左，右子树都是二叉平衡树二叉树结点的平衡因子：该结点的左子树的高度减去右子树的高度。二叉平衡树的所有结点的平衡因子只可能是-1，0，12AVL树的旋转旋转变换的目的：是调整结点的子树高度，并维持二叉搜索树性质，即结点中元素的中序性质。旋转变换分为单旋转变换和双旋转变换2种类型。单旋转变换又分为右单旋转变换（RR）和左单旋转变换（LR）。双旋转变换又分为RL双旋转变换和LR双旋转变换。AVL树的插入运算AVL树与二叉搜

2、索树的插入运算是类似的。惟一的不同之处是，在AVL树中执行1次二叉搜索树的插入运算，可能会破坏AVL树的高度平衡性质，因此需要重新平衡。设新插入的结点为v。从根结点到结点v的路径上，每个结点处插入运算所进入的子树高度可能增1。因此在执行1次二叉搜索树的插入运算后，需从新插入的结点v开始，沿此插入路径向根结点回溯，修正平衡因子，调整子树高度，恢复被破坏的平衡性质。AVL树的插入运算插入一个新结点，势必会影响从根到新结点的路径上所有结点的平衡因子值。如果新结点插在这条路径上某结点的左子树上，那么该结点的平衡因子加1，否则减1。如果插入前从根结点到新结点的插入

3、位置的路径上所有结点的平衡因子均为0，那么插入后这个树依然是二叉平衡树，且整棵树的高度加1。如果某个结点的平衡因子不为0，但自它而下直至新结点的所有结点的平衡因子都为0。那么，插入新结点后，以结点s为根的子树将是有可能不平衡的最小子树。AVL树的插入运算假设q结点已插入二叉搜索树中，并且：结点s是新结点q的具有非零平衡因子值（插入前的值）的最近的祖先新节点q以插在s结点的左子树（右子树）上从结点s到结点q的路径上所有结点（不含s）的平衡因子值均已修订AVL树的插入运算分以下3种情形讨论二叉平衡树的插入运算。情形1：插入前，从根结点到新结点q的插入位置的路

4、径上，所有结点的平衡因子均为0，则插入后，须依次改变所经过结点的平衡因子，并且将树的高度加1，插入操作即完成。情形2：若新结点q插在结点s较矮的子树上（s的平衡因子BF为-1，并假定q插在s的左子树上），则插入后需令s的平衡因子BF为0，插入算法即完成。AVL树的插入运算情况三：q插在s的较高的子树上情形3.1：LL旋转q插在s的左孩子的左子树上，设r是s的左孩子，这时，由于以s为根的子树的平衡性被破坏，需用LL旋转重新恢复二叉树的平衡性将r的右孩子改为s的左子树，再使s成为r的右孩子，并将s的平衡因子修正为0。r是新子树的根，他的平衡因子是0。左单旋L

5、L的情况原来的AVL树插入一结点，A点不平衡左单旋的结果121右单旋RR的情况原来的AVL树插入一结点，A点不平衡右单旋的结果-1-2-1AVL树的插入运算情形3.2：LR旋转q插在s的左孩子的右子树上，r是s的左孩子，那么s的平衡因子为1且r的平衡因子为-1（s的尚未修正）这时需用LR旋转重新恢复二叉树的平衡性先进行右旋再进行左旋执行完LR旋转后，必须修改s，r和u的平衡因子值原来的AVL树插入一结点，A点不平衡先右旋再左旋LR双旋的情况12-1RL双旋的情况原来的AVL树插入一结点，A点不平衡先左旋再右旋-1-21-1AVL树的删除运算AVL树与二叉

6、搜索树的删除运算是类似的。惟一的不同之处是，在AVL树中执行1次二叉搜索树的删除运算，可能会破坏AVL树的高度平衡性质，因此需要重新平衡。设被删除结点为q，其惟一的儿子结点为v。结点q被删除后，结点v取代了它的位置。从根结点到结点v的路径上，每个结点处删除运算所进入的子树高度可能减1。因此在执行1次二叉搜索树的删除运算后，需从结点v开始，沿此删除路径向根结点回溯，修正平衡因子，调整子树高度，恢复被破坏的平衡性质。P是被删除结点q的父节点，同时增加一个bool变量shorter用来记录对双亲平衡性的影响情况一：p的平衡因子为0从p的子树上删除结点后，该子树

7、变矮，但是以p为根的子树高度不变，只需适当修正p的平衡因子即可情况二：从p的较高的子树上删除一个结点从p的较高的子树上删除一个结点后，该子树变矮，以p为根的子树也随之变矮，但该子树本身仍是平衡树。一方面，应将p的平衡因子置0，另一方面应继续考虑以p的双亲为根的子树的平衡问题AVL树的删除运算情况三：从p的较矮的子树上删除一个结点：此时子树的平衡性被破坏，需要通过旋转来恢复其平衡性，设r是p的较高的子树的根。3.1r的平衡因子为0时，采用单一旋转3.2r的平衡因子与p的平衡因子同号是，采用单一旋转3.3r的平衡因子和p的平衡因子异号时，应采用双重旋转AVL

8、树的删除运算#include"stdio.h"#include"malloc.h