page373.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 58 行
HTML
58 行
<HTML><HEAD><TITLE>Adding 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="tex2html5491" HREF="page374.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5489" HREF="page371.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5483" HREF="page372.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5493" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0011432000000000000000">Adding Binomial Trees</A></H3><P>Recall that we can combine two binomial trees of the same order, say <I>k</I>,into a single binomial tree of order <I>k</I>+1.Each of the two trees to be combined is heap-ordered.Since the smallest key is at the root of a heap-ordered tree,we know that the root of the result must be the smallerroot of the two trees which are to be combined.Therefore, to combine the two trees,we simply attach the tree with the larger rootunder the root of the tree with the smaller root.For example,Figure <A HREF="page373.html#figbinom3"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> illustrates how two heap-ordered binomial trees of order twoare combined into a single heap-ordered tree of order three.<P><P><A NAME="26881"> </A><A NAME="figbinom3"> </A> <IMG WIDTH=575 HEIGHT=316 ALIGN=BOTTOM ALT="figure26662" SRC="img1503.gif" ><BR><STRONG>Figure:</STRONG> Adding binomial trees.<BR><P><P>The <tt>add</tt> method defined in Program <A HREF="page373.html#progbinomialQueuei"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>provides the means to combine two binomial trees of the same order.The <tt>add</tt> method takes two <tt>BinomialTree</tt>s,<tt>self</tt> and <tt>tree</tt>,and attaches the binomial tree <tt>tree</tt> to the binomial tree <tt>self</tt>.This is only permissible when both trees have the same order.<P><P><A NAME="27122"> </A><A NAME="progbinomialQueuei"> </A> <IMG WIDTH=575 HEIGHT=294 ALIGN=BOTTOM ALT="program26892" SRC="img1504.gif" ><BR><STRONG>Program:</STRONG> <tt>BinomialTree</tt> class <tt>add</tt> method.<BR><P><P>In order to ensure that the resulting binomial tree is heap ordered,the roots of the trees are compared.If necessary, the contents of the nodes are exchangedusing <tt>swapContentsWith</tt> (lines 8-9)before the subtree is attached (line 10).Assuming <tt>swapContentsWith</tt> and <tt>attachSubtree</tt>both run in constant time,the worst-case running time of the <tt>add</tt> method is <IMG WIDTH=106 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline66319" SRC="img1505.gif" >.That is, exactly one comparison and a constant amount of additionalwork is needed to combine two binomial trees.<P><HR><A NAME="tex2html5491" HREF="page374.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5489" HREF="page371.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5483" HREF="page372.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5493" 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 + -
显示快捷键?