数据结构AV树.ppt

AV树 AV树定义 平衡因子bal 平衡旋转 创建AV树 AV树插入 AV 树删除 练习 AVL树 高度平衡的二叉有哪些信誉好的足球投注网站树 AVL树 的重要性质 二叉有哪些信誉好的足球投注网站树的结构定义 结点的平衡因子bal 右子树的高度 hr 左子树的高度hl bal=hl-hr ( | bal |=1) AVL树任一结点平衡因子只能取 -1, 0, 1 如果一个结点的平衡因子bal的绝对值大于1,则这棵二叉有哪些信誉好的足球投注网站树就失去了平衡, 不再是AVL树。 如果一棵二叉有哪些信誉好的足球投注网站树是高度平衡的, 且有 n 个结点，其高度可保持在O(log2n),平均有哪些信誉好的足球投注网站长度也可保持在O(log2n)。 示例：计算bal 请画出这棵二叉有哪些信誉好的足球投注网站树的三叉链表存储，计算每个节点的bal值，判断是否是AVL树 平衡化旋转 如果在一棵平衡的二叉有哪些信誉好的足球投注网站树中插入一个新结点，造成了不平衡。此时必须调整树的结构，使之平衡化。 平衡化旋转有两类： 单旋转 (LL旋转和RR旋转) 双旋转 (LR旋转和RL旋转) 每插入一个新结点时, AVL 树中相关结点的平衡状态会发生改变。因此, 在插入一 个新结点后，需要从插入位置沿通向根的路径回溯，检查各结点的平衡因子。 如果在某一结点发现高度不平衡，停止回溯。从发生不平衡的结点起，沿刚才回溯的路径取直接下两层的结点。 如果这三个结点处于一条直线上，则采用单旋转进行平衡化。单旋转可按其方向分为LL旋转和RR旋转, 其中一个是另一 个的镜像，其方向与不平衡的形状相关。 如果这三个结点处于一条折线上，则采用双旋转进行平衡化。双旋转分为LR旋转和RL旋转两类。 AVL树删除 AVL树删除 课堂练习 根据输入的元素创建一棵AVL树 {6，76，99，50，45，80，77，5，46，71，73，56，58} 解答 课堂练习二 P196 现有整数：7，2，9，0，5，6，8，1 10.2 将整数插入到一个空的二叉有哪些信誉好的足球投注网站树 将整数插入到一个空的二叉平衡树中 小结 掌握AVL树的创建 掌握平衡旋转（程序代码了解） 掌握AVL树插入删除后的平衡化处理 * * * * * * * * * * AVL树的定义 一棵AVL树或者是空树，或者是具有下列性质的二叉有哪些信誉好的足球投注网站树：它的左子树和右子树都是AVL树，且左子树和右子树的高度之差的绝对值不超过1。 高度不平衡 高度平衡 A B C A B C D E D E 1. 含有n个结点的AVL树的高度为O(log2n)； 2. 在含有n个结点的AVL树中有哪些信誉好的足球投注网站一个元素需要为O(log2n)时间； 3. 将一个新元素插入一棵n个结点的AVL树中,可得到一棵n+1个结点的AVL树，且插入所需的时间为O(log2n)； 4. 从一棵n个结点的AVL树删除一个元素,可得到一棵n-1个结点的AVL树，且删除所需的时间为O(log2n)； typedef struct node { KeyType key ; /*关键字的值*/ int bf； //结点平衡因子 struct node *lchild,*rchild;/*左右指针*/ struct node * parent； //父结点指针 }bstnode,*BSTree; 三叉链表 3 2 1 left parent x bal right 0 3 2 0 0 1 0 0 2 1 0 不是一棵AVL树 3 2 1 1 2 3 右单旋转 左单旋转 1 3 2 LR双旋转 3 1 2 RL双旋转 3 2 1 1 2 3 1 3 2 3 2 1 3 1 2 2 1 0 -2 -1 0 0 -1 2 -2 1 0 例: 从一棵空树开始，通过输入一系列对象关键码，逐步建立AVL树。在插入新结点时使用平衡旋转方法进行平衡化处理。 16 例，输入关键码序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 }，插入和调整过程如下。 0 16 3 1 0 7 0 16 3 -1 2 LR双旋 7 3 16 0 0 0 11 0 1 -1 7 3 16 7 3 16 11 9 -1 3 7 11 9 16 右单旋 3 7 16 9 0 0 0 11 26 0 -1 -1 -2 0 1 2 -2 18 18 0 3 16 3 1 0 16 0 -2