📄 page347.html
字号:
<HTML><HEAD><TITLE>Removing Items from a B-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="tex2html5185" HREF="page348.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5183" HREF="page340.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5179" HREF="page346.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5187" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0010730000000000000000">Removing Items from a B-Tree</A></H2><P>The algorithm for removing items from a B-treeis similar to the algorithm for removing item from an AVL tree.That is, once the item to be removed has be found,it is pushed down the tree to a leaf node where it can be easily deleted.When an item is deleted from a nodeit is possible that the number of keys remainingis less than <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65005" SRC="img1331.gif" >.In this case, balancing is necessary.<P>The algorithm of balancing after deletion is like the balancingafter insertion in that it progresses from the leaf nodeup the tree toward the root.Given a node <I>T</I> which has <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65203" SRC="img1361.gif" > keys,there are four cases to consider.<P>In the first case, <I>T</I> is the root.If no keys remain, <I>T</I> becomes the empty tree.Otherwise, no balancing is needed because the root is permitted to haveas few as two subtrees and one key.For the remaining cases <I>T</I> is not the root.<P>In the second case <I>T</I> has <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65203" SRC="img1361.gif" > keysand it also has a sibling immediately on the leftwith at least <IMG WIDTH=41 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64977" SRC="img1328.gif" > keys.The tree can be balanced by doingan LL rotation<A NAME=22070> </A><A NAME=22071> </A>as shown in Figure <A HREF="page347.html#figbtree4"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.Notice that after the rotation,both siblings have at least <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65005" SRC="img1331.gif" > keys.Furthermore, the heights of the siblings remain unchanged.Therefore, the resulting tree is a valid B-tree.<P><P><A NAME="22572"> </A><A NAME="figbtree4"> </A> <IMG WIDTH=575 HEIGHT=365 ALIGN=BOTTOM ALT="figure22073" SRC="img1362.gif" ><BR><STRONG>Figure:</STRONG> LL rotation in a B-tree.<BR><P><P>The third case is the left-right mirror of the second case.That is, <I>T</I> has <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65203" SRC="img1361.gif" > keysand it also has a sibling immediately on the rightwith a least <IMG WIDTH=41 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline64977" SRC="img1328.gif" > keys.In this case, the tree can be balanced by doing anRR rotation<A NAME=22575> </A><A NAME=22576> </A>.<P>In the fourth and final case, <I>T</I> has <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65203" SRC="img1361.gif" > keys,and its immediate sibling(s) have <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65005" SRC="img1331.gif" > keys.In this case, the sibling(s) cannot give-up a key in a rotationbecause they already have the minimum number of keys.The solution is to <em>merge</em><A NAME=22578> </A><I>T</I> with one of its siblingsas shown in Figure <A HREF="page347.html#figbtree5"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>.<P><P><A NAME="23020"> </A><A NAME="figbtree5"> </A> <IMG WIDTH=575 HEIGHT=365 ALIGN=BOTTOM ALT="figure22580" SRC="img1363.gif" ><BR><STRONG>Figure:</STRONG> Merging nodes in a B-tree.<BR><P><P>The merged node contains <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65203" SRC="img1361.gif" > keys from <I>T</I>, <IMG WIDTH=71 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65005" SRC="img1331.gif" > keys from the sibling,and one key from the parent (the key <I>x</I> in Figure <A HREF="page347.html#figbtree5"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>).The resulting node contains <IMG WIDTH=80 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline65409" SRC="img1364.gif" > keys altogether,which is <I>M</I>-2 if <I>M</I> is even and <I>M</I>-1 if <I>M</I> is odd.Either way, the resulting node contains no more than <I>M</I>-1 keysand is a valid B-tree node.Notice that in this case a key has been removed from the parent of <I>T</I>.Therefore, it may be necessary to balance the parent.Balancing the parent may necessitate balancing the grandparent,and so on, up the tree to the root.<P><HR><A NAME="tex2html5185" HREF="page348.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html5183" HREF="page340.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html5179" HREF="page346.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html5187" 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 + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -