📄 page328.html
字号:
<HTML><HEAD><TITLE>Implementation</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="tex2html4974" HREF="page329.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4972" HREF="page324.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4968" HREF="page327.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4976" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0010524000000000000000">Implementation</A></H3><P>Program <A HREF="page328.html#progavlTreec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the code for the <tt>doLLRotation</tt>method of the <tt>AVLTree</tt> class.This code implements the LL rotation shown in Figure <A HREF="page326.html#figavl1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The purpose of the <tt>doLLRotation</tt> method is to perform an LL rotation at the root of a given AVL tree instance.<P><P><A NAME="20463"> </A><A NAME="progavlTreec"> </A> <IMG WIDTH=575 HEIGHT=371 ALIGN=BOTTOM ALT="program20307" SRC="img1288.gif" ><BR><STRONG>Program:</STRONG> <tt>AVLTree</tt> class <tt>doLLRotation</tt> method.<BR><P><P>The rotation is simply a sequence of variable manipulationsfollowed by two height adjustments.Notice the rotation is done in such a way so that thethe given <tt>AVLTree</tt> instance remains the root of the tree.This is done so that if the tree has a parent,it is not necessary to modify the contents of the parent.<P>The <tt>AVLTree</tt> class also requires an <tt>doRRRotation</tt>method to implement an RR rotation.The implementation of that methodfollows directly from Program <A HREF="page328.html#progavlTreec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Clearly, the running time for the single rotations is <I>O</I>(1).<P>Program <A HREF="page328.html#progavlTreed"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the implementation for the<tt>doLRRotation</tt> method of the <tt>AVLTree</tt> class.This double rotation is trivially implemented as a sequence oftwo single rotations.As above, the method for the complementary rotationis easily derived from the given code.The running time for each of the double rotation methods is also <I>O</I>(1).<P><P><A NAME="20465"> </A><A NAME="progavlTreed"> </A> <IMG WIDTH=575 HEIGHT=180 ALIGN=BOTTOM ALT="program20323" SRC="img1289.gif" ><BR><STRONG>Program:</STRONG> <tt>AVLTree</tt> class <tt>doLRRotation</tt> method.<BR><P><P>When an imbalance is detected, it is necessary to correct the imbalanceby doing the appropriate rotation.The code given in Program <A HREF="page328.html#progavlTreee"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> takes care of this.The <tt>balance</tt> method tests for an imbalance usingthe <tt>balanceFactor</tt> property.The balance test itself takes constant time.If the node is balanced, only a constant-time height adjustment is needed.<P><P><A NAME="20467"> </A><A NAME="progavlTreee"> </A> <IMG WIDTH=575 HEIGHT=313 ALIGN=BOTTOM ALT="program20335" SRC="img1290.gif" ><BR><STRONG>Program:</STRONG> <tt>AVLTree</tt> class <tt>balance</tt> method.<BR><P><P>Otherwise, the <tt>balance</tt> method of the <tt>AVLTree</tt> classdetermines which of the four cases has occurred,and invokes the appropriate rotation to correct the imbalance.To determine which case has occurred,the <tt>balance</tt> method calls the <tt>balanceFactor</tt> propertyat most twice.Therefore, the time for selecting the case is constant.In all only one rotation is done to correct the imbalance.Therefore, the running time of this method is <I>O</I>(1).<P>The <tt>insert</tt> method for AVL trees is inherited fromthe <tt>BinarySearchTree</tt> class (see Program <A HREF="page316.html#progbinarySearchTreec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).The <tt>insert</tt> method calls <tt>attachKey</tt> to do the actual insertion.The <tt>attachKey</tt> method is overridden in the <tt>AVLTree</tt> classas shown in Program <A HREF="page328.html#progavlTreef"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="20469"> </A><A NAME="progavlTreef"> </A> <IMG WIDTH=575 HEIGHT=218 ALIGN=BOTTOM ALT="program20356" SRC="img1291.gif" ><BR><STRONG>Program:</STRONG> <tt>AVLTree</tt> class <tt>attachKey</tt> method.<BR><P><P>The very last thing that the <tt>insert</tt>method does is to call the <tt>balance</tt> method.which has also been overridden as shown in Program <A HREF="page328.html#progavlTreee"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.As a result the <tt>insert</tt> methodadjusts the heights of the nodes along the insertion pathand does a rotation when an imbalance is detected.Since the height of an AVL tree is guaranteed to be <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >,the time for insertion is simply <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >.<P><HR><A NAME="tex2html4974" HREF="page329.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4972" HREF="page324.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4968" HREF="page327.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4976" 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 + -