📄 page327.html
字号:
<HTML><HEAD><TITLE>Double Rotations</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="tex2html4965" HREF="page328.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4963" HREF="page324.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4957" HREF="page326.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4967" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0010523000000000000000">Double Rotations</A></H3><P>The preceding cases have dealt with access paths LL and RR.Clearly two more cases remain to be implemented.Consider the casewhere the root becomes unbalanced with a positive balance factorbut the left subtree of the root has a negative balance factor.This situation is shown in Figure <A HREF="page327.html#figavl2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b).<P><P><A NAME="20279"> </A><A NAME="figavl2"> </A> <IMG WIDTH=575 HEIGHT=801 ALIGN=BOTTOM ALT="figure19778" SRC="img1287.gif" ><BR><STRONG>Figure:</STRONG> Balancing an AVL tree with a double (LR) rotation.<BR><P><P>The tree can be restored by performing an RR rotation at node <I>A</I>,followed by an LL rotation at node <I>C</I>.The tree which results is shown in Figure <A HREF="page327.html#figavl2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c).The LL and RR rotations are called<em>single rotations</em><A NAME=20284> </A><A NAME=20285> </A>.The combination of the two single rotations is called a<em>double rotation</em><A NAME=20287> </A><A NAME=20288> </A>and is given the name <em>LR rotation</em><A NAME=20290> </A><A NAME=20291> </A>because the first two edges in the insertion path from node <I>C</I>both go left and then right.<P>Obviously, the left-right mirror image of the LR rotation is calledan <em>RL rotation</em><A NAME=20293> </A><A NAME=20294> </A>.An RL rotation is called for whenthe root becomes unbalanced with a negative balance factorbut the right subtree of the root has a positive balance factor.Double rotations have the same properties as the single rotations:The result is a valid, AVL-balanced search tree andthe height of the result is the same as that of the initial tree.<P>Clearly the four rotations, LL, RR, LR, and RL,cover all the possible ways in which any one node can become unbalanced.But how many rotations are required to balance a treewhen an insertion is done?The following theorem addresses this question:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theoremsrchtreerotate"> </A>When an AVL tree becomes unbalanced after an insertion,exactly one single or one double rotation is required to balance the tree.</BLOCKQUOTE><P> extbfProofWhen an item, <I>x</I>, is inserted into an AVL tree, <I>T</I>,that item is placed in an external node of the tree.The only nodes in <I>T</I> whose heights may be affected by the insertion of <I>x</I>are those nodes which lie on the access path from the root of <I>T</I> to <I>x</I>.Therefore, the only nodes at which an imbalance can appearare those along the access path.Furthermore, when a node is inserted into a tree,either the height of the tree remains the sameor the height of the tree increases by one.<P>Consider some node <I>c</I> along the access path from the root of <I>T</I> to <I>x</I>.When <I>x</I> is inserted,the height of <I>c</I> either increases by one, or remains the same.If the height of <I>c</I> does not change,then no rotation is necessary at <I>c</I>or at any node above <I>c</I> in the access path.<P>If the height of <I>c</I> increases then there are two possibilities:Either <I>c</I> remains balanced or an imbalance appears at <I>c</I>.If <I>c</I> remains balanced, then no rotation is necessary at <I>c</I>.However, a rotation may be needed somewhere above <I>c</I> along the access path.<P>On the other hand, if <I>c</I> becomes unbalanced,then a single or a double rotation must be performed at <I>c</I>.After the rotation is done, the height of <I>c</I> is the same as it wasbefore the insertion.Therefore, no further rotation is needed above <I>c</I> in the access path.<P>Theorem <A HREF="page327.html#theoremsrchtreerotate"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> suggests the followingmethod for balancing an AVL tree after an insertion:Begin at the node containing the item which was just insertedand move back along the access path toward the root.For each node determine its height and check the balance condition.If the height of the current node does not increase,then the tree is AVL balanced and no further nodes need be considered.If the node has become unbalanced, a rotation is needed to balance it.After the rotation, the height of the node remains unchanged,the tree is AVL balanced and no further nodes need be considered.Otherwise, the height of the node increases by one,but no rotation is needed and we proceed to the next node on the access path.<P><HR><A NAME="tex2html4965" HREF="page328.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4963" HREF="page324.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4957" HREF="page326.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4967" 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 + -