📄 page317.html
字号:
<HTML><HEAD><TITLE>Removing Items from a Binary 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="tex2html4848" HREF="page318.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4846" HREF="page310.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4842" HREF="page316.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4850" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0010430000000000000000">Removing Items from a Binary Search Tree</A></H2><P><A NAME="secsrchtreebstout"> </A><P>When removing an item from a search tree,it is imperative that the tree that remains satisfiesthe data ordering criterion.If the item to be removed is in a leaf node,then it is fairly easy to remove that item from the treesince doing so does not disturb the relative orderof any of the other items in the tree.<P>For example,consider the binary search tree shown in Figure <A HREF="page317.html#figtree14"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a).Suppose we wish to remove the node labeled 4.Since node 4 is a leaf, its subtrees are empty.When we remove it from the tree,the tree remains a valid search treeas shown in Figure <A HREF="page317.html#figtree14"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b).<P><P><A NAME="18975"> </A><A NAME="figtree14"> </A> <IMG WIDTH=575 HEIGHT=190 ALIGN=BOTTOM ALT="figure18750" SRC="img1245.gif" ><BR><STRONG>Figure:</STRONG> Removing a leaf node from a binary search tree.<BR><P><P>To remove a non-leaf node,we move it down in the tree until it becomes a leaf nodesince a leaf node is easily deleted.To move a node down we swap it with anothernode which is further down in the tree.For example, consider the search tree shown in Figure <A HREF="page317.html#figtree15"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (a).Node 1 is not a leaf since it has an empty left subtreebut a non-empty right subtree.To remove node 1, we swap it with the smallest key in its right subtree,which in this case is node 2, Figure <A HREF="page317.html#figtree15"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (b).Since node 1 is now a leaf, it is easily deleted.Notice that the resulting tree remains a valid search tree,as shown in Figure <A HREF="page317.html#figtree15"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> (c).<P><P><A NAME="19214"> </A><A NAME="figtree15"> </A> <IMG WIDTH=575 HEIGHT=207 ALIGN=BOTTOM ALT="figure18981" SRC="img1246.gif" ><BR><STRONG>Figure:</STRONG> Removing a non-leaf node from a binary search tree.<BR><P><P>To move a non-leaf node down in the tree,we either swap it with the smallest key in the right subtreeor with the largest one in the left subtree.At least one such swap is always possible,since the node is a non-leaf and thereforeat least one of its subtrees is non-empty.If after the swap, the node to be deleted is not a leaf,the we push it further down the tree with yet another swap.Eventually, the node must reach the bottom of the treewhere it can be deleted.<P><BR> <HR><UL> <LI> <A NAME="tex2html4851" HREF="page318.html#SECTION0010431000000000000000"><tt>withdraw</tt> Method</A></UL><HR><A NAME="tex2html4848" HREF="page318.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4846" HREF="page310.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4842" HREF="page316.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4850" 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 + -