page338.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 57 行
HTML
57 行
<HTML><HEAD><TITLE>Inserting Items into an M-Way Search Tree</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="tex2html5087" HREF="page339.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5085" HREF="page330.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5079" HREF="page337.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5089" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0010630000000000000000">Inserting Items into an <I>M</I>-Way Search Tree</A></H2><P>The method for inserting items in an <I>M</I>-way search treefollows directly from the algorithm for insertion in a binary search tree givenin Section <A HREF="page315.html#secsrchtreebstin"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The added wrinkle in an <I>M</I>-way tree is that an internal nodemay contain between 1 and <I>M</I>-1 keyswhereas an internal node in a binary tree must contain exactly one key.<P>Program <A HREF="page338.html#progmWayTreee"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the implementationof the <tt>insert</tt> method of the <tt>MWayTree</tt> class.In addition to <tt>self</tt>,this method takes as its argument the objectto be inserted into the search tree.<P><P><A NAME="21043"> </A><A NAME="progmWayTreee"> </A> <IMG WIDTH=575 HEIGHT=485 ALIGN=BOTTOM ALT="program20947" SRC="img1323.gif" ><BR><STRONG>Program:</STRONG> <tt>MWayTree</tt> class <tt>insert</tt> method.<BR><P><P>The general algorithm for insertion is to search for the itemto be inserted and then to insert it at the point where the search terminates.If the search terminates at an external node,that node is transformed to an internal node of the form <IMG WIDTH=53 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64909" SRC="img1324.gif" >,where <I>x</I> is the key just inserted (lines 5-8).<P>If the search terminates at an internal node,we insert the new item into the sorted list of keys at the appropriate offset.Inserting the key <I>x</I> in the array of keys moves all the keys larger than <I>x</I>and the associated subtrees to the right one position (lines 14-18).The hole in the list of subtrees is filled with an empty tree (line 19).<P>The preceding section gives the running time for a searchin an <I>M</I>-way search tree as<P> <IMG WIDTH=415 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath64844" SRC="img1321.gif" ><P>where <I>h</I> is the height of the tree.The additional time required to insert the item into the nodeonce the correct node has been located is <I>O</I>(<I>M</I>).Therefore, the total running time for the<tt>insert</tt> algorithm given in Program <A HREF="page338.html#progmWayTreee"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> is<P> <IMG WIDTH=445 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath64896" SRC="img1325.gif" ><P><HR><A NAME="tex2html5087" HREF="page339.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5085" HREF="page330.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5079" HREF="page337.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5089" 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 + -
显示快捷键?