📄 page320.html
字号:
<HTML>
<HEAD>
<TITLE>AVL Search Trees</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="tex2html5879" HREF="page321.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page321.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="tex2html5877" HREF="page299.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page299.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="tex2html5871" HREF="page319.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page319.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="tex2html5881" 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="tex2html5882" 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>
<H1><A NAME="SECTION0011500000000000000000">AVL Search Trees</A></H1>
<A NAME="sectreesavl"> </A>
<P>
The problem with binary search trees is that while
the average running times for search, insertion, and withdrawal
operations are all <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59891" SRC="img403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img403.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 general
about the shape of the tree.
<P>
For example,
consider the two binary search trees shown Figure <A HREF="page305.html#figtree13" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page305.html#figtree13"><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>.
Both trees contain the same set of keys.
The tree <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63424" SRC="img1094.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1094.gif" > is obtained by starting with an empty tree
and inserting the keys in the following order
<P> <IMG WIDTH=300 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath64856" SRC="img1306.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1306.gif" ><P>
The tree <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63426" SRC="img1095.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1095.gif" > is obtained by starting with an empty tree
and inserting the keys in this order
<P> <IMG WIDTH=301 HEIGHT=14 ALIGN=BOTTOM ALT="displaymath64857" SRC="img1307.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1307.gif" ><P>
Clearly, <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63426" SRC="img1095.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1095.gif" > is a better tree search tree than <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63424" SRC="img1094.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1094.gif" >.
In fact, since <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63426" SRC="img1095.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1095.gif" > is a <em>perfect binary tree</em><A NAME=19961> </A>,
its height is <IMG WIDTH=104 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64882" SRC="img1308.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1308.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_inline59891" SRC="img403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img403.gif" >.
<P>
The reason that <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63426" SRC="img1095.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1095.gif" > is better than <IMG WIDTH=15 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63424" SRC="img1094.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1094.gif" > is that
it is the more <em>balanced</em> tree.
If we could ensure that the search trees we construct are balanced
then 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 right
subtrees 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=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63812" SRC="img1137.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1137.gif" > internal nodes.
Therefore, it is only possible to create perfect trees with <I>n</I> nodes
for <IMG WIDTH=164 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline64896" SRC="img1309.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1309.gif" >.
Clearly, this is an unsuitable balance condition because
it 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=19966> </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_inline59891" SRC="img403.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img403.gif" >.<LI>
A good balance condition can be maintained efficiently.
I.e., 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="tex2html595" HREF="footnode.html#20181" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/footnode.html#20181"><IMG ALIGN=BOTTOM ALT="gif" SRC="foot_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/foot_motif.gif"></A>
were the first to propose the following
balance 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=19974> </A><A NAME=19975> </A>.
A non-empty binary tree, <IMG WIDTH=107 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63788" SRC="img1135.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1135.gif" >, is AVL balanced if
both <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63784" SRC="img1133.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1133.gif" > and <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63786" SRC="img1134.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1134.gif" > are AVL balanced and
<P> <IMG WIDTH=298 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath64858" SRC="img1310.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1310.gif" ><P>
where <IMG WIDTH=17 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64912" SRC="img1311.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1311.gif" > is the height of <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63784" SRC="img1133.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1133.gif" > and <IMG WIDTH=17 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64916" SRC="img1312.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1312.gif" > is the height of <IMG WIDTH=18 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63786" SRC="img1134.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1134.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 balance
condition are logarithmic in the number of internal nodes.
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theoremsrchtreeii"> </A>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -