page326.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 68 行
HTML
68 行
<HTML><HEAD><TITLE>Single 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="tex2html4954" HREF="page327.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4952" HREF="page324.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4946" HREF="page325.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4956" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0010522000000000000000">Single Rotations</A></H3><P>Figure <A HREF="page326.html#figavl1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a) shows an AVL balanced tree.For example, the balance factor for node <I>A</I> is zero,since its left and right subtrees have the same height;and the balance factor of node <I>B</I> is +1,since its left subtree has height <I>h</I>+1 and its right subtree has height <I>h</I>.<P><P><A NAME="19763"> </A><A NAME="figavl1"> </A> <IMG WIDTH=575 HEIGHT=725 ALIGN=BOTTOM ALT="figure19392" SRC="img1283.gif" ><BR><STRONG>Figure:</STRONG> Balancing an AVL tree with a single (LL) rotation.<BR><P><P>Suppose we insert an item into <IMG WIDTH=20 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64433" SRC="img1284.gif" >, the left subtree of <I>A</I>.The height of <IMG WIDTH=20 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64433" SRC="img1284.gif" > can either increase or remain the same.In this case we assume that it increases.Then, as shown in Figure <A HREF="page326.html#figavl1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b),the resulting tree is no longer AVL balanced.Notice where the imbalance has been manifested--node <I>A</I> is balanced but node <I>B</I> is not.<P>Balance can be restored by reorganizing the two nodes <I>A</I> and <I>B</I>,and the three subtrees, <IMG WIDTH=20 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64433" SRC="img1284.gif" >, <IMG WIDTH=21 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64449" SRC="img1285.gif" >, and <IMG WIDTH=21 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64451" SRC="img1286.gif" >,as shown in Figure <A HREF="page326.html#figavl1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c).This is called an <em>LL rotation</em><A NAME=19769> </A><A NAME=19770> </A>,because the first two edges in the insertion path from node <I>B</I>both go to the left.<P>There are three important properties of the LL rotation:<OL><LI> The rotation does not destroy the data ordering property so the result is still a valid search tree. Subtree <IMG WIDTH=20 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64433" SRC="img1284.gif" > remains to the left of node <I>A</I>, subtree <IMG WIDTH=21 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline64449" SRC="img1285.gif" > remains between nodes <I>A</I> and <I>B</I>, and subtree <IMG WIDTH=21 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64451" SRC="img1286.gif" > remains to the right of node <I>B</I>.<LI> After the rotation both <I>A</I> and <I>B</I> are AVL balanced. Both nodes <I>A</I> and <I>B</I> end up with zero balance factors.<LI> After the rotation, the tree has the same height it had originally. Inserting the item did not increase the overall height of the tree!</OL>Notice, the LL rotation was called for becausethe root became unbalanced with a positive balance factor(i.e., its left subtree was too high)and the left subtree of the root also had a positive balance factor.<P>Not surprisingly,the left-right mirror image of the LL rotation is calledan <em>RR rotation</em><A NAME=19774> </A><A NAME=19775> </A>.An RR rotation is called for whenthe root becomes unbalanced with a negative balance factor(i.e., its right subtree is too high)and the right subtree of the root also has a negative balance factor.<P><HR><A NAME="tex2html4954" HREF="page327.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4952" HREF="page324.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4946" HREF="page325.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4956" 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 + =
减小字号Ctrl + -
显示快捷键?