page354.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 186 行
HTML
186 行
<HTML><HEAD><TITLE>Complete Trees</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="tex2html5271" HREF="page355.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5269" HREF="page353.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5263" HREF="page353.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5273" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0011210000000000000000">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="page304.html#defnperfectbt"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline65527" SRC="img1379.gif" > internal nodes.Since, the only permissible values of <I>n</I> are<P> <IMG WIDTH=363 HEIGHT=18 ALIGN=BOTTOM ALT="displaymath65519" SRC="img1380.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 structurethat can hold an arbitrary number of objectsso 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=23458> </A><A NAME=23459> </A>of height <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63063" SRC="img1074.gif" >,is a binary tree <IMG WIDTH=79 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65533" SRC="img1381.gif" > with the following properties.<OL><LI> If <I>h</I>=0, <IMG WIDTH=47 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63843" SRC="img1184.gif" > and <IMG WIDTH=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63845" SRC="img1185.gif" >.<LI> For <I>h</I><I>></I>0 there are two possibilities: <OL><LI> <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63147" SRC="img1085.gif" > is a perfect binary tree of height <I>h</I>-1 and <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63149" SRC="img1086.gif" > is a complete binary tree of height <I>h</I>-1; or<LI> <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63147" SRC="img1085.gif" > is a complete binary tree of height <I>h</I>-1 and <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63149" SRC="img1086.gif" > is a perfect binary tree of height <I>h</I>-2. </OL></OL></BLOCKQUOTE><P>Figure <A HREF="page354.html#figtree16"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows an exampleof a complete binary tree of height four.Notice that the left subtree of node 1 is a completebinary 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="page354.html#defncompletebt"><IMG ALIGN=BOTTOM ALT="gif" SRC="../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="page354.html#defncompletebt"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="23640"> </A><A NAME="figtree16"> </A> <IMG WIDTH=575 HEIGHT=226 ALIGN=BOTTOM ALT="figure23468" SRC="img1382.gif" ><BR><STRONG>Figure:</STRONG> A complete binary tree.<BR><P><P>Does there exist a complete binary with exactly <I>n</I> nodesfor every integer <I>n</I><I>></I>0?The following theorem addresses this question indirectly by definingthe relationship between the height of a complete treeand the number of nodes it contains.<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesi"> </A>A complete binary tree of height <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63063" SRC="img1074.gif" > contains at least <IMG WIDTH=15 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline63187" SRC="img1091.gif" >and at most <IMG WIDTH=58 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63175" SRC="img1089.gif" > nodes.</BLOCKQUOTE><P> extbfProofFirst, we prove the lower bound by induction.Let <IMG WIDTH=21 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline65569" SRC="img1383.gif" > be the <em>minimum</em> number of nodes in a completebinary tree of height <I>h</I>.To prove the lower bound we must show that <IMG WIDTH=59 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline65573" SRC="img1384.gif" >.<P><b>Base Case</b>There is exactly one node in a tree of height zero.Therefore, <IMG WIDTH=86 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline65575" SRC="img1385.gif" >.<P><b>Inductive Hypothesis</b>Assume that <IMG WIDTH=59 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline65573" SRC="img1384.gif" > for <IMG WIDTH=111 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63073" SRC="img1077.gif" >, for some <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60883" SRC="img708.gif" >.Consider the complete binary tree of height <I>k</I>+1which has the smallest number of nodes.Its left subtree is a complete tree of height <I>k</I>having the smallest number of nodesand its right subtree is a perfect tree of height <I>k</I>-1.<P>From the inductive hypothesis,there are <IMG WIDTH=13 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58271" SRC="img176.gif" > nodes in the left subtreeand there are exactly <IMG WIDTH=84 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline65591" SRC="img1386.gif" > nodes in the perfect right subtree.Thus,<P> <IMG WIDTH=500 HEIGHT=39 ALIGN=BOTTOM ALT="eqnarray23653" SRC="img1387.gif" ><P>Therefore, by induction <IMG WIDTH=59 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline65573" SRC="img1384.gif" > for all <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63063" SRC="img1074.gif" >,which proves the lower bound.<P>Next, we prove the upper bound by induction.Let <IMG WIDTH=22 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65597" SRC="img1388.gif" > be the <em>maximum</em> number of nodes in a completebinary tree of height <I>h</I>.To prove the upper bound we must show that <IMG WIDTH=103 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline65601" SRC="img1389.gif" >.<P><b>Base Case</b>There is exactly one node in a tree of height zero.Therefore, <IMG WIDTH=114 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline65603" SRC="img1390.gif" >.<P><b>Inductive Hypothesis</b>Assume that <IMG WIDTH=103 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline65601" SRC="img1389.gif" > for <IMG WIDTH=111 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63073" SRC="img1077.gif" >, for some <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60883" SRC="img708.gif" >.Consider the complete binary tree of height <I>k</I>+1which has the largest number of nodes.Its left subtree is a perfect tree of height <I>k</I>and its right subtree is a complete tree of height <I>k</I>having the largest number of nodes.<P>There are exactly <IMG WIDTH=58 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline65617" SRC="img1391.gif" > nodes in the perfect left subtree.From the inductive hypothesis,there are <IMG WIDTH=58 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline65617" SRC="img1391.gif" > nodes in the right subtree.Thus,<P> <IMG WIDTH=500 HEIGHT=38 ALIGN=BOTTOM ALT="eqnarray23665" SRC="img1392.gif" ><P>Therefore, by induction <IMG WIDTH=103 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline65601" SRC="img1389.gif" > for all <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63063" SRC="img1074.gif" >,which proves the upper bound.<P>It follows from Theorem <A HREF="page354.html#theorempqueuesi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>that there exists exactly one complete binary treethat contains exactly <I>n</I> internal nodesfor every integer <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >.It also follows from Theorem <A HREF="page354.html#theorempqueuesi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>that the height of a complete binary tree containing <I>n</I> internal nodesis <IMG WIDTH=81 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65631" SRC="img1393.gif" >.<P>Why are we interested in complete trees?As it turns out, complete trees have some useful characteristics.For example,in the preceding chapter we saw that the internal path length of a tree,i.e., the sum of the depths of all the internal nodes,determines the average time for various operations.A complete binary tree has the nice property thatit has the smallest possible internal path length:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesii"> </A>The internal path length of a binary tree with <I>n</I> nodesis at least as big as the internal path length ofa <em>complete</em> binary tree with <I>n</I> nodes.</BLOCKQUOTE><P> extbfProofConsider a binary tree with <I>n</I> nodes that has the smallest possibleinternal path length.Clearly, there can only be one node at depth zero--the root.Similarly, at most two nodes can be at depth one;at most four nodes can be at depth two; and so on.Therefore, the internal path length of a tree with <I>n</I> nodesis always at least as large as the sum of the first <I>n</I> terms in the series<P> <IMG WIDTH=392 HEIGHT=36 ALIGN=BOTTOM ALT="displaymath65520" SRC="img1394.gif" ><P>But this summation is precisely the internal path lengthof a complete binary tree!<P>Since the depth of the average node in a tree is obtained by dividing the internal path length of the tree by <I>n</I>,Theorem <A HREF="page354.html#theorempqueuesii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> tells us that complete trees are the bestpossible in the sense that the average depth of a node in a completetree is the smallest possible.But how small is small?That is, is does the average depth grow logarithmically with <I>n</I>.The following theorem addresses this question:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesiii"> </A>The <em>internal path length</em><A NAME=23689> </A>of a complete binary tree with <I>n</I> nodes is<P> <IMG WIDTH=438 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath65521" SRC="img1395.gif" ><P></BLOCKQUOTE><P> extbfProofThe proof of Theorem <A HREF="page354.html#theorempqueuesiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is left as an exercise for the reader (Exercise <A HREF="page384.html#exercisepqueuesipl"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<P>From Theorem <A HREF="page354.html#theorempqueuesiii"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> we may conclude thatthe internal path length of a complete tree is <IMG WIDTH=68 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59353" SRC="img402.gif" >.Consequently, the depth of the average node in a complete tree is <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >.<P><BR> <HR><UL> <LI> <A NAME="tex2html5274" HREF="page355.html#SECTION0011211000000000000000">Complete <I>N</I>-ary Trees</A></UL><HR><A NAME="tex2html5271" HREF="page355.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5269" HREF="page353.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5263" HREF="page353.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5273" 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 + -
显示快捷键?