page355.html
来自「wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq」· HTML 代码 · 共 186 行 · 第 1/2 页
HTML
186 行
<HTML>
<HEAD>
<TITLE>Complete 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="tex2html6316" HREF="page356.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page356.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="tex2html6314" HREF="page354.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page354.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="tex2html6308" HREF="page354.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page354.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="tex2html6318" 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="tex2html6319" 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>
<H2><A NAME="SECTION0012210000000000000000">Complete Trees</A></H2>
<A NAME="secpqueuescomplete"> </A>
<P>
The preceding chapter introduces the idea of a <em>perfect tree</em>
(see Definition <A HREF="page305.html#defnperfectbt" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page305.html#defnperfectbt"><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>).
Complete trees and perfect trees are closely related,
yet quite distinct.
As pointed out in the preceding chapter,
a perfect binary tree of height <I>h</I>
has exactly <IMG WIDTH=90 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66162" SRC="img1433.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1433.gif" > internal nodes.
Since, the only permissible values of <I>n</I> are
<P> <IMG WIDTH=365 HEIGHT=18 ALIGN=BOTTOM ALT="displaymath66154" SRC="img1434.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1434.gif" ><P>
there is no <em>perfect</em> binary tree which contains,
say 2, 4, 5, or 6 nodes.
<P>
However, we want a data structure
that can hold an arbitrary number of objects
so we cannot use a perfect binary tree.
Instead, we use a <em>complete binary tree</em>,
which is defined as follows:
<P>
<BLOCKQUOTE> <b>Definition (Complete Binary Tree)</b><A NAME="defncompletebt"> </A>
A <em>complete binary tree</em><A NAME=24040> </A><A NAME=24041> </A>
of height <IMG WIDTH=36 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63700" SRC="img1122.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1122.gif" >,
is a binary tree <IMG WIDTH=77 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66168" SRC="img1435.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1435.gif" > with the following properties.
<OL><LI> If <I>h</I>=0, <IMG WIDTH=47 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline64524" SRC="img1239.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1239.gif" > and <IMG WIDTH=48 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline64526" SRC="img1240.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1240.gif" >.<LI> For <I>h</I><I>></I>0 there are two possibilities:
<OL><LI> <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" > is a perfect binary tree of height <I>h</I>-1
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" > is a complete binary tree of height <I>h</I>-1; or<LI> <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" > is a complete binary tree of height <I>h</I>-1
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" > is a perfect binary tree of height <I>h</I>-2.
</OL></OL></BLOCKQUOTE>
<P>
Figure <A HREF="page355.html#figtree16" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page355.html#figtree16"><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> shows an example
of a complete binary tree of height four.
Notice that the left subtree of node 1 is a complete
binary tree of height three;
and the right subtree is a perfect binary tree of height two.
This corresponds to case 2 (b) of Definition <A HREF="page355.html#defncompletebt" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page355.html#defncompletebt"><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>.
Similarly, the left subtree of node 2 is a perfect binary tree of height two;
and the right subtree is a complete binary tree of height two.
This corresponds to case 2 (a) of Definition <A HREF="page355.html#defncompletebt" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page355.html#defncompletebt"><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>.
<P>
<P><A NAME="24218"> </A><A NAME="figtree16"> </A> <IMG WIDTH=575 HEIGHT=226 ALIGN=BOTTOM ALT="figure24050" SRC="img1436.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1436.gif" ><BR>
<STRONG>Figure:</STRONG> A Complete Binary Tree<BR>
<P>
<P>
Does there exist an complete binary with exactly <I>n</I> nodes
for every integer <I>n</I><I>></I>0?
The following theorem addresses this question indirectly by defining
the relationship between the height of a complete tree
and the number of nodes it contains.
<P>
<BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesi"> </A>
A complete binary tree of height <IMG WIDTH=36 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63700" SRC="img1122.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1122.gif" > contains at least <IMG WIDTH=14 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline63824" SRC="img1139.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1139.gif" >
and at most <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" > nodes.
</BLOCKQUOTE>
<P>
extbfProof
First, we prove the lower bound by induction.
Let <IMG WIDTH=20 HEIGHT=15 ALIGN=MIDDLE ALT="tex2html_wrap_inline66204" SRC="img1437.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1437.gif" > be the <em>minimum</em> number of nodes in a complete
binary tree of height <I>h</I>.
To prove the lower bound we must show that <IMG WIDTH=57 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66208" SRC="img1438.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1438.gif" >.
<P>
<b>Base Case</b>
There is exactly one node in a tree of height zero.
Therefore, <IMG WIDTH=86 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline66210" SRC="img1439.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1439.gif" >.
<P>
<b>Inductive Hypothesis</b>
Assume that <IMG WIDTH=57 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66208" SRC="img1438.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1438.gif" > for <IMG WIDTH=114 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63710" SRC="img1125.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1125.gif" >, for some <IMG WIDTH=36 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline61524" SRC="img761.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img761.gif" >.
Consider the complete binary tree of height <I>k</I>+1
which has the smallest number of nodes.
Its left subtree is a complete tree of height <I>k</I>
having the smallest number of nodes
and its right subtree is a perfect tree of height <I>k</I>-1.
<P>
From the inductive hypothesis,
there are <IMG WIDTH=14 HEIGHT=13 ALIGN=BOTTOM ALT="tex2html_wrap_inline58821" SRC="img179.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img179.gif" > nodes in the left subtree
and there are exactly <IMG WIDTH=83 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66226" SRC="img1440.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1440.gif" > nodes in the perfect right subtree.
Thus,
<P> <IMG WIDTH=500 HEIGHT=38 ALIGN=BOTTOM ALT="eqnarray24231" SRC="img1441.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1441.gif" ><P>
Therefore, by induction <IMG WIDTH=57 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66208" SRC="img1438.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1438.gif" > for all <IMG WIDTH=36 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63700" SRC="img1122.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1122.gif" >,
which proves the lower bound.
<P>
Next, we prove the upper bound by induction.
Let <IMG WIDTH=20 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66232" SRC="img1442.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/img1442.gif" > be the <em>maximum</em> number of nodes in a complete
⌨️ 快捷键说明
复制代码Ctrl + C
搜索代码Ctrl + F
全屏模式F11
增大字号Ctrl + =
减小字号Ctrl + -
显示快捷键?