?? page327.html
字號:
<HTML>
<HEAD>
<TITLE>Double Rotations</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
<img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html5970" HREF="page328.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page328.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html5968" HREF="page324.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page324.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html5962" HREF="page326.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page326.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html5972" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html5973" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H3><A NAME="SECTION0011523000000000000000">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 case
where the root becomes unbalanced with a positive balance factor
but the left subtree of the root has a negative balance factor.
This situation is shown in Figure <A HREF="page327.html#figavl2" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page327.html#figavl2"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> (b).
<P>
<P><A NAME="21033"> </A><A NAME="figavl2"> </A> <IMG WIDTH=575 HEIGHT=795 ALIGN=BOTTOM ALT="figure20532" SRC="img1345.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1345.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" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page327.html#figavl2"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> (c).
The LL and RR rotations are called
<em>single rotations</em><A NAME=21038> </A><A NAME=21039> </A>.
The combination of the two single rotations is called a
<em>double rotation</em><A NAME=21041> </A><A NAME=21042> </A>
and is given the name <em>LR rotation</em><A NAME=21044> </A><A NAME=21045> </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 called
an <em>RL rotation</em><A NAME=21047> </A><A NAME=21048> </A>.
An RL rotation is called for when
the root becomes unbalanced with a negative balance factor
but 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 and
the 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 tree
when 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 double rotation is required to balance the tree.
</BLOCKQUOTE>
<P>
extbfProof
When 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 appear
are those along the access path.
Furthermore, when a node is inserted into a tree,
either the height of the tree remains the same
or 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 was
before the insertion.
Therefore, no further rotation is needed above <I>c</I> in the access path.
<P>
Theorem <A HREF="page327.html#theoremsrchtreerotate" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page327.html#theoremsrchtreerotate"><IMG ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> suggests the following
method for balancing an AVL tree after an insertion:
Begin at the node containing the item which was just inserted
and 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="tex2html5970" HREF="page328.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page328.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html5968" HREF="page324.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page324.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html5962" HREF="page326.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page326.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html5972" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html5973" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright © 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address. \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a> All rights reserved.
</ADDRESS>
</BODY>
</HTML>
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -