page369.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 169 行
HTML
169 行
<HTML><HEAD><TITLE>Binomial 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="tex2html5441" HREF="page370.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5439" HREF="page368.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5433" HREF="page368.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5443" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0011410000000000000000">Binomial Trees</A></H2><P>A binomial tree is a general tree with a very special shape:<P><BLOCKQUOTE> <b>Definition (Binomial Tree)</b><A NAME="defnbinomialtree"> </A>The <em>binomial tree of order <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60883" SRC="img708.gif" ></em> with root <I>R</I>is the tree <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" > defined as follows<OL><LI> If <I>k</I>=0, <IMG WIDTH=109 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65959" SRC="img1446.gif" >. That is, the binomial tree of order zero consists of a single node, <I>R</I>.<LI> If <I>k</I><I>></I>0, <IMG WIDTH=193 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65965" SRC="img1447.gif" >. That is, the binomial tree of order <I>k</I><I>></I>0 comprises the root <I>R</I>, and <I>k</I> binomial subtrees, <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65973" SRC="img1448.gif" >, <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65975" SRC="img1449.gif" >, ..., <IMG WIDTH=34 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline65977" SRC="img1450.gif" >.</OL></BLOCKQUOTE><P>Figure <A HREF="page369.html#figbinom1"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows the first five binomial trees, <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65973" SRC="img1448.gif" >- <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65981" SRC="img1451.gif" >.It follows directly from Definition <A HREF="page369.html#defnbinomialtree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> that the root of <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" >,the binomial tree of order <I>k</I>,has degree <I>k</I>.Since <I>k</I> may arbitrarily large,so too can the degree of the root.Furthermore, the root of a binomial tree has the largest fanout ofany of the nodes in that tree.<P><P><A NAME="26290"> </A><A NAME="figbinom1"> </A> <IMG WIDTH=575 HEIGHT=429 ALIGN=BOTTOM ALT="figure26023" SRC="img1452.gif" ><BR><STRONG>Figure:</STRONG> Binomial trees <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65973" SRC="img1448.gif" >, <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65975" SRC="img1449.gif" >, ..., <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65981" SRC="img1451.gif" >.<BR><P><P>The number of nodes in a binomial tree of order <I>k</I> is a function of <I>k</I>:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesv"> </A>The binomial tree of order <I>k</I>, <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" >,contains <IMG WIDTH=13 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline58271" SRC="img176.gif" > nodes.</BLOCKQUOTE><P> extbfProof (By induction).Let <IMG WIDTH=16 HEIGHT=14 ALIGN=MIDDLE ALT="tex2html_wrap_inline66017" SRC="img1453.gif" > be the number of nodes in <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" >,a binomial tree of order <I>k</I>.<P><b>Base Case</b>By definition, <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65973" SRC="img1448.gif" > consists a single node.Therefore <IMG WIDTH=81 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66025" SRC="img1454.gif" >.<P><b>Inductive Hypothesis</b>Assume that <IMG WIDTH=53 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66027" SRC="img1455.gif" > for <IMG WIDTH=106 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66029" SRC="img1456.gif" >, for some <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66031" SRC="img1457.gif" >.Consider the binomial tree of order <I>l</I>+1:<P> <IMG WIDTH=358 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath65943" SRC="img1458.gif" ><P>Therefore the number of nodes in <IMG WIDTH=31 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66035" SRC="img1459.gif" > is given by<P> <IMG WIDTH=500 HEIGHT=168 ALIGN=BOTTOM ALT="eqnarray26303" SRC="img1460.gif" ><P>Therefore, by induction on <I>l</I>, <IMG WIDTH=53 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66027" SRC="img1455.gif" > for all <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60883" SRC="img708.gif" >.<P>It follows from Theorem <A HREF="page369.html#theorempqueuesv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> that binomial trees only comein sizes that are a power of two.That is, <IMG WIDTH=154 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66043" SRC="img1461.gif" >.Furthermore, for a given power of two,there is exactly one shape of binomial tree.<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesvi"> </A>The height of <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" >, the binomial tree of order <I>k</I>, is <I>k</I>.</BLOCKQUOTE><P> extbfProof (By induction).Let <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66051" SRC="img1462.gif" > be the height of <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" >,a binomial tree of order <I>k</I>.<P><b>Base Case</b>By definition, <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65973" SRC="img1448.gif" > consists a single node.Therefore <IMG WIDTH=45 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66059" SRC="img1463.gif" >.<P><b>Inductive Hypothesis</b>Assume that <IMG WIDTH=45 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66061" SRC="img1464.gif" > for <IMG WIDTH=106 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66029" SRC="img1456.gif" >, for some <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66031" SRC="img1457.gif" >.Consider the binomial tree of order <I>l</I>+1:<P> <IMG WIDTH=358 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath65943" SRC="img1458.gif" ><P>Therefore the height <IMG WIDTH=31 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66035" SRC="img1459.gif" > is given by<P> <IMG WIDTH=500 HEIGHT=75 ALIGN=BOTTOM ALT="eqnarray26325" SRC="img1465.gif" ><P>Therefore, by induction on <I>l</I>, <IMG WIDTH=45 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66061" SRC="img1464.gif" > for all <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline60883" SRC="img708.gif" >.<P>Theorem <A HREF="page369.html#theorempqueuesvi"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> tells us that the height of a binomial tree of order <I>k</I>is <I>k</I> and Theorem <A HREF="page369.html#theorempqueuesv"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> tells us that the number of nodes is <IMG WIDTH=53 HEIGHT=28 ALIGN=MIDDLE ALT="tex2html_wrap_inline66027" SRC="img1455.gif" >.Therefore, the height of <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" > is exactly <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >.<P>Figure <A HREF="page369.html#figbinom2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows that there are two waysto think about the construction of binomial trees.The first way follows directly from the Definition <A HREF="page369.html#defnbinomialtree"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.That is, binomial <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" > consists of a root node to which the <I>k</I> binomial trees <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65973" SRC="img1448.gif" >, <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65975" SRC="img1449.gif" >, ..., <IMG WIDTH=34 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline65977" SRC="img1450.gif" > are attachedas shown in Figure <A HREF="page369.html#figbinom2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a).<P><P><A NAME="26513"> </A><A NAME="figbinom2"> </A> <IMG WIDTH=575 HEIGHT=500 ALIGN=BOTTOM ALT="figure26336" SRC="img1466.gif" ><BR><STRONG>Figure:</STRONG> Two views of binomial tree <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65981" SRC="img1451.gif" >.<BR><P><P>Alternatively, we can think of <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" > as being comprised of two binomialtrees of order <I>k</I>-1.For example, Figure <A HREF="page369.html#figbinom2"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b) shows that <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65981" SRC="img1451.gif" >is made up of two instances of <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66117" SRC="img1467.gif" >.In general, suppose we have two trees of order <I>k</I>-1,say <IMG WIDTH=34 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline66121" SRC="img1468.gif" > and <IMG WIDTH=34 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline66123" SRC="img1469.gif" >,where <IMG WIDTH=244 HEIGHT=25 ALIGN=MIDDLE ALT="tex2html_wrap_inline66125" SRC="img1470.gif" >.Then we can construct a binomial tree of order <I>k</I> by combiningthe trees to get<P> <IMG WIDTH=387 HEIGHT=19 ALIGN=BOTTOM ALT="displaymath65945" SRC="img1471.gif" ><P><P>Why do we call <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" > a <em>binomial</em> tree?It is because the number of nodes at a given depth in the treeis determined by the <em>binomial coefficient</em>.And the binomial coefficient derives its name from the <em>binomial theorem</em>.And the binomial theorem tells us how to compute the <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57913" SRC="img94.gif" > power ofa <em>binomial</em><A NAME=26528> </A>.And a binomial is an expression which consists of two terms, such as <I>x</I>+<I>y</I>.That is why it is called a binomial tree!<P><BLOCKQUOTE> <b>Theorem (Binomial Theorem)</b><A NAME="theorempqueuesbinom"> </A>The <IMG WIDTH=21 HEIGHT=14 ALIGN=BOTTOM ALT="tex2html_wrap_inline57913" SRC="img94.gif" > power of the binomial <I>x</I>+<I>y</I> for <IMG WIDTH=39 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline58503" SRC="img238.gif" >is given by<P> <IMG WIDTH=343 HEIGHT=44 ALIGN=BOTTOM ALT="displaymath65946" SRC="img1472.gif" ><P>where <IMG WIDTH=88 HEIGHT=29 ALIGN=MIDDLE ALT="tex2html_wrap_inline66141" SRC="img1473.gif" > is called the<em>binomial coefficient</em><A NAME=26543> </A><A NAME=26544> </A>.</BLOCKQUOTE><P> extbfProofThe proof of the binomial theoremis left as an exercise for the reader (Exercise <A HREF="page384.html#exercisepqueuesbinom"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).<A NAME="tex2html647" HREF="footnode.html#26707"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/foot_motif.gif"></A><P>The following theorem gives the expressionfor the number of nodes at a given depth in a binomial tree:<P><BLOCKQUOTE> <b>Theorem</b><A NAME="theorempqueuesvii"> </A>The number of nodes at level <I>l</I> in <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" >,the binomial tree of order <I>k</I>, where <IMG WIDTH=63 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66149" SRC="img1474.gif" >,is given by the <em>binomial coefficient</em> <IMG WIDTH=18 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline66151" SRC="img1475.gif" >.</BLOCKQUOTE><P> extbfProof (By induction).Let <IMG WIDTH=34 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66153" SRC="img1476.gif" > be the number of nodes at level <I>l</I> in <IMG WIDTH=19 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65955" SRC="img1445.gif" >,a binomial tree of order <I>k</I>.<P><b>Base Case</b>Since <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65973" SRC="img1448.gif" > contains a single node,there is only one level in the tree, <I>l</I>=0,and exactly one node at that level.Therefore, <IMG WIDTH=107 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline66165" SRC="img1477.gif" >.<P><b>Inductive Hypothesis</b>Assume that <IMG WIDTH=75 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline66167" SRC="img1478.gif" > for <IMG WIDTH=112 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66169" SRC="img1479.gif" >, for some <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63063" SRC="img1074.gif" >.The binomial tree of order <I>h</I>+1 is composed oftwo binomial trees of height <I>h</I>,one attached under the root of the other.Hence, the number of nodes at level <I>l</I> in <IMG WIDTH=34 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline66179" SRC="img1480.gif" >is equal to the number of nodes at level <I>l</I> in <IMG WIDTH=20 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66183" SRC="img1481.gif" >plus the number of nodes at level <I>l</I>-1 in <IMG WIDTH=20 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline66183" SRC="img1481.gif" >:<P> <IMG WIDTH=500 HEIGHT=281 ALIGN=BOTTOM ALT="eqnarray26566" SRC="img1482.gif" ><P>Therefore by induction on <I>h</I>, <IMG WIDTH=75 HEIGHT=31 ALIGN=MIDDLE ALT="tex2html_wrap_inline66167" SRC="img1478.gif" >.<P><HR><A NAME="tex2html5441" HREF="page370.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5439" HREF="page368.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5433" HREF="page368.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5443" 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 + -
显示快捷键?