📄 page319.html
字号:
<HTML><HEAD><TITLE>AVL Search Trees</TITLE></HEAD><BODY bgcolor="#FFFFFF"> <a href="../index.html" target="_top"><img src="../icons/usins.gif" alt="Logo" align=right></a><b>Data Structures and Algorithms with Object-Oriented Design Patterns in Python</b><br><A NAME="tex2html4869" HREF="page320.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4867" HREF="page298.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4861" HREF="page318.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4871" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0010500000000000000000">AVL Search Trees</A></H1><A NAME="sectreesavl"> </A><P>The problem with binary search trees is that whilethe average running times for search, insertion, and withdrawaloperations are all <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >,any one operation is still <I>O</I>(<I>n</I>) in the worst case.This is so because we cannot say anything in generalabout the shape of the tree.<P>For example,consider the two binary search trees shown Figure <A HREF="page304.html#figtree13"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Both trees contain the same set of keys.The tree <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62787" SRC="img1046.gif" > is obtained by starting with an empty treeand inserting the keys in the following order<P> <IMG WIDTH=300 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath64175" SRC="img1248.gif" ><P>The tree <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62789" SRC="img1047.gif" > is obtained by starting with an empty treeand inserting the keys in this order<P> <IMG WIDTH=301 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath64176" SRC="img1249.gif" ><P>Clearly, <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62789" SRC="img1047.gif" > is a better tree search tree than <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62787" SRC="img1046.gif" >.In fact, since <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62789" SRC="img1047.gif" > is a <em>perfect binary tree</em><A NAME=19235> </A>,its height is <IMG WIDTH=103 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64201" SRC="img1250.gif" >.Therefore, all three operations, search, insertion, and withdrawal,have the same worst case asymptotic running time, <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >.<P>The reason that <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62789" SRC="img1047.gif" > is better than <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62787" SRC="img1046.gif" > is thatit is the more <em>balanced</em> tree.If we could ensure that the search trees we construct are balancedthen the worst-case running time of search, insertion, and withdrawal,could be made logarithmic rather than linear.But under what conditions is a tree <em>balanced</em>?<P>If we say that a binary tree is balanced if the left and rightsubtrees of every node have the same height,then the only trees which are balanced are the perfect binary trees.A perfect binary tree of height <I>h</I> has exactly <IMG WIDTH=58 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63175" SRC="img1089.gif" > internal nodes.Therefore, it is only possible to create perfect trees with <I>n</I> nodesfor <IMG WIDTH=164 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64215" SRC="img1251.gif" >.Clearly, this is an unsuitable balance condition becauseit is not possible to create a balanced tree for every <I>n</I>.<P>What are the characteristics of a good<em>balance condition</em><A NAME=19240> </A>?<OL><LI> A good balance condition ensures that the height of a tree with <I>n</I> nodes is <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >.<LI> A good balance condition can be maintained efficiently. That is, the additional work necessary to balance the tree when an item is inserted or deleted is <I>O</I>(1).</OL>Adelson-Velskii and Landis<A NAME="tex2html549" HREF="footnode.html#19437"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A>were the first to propose the followingbalance condition and show that it has the desired characteristics.<P><BLOCKQUOTE> <b>Definition (AVL Balance Condition)</b><A NAME="defnsrchtreeavl"> </A>An empty binary tree is<em>AVL balanced</em><A NAME=19248> </A><A NAME=19249> </A>.A non-empty binary tree, <IMG WIDTH=108 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63151" SRC="img1087.gif" >, is AVL balanced ifboth <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63147" SRC="img1085.gif" > and <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63149" SRC="img1086.gif" > are AVL balanced and<P> <IMG WIDTH=299 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath64177" SRC="img1252.gif" ><P>where <IMG WIDTH=17 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64231" SRC="img1253.gif" > is the height of <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63147" SRC="img1085.gif" > and <IMG WIDTH=17 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64235" SRC="img1254.gif" > is the height of <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63149" SRC="img1086.gif" >.</BLOCKQUOTE><P>Clearly, all perfect binary trees are AVL balanced.What is not so clear is that heights of all trees that satisfy the AVL balancecondition are logarithmic in the number of internal nodes.<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremsrchtreeii"> </A>The height, <I>h</I>, of an AVL balanced tree with <I>n</I> internal nodes satisfies<P> <IMG WIDTH=412 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath64178" SRC="img1255.gif" ><P></BLOCKQUOTE><P> extbfProofThe lower bound follows directly from Theorem <A HREF="page256.html#theoremtreesii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.It is in fact true for all binary treesregardless of whether they are AVL balanced.<P>To determine the upper bound,we turn the problem around and ask the question,what is the minimum number of internal nodesin an AVL balanced tree of height <I>h</I>?<P>Let <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64245" SRC="img1256.gif" > represent an AVL balanced tree of height <I>h</I>which has the smallest possible number of internal nodes, say <IMG WIDTH=20 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64249" SRC="img1257.gif" >.Clearly, <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64245" SRC="img1256.gif" > must have at least one subtree of height <I>h</I>-1 and thatsubtree must be <IMG WIDTH=32 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline64255" SRC="img1258.gif" >.To remain AVL balanced, the other subtree can have height <I>h</I>-1 or <I>h</I>-2.Since we want the smallest number of internal nodes, it must be <IMG WIDTH=33 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline64261" SRC="img1259.gif" >.Therefore, the number of internal nodes in <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64245" SRC="img1256.gif" > is <IMG WIDTH=163 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline64265" SRC="img1260.gif" >, where <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64267" SRC="img1261.gif" >.<P>Clearly, <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63001" SRC="img1066.gif" > contains a single internal node, so <IMG WIDTH=48 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64271" SRC="img1262.gif" >.Similarly, <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif" > contains exactly two nodes, so <IMG WIDTH=49 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64275" SRC="img1263.gif" >.Thus, <IMG WIDTH=20 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64249" SRC="img1257.gif" > is given by the recurrence<P><A NAME="eqnsrchtreeavl"> </A> <IMG WIDTH=500 HEIGHT=67 ALIGN=BOTTOM ALT="equation19261" SRC="img1264.gif" ><P><P>The remarkable thing about Equation <A HREF="page319.html#eqnsrchtreeavl"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is its similarity with the definitionof <em>Fibonacci numbers</em><A NAME=19270> </A>(Equation <A HREF="page75.html#eqnasymptoticfibonacci"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).In fact, it can easily be shown by induction that<P> <IMG WIDTH=301 HEIGHT=15 ALIGN=BOTTOM ALT="displaymath64179" SRC="img1265.gif" ><P>for all <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63063" SRC="img1074.gif" >, where <IMG WIDTH=16 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64281" SRC="img1266.gif" > is the <IMG WIDTH=20 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline61477" SRC="img821.gif" > Fibonacci number.<P><b>Base Cases</b><P> <IMG WIDTH=500 HEIGHT=38 ALIGN=BOTTOM ALT="eqnarray19275" SRC="img1267.gif" ><P><P><b>Inductive Hypothesis</b>Assume that <IMG WIDTH=103 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64285" SRC="img1268.gif" > for <IMG WIDTH=111 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63073" SRC="img1077.gif" >.Then<P> <IMG WIDTH=500 HEIGHT=89 ALIGN=BOTTOM ALT="eqnarray19279" SRC="img1269.gif" ><P>Therefore, by induction on <I>k</I>, <IMG WIDTH=103 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64285" SRC="img1268.gif" >, for all <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63063" SRC="img1074.gif" >.<P>According to Theorem <A HREF="page75.html#theoremasymptoticfibonacci"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>,the Fibonacci numbers are given by<P> <IMG WIDTH=318 HEIGHT=38 ALIGN=BOTTOM ALT="displaymath61787" SRC="img859.gif" ><P>where <IMG WIDTH=106 HEIGHT=30 ALIGN=MIDDLE ALT="tex2html_wrap_inline59943" SRC="img486.gif" >and <IMG WIDTH=106 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline59945" SRC="img487.gif" >.Furthermore, since <IMG WIDTH=79 HEIGHT=34 ALIGN=MIDDLE ALT="tex2html_wrap_inline64299" SRC="img1270.gif" >, <IMG WIDTH=84 HEIGHT=32 ALIGN=MIDDLE ALT="tex2html_wrap_inline64301" SRC="img1271.gif" >.<P>Therefore,<P> <IMG WIDTH=500 HEIGHT=123 ALIGN=BOTTOM ALT="eqnarray19299" SRC="img1272.gif" ><P>This completes the proof of the upper bound.<P>So, we have shown that the AVL balance condition satisfies thefirst criterion of a good balance condition--the height of an AVL balanced tree with <I>n</I> internal nodes is <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64305" SRC="img1273.gif" >.What remains to be shown is that the balance condition can beefficiently maintained.To see that it can,we need to look at an implementation.<P><BR> <HR><UL> <LI> <A NAME="tex2html4872" HREF="page320.html#SECTION0010510000000000000000">Implementing AVL Trees</A><LI> <A NAME="tex2html4873" HREF="page324.html#SECTION0010520000000000000000">Inserting Items into an AVL Tree</A><LI> <A NAME="tex2html4874" HREF="page329.html#SECTION0010530000000000000000">Removing Items from an AVL Tree</A></UL><HR><A NAME="tex2html4869" HREF="page320.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4867" HREF="page298.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4861" HREF="page318.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4871" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <P><ADDRESS><img src="../icons/bruno.gif" alt="Bruno" align=right><a href="../copyright.html">Copyright © 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.</ADDRESS></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -