page345.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 107 行
HTML
107 行
<HTML><HEAD><TITLE>Implementation</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="tex2html5167" HREF="page346.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5165" HREF="page344.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5159" HREF="page344.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5169" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0010721000000000000000">Implementation</A></H3><P>Insertion in a B-tree is a two-pass process.The first pass moves down the tree from the rootin order to locate the leaf in which the insertion is to begin.This part of the algorithm is quite similar tothe <tt>find</tt> method given in Program <A HREF="page337.html#progmWayTreed"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The second pass moves from the bottom of the tree back up to the root,splitting nodes and inserting them further up the tree as needed.Program <A HREF="page345.html#progbTreeb"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the code for the first (downward) pass(<tt>insert</tt> method)and the Program <A HREF="page345.html#progbTreec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives the code for the second (upward) pass(<tt>insertUp</tt> method).<P><P><A NAME="22131"> </A><A NAME="progbTreeb"> </A> <IMG WIDTH=575 HEIGHT=352 ALIGN=BOTTOM ALT="program22007" SRC="img1351.gif" ><BR><STRONG>Program:</STRONG> <tt>BTree</tt> class <tt>insert</tt> method.<BR><P><P>In the implementation shown,the downward pass starts at the root node and descends the treeuntil it arrives at an external node.If the external node has no parent,it must be the root and, therefore, the tree is empty.In this case,the root becomes an internal node containing a single keyand two empty subtrees (lines 6-9).Otherwise, we have arrived at an external node in a non-empty treeand the second pass begins by calling <tt>insertUp</tt>to insert the pair <IMG WIDTH=35 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65061" SRC="img1339.gif" > in the parent (line 11).<P>The upward pass of the insertion algorithm is done by therecursive <tt>insertUp</tt> method shown in Program <A HREF="page345.html#progbTreec"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.The <tt>insertUp</tt> method takes two arguments.The first, <tt>obj</tt>, is an objectand the second, <tt>child</tt>, is a <tt>BTree</tt>.It is assumed that all the keys in <tt>child</tt> are strictly greater than<tt>obj</tt>.<P><P><A NAME="22133"> </A><A NAME="progbTreec"> </A> <IMG WIDTH=575 HEIGHT=562 ALIGN=BOTTOM ALT="program22025" SRC="img1352.gif" ><BR><STRONG>Program:</STRONG> <tt>BTree</tt> class <tt>insertUp</tt> method.<BR><P><P>The <tt>insertUp</tt> method calls <tt>findIndex</tt> to determinethe position in the array of keysat which pair (<tt>obj</tt>,<tt>child</tt>) should be inserted (line 8).If this node is not full (line 5),the <tt>insertPair</tt> method is calledto insert the given key and tree at the specified positionin the <tt>_key</tt> and <tt>_subtree</tt> arrays, respectively (line 6).<P>In the event that the node is full,the <tt>insertPair</tt> method returns the key the subtreethat fall off the right end of the array.These are assigned to <tt>extraKey</tt> and <tt>extraSubtree</tt> (line 9-10).<P>The node has now overflowed and it is necessary to balance the B-tree.If the node overflows and it is the root (line 11),then two new B-trees, <tt>left</tt> and <tt>right</tt> are created (lines 12-13).The first <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65005" SRC="img1331.gif" > keys and <IMG WIDTH=41 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64977" SRC="img1328.gif" > subtrees of thegiven node are moved to the <tt>left</tt> tree by the <tt>attachLeftHalfOf</tt>method (line 14);and the last <IMG WIDTH=112 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65163" SRC="img1353.gif" > keysand <IMG WIDTH=110 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65165" SRC="img1354.gif" > subtrees ofthe given node are moved to the <tt>right</tt> treeby the <tt>attachRightHalfOf</tt> method (line 15).Then, the pair (<tt>extraKey</tt>,<tt>extraTree</tt>) is insertedinto the <tt>right</tt> tree (line 16).<P>The left-over key is the one in the middle of the array,i.e., <IMG WIDTH=43 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65101" SRC="img1347.gif" >.Finally, the root node is modifiedso that it contains the two new subtreesand the single left-over key (lines 17-19).<P>If the node overflows and it is not the root,then one new B-tree is created, <tt>right</tt> (line 23).The last <IMG WIDTH=112 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65163" SRC="img1353.gif" > keysand <IMG WIDTH=110 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65165" SRC="img1354.gif" > subtrees of thegiven node are moved to the <tt>left</tt> treeby the <tt>attachRightHalfOf</tt> method (line 24)and the pair (<tt>extraKey</tt>,<tt>extraTree</tt>)is inserted in the <tt>right</tt> tree (line 25).The first <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65005" SRC="img1331.gif" > keys and <IMG WIDTH=41 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64977" SRC="img1328.gif" > subtrees ofthe given node remain attached to it.<P>Finally, the <tt>insertUp</tt> method calls itself recursivelyto insert the left-over key, <IMG WIDTH=43 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline65101" SRC="img1347.gif" >,and the new B-tree, <tt>right</tt>, into the parent of this (line 26).This is the place where the <tt>_parent</tt> instance attribute is needed!<P><HR><A NAME="tex2html5167" HREF="page346.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5165" HREF="page344.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5159" HREF="page344.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5169" 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 + -
显示快捷键?