第9章查找4讲-平衡二叉树.pptx

　　若一棵二叉树中每个结点的左、右子树的高度至多相差1，则称此二叉树为平衡二叉树（AVL）。　;二叉排序树;5; 平衡二叉树中插入新结点方式与二叉排序树相似，只是插入后可能破坏了平衡二叉树的平衡性，解决方法是调整。 　　 调整操作可归纳为4种情况。; （1）LL型调整;;AVL树LL调整演示;;;;调整完毕;;;;;0;; 【例9-5】 输入关键字序列(16，3，7，11，9，26，18，14，15)，给出构造一棵AVL树的步骤。;7;;;11;11; 在平衡二叉树上进行查找的过程和在二叉排序树上进行查找的过程完全相同，因此在平衡二叉树上进行查找关键字的比较次数不会超过平衡二叉树的高度。 在最坏的情况下，普通二叉排序树的查找长度为O(n)。那么，平衡二叉树的情况又是怎样的呢？ ; 构造一系列的平衡二叉树T1，T2，T3，…，其中，Th表示高度为h且结点数尽可能少的平衡二叉树，下图所示的T1，T2，T3、T4和Th。　;设N(h)为Th的结点数，从图中可以看出有下列关系成立： N(1)=1，N(2)=2，N(h)=N(h-1)+N(h-2)+1;由于Fibonacci数满足渐近公式：F(h)= 其中， 故由此可得近似公式：N(h)= 即：h≈log2(N(h)+1);思考题 平衡二叉树和二叉排序树相比，有什么优点？; ━━本讲完━━