📄 page287.html

📁 wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq
💻 HTML
字号:
<HTML>
<HEAD>
<TITLE>Key, AttachKey and DetachKey
Member Functions</TITLE>
</HEAD>
<BODY bgcolor="#FFFFFF">
 <img src="cover75.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cover75.gif" alt="Logo" align=right>
<b>Data Structures and Algorithms 
with Object-Oriented Design Patterns in C++</b><br>
<A NAME="tex2html5477" HREF="page288.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page288.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html5475" HREF="page282.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page282.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html5469" HREF="page286.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page286.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html5479" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html5480" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <BR><HR>
<H3><A NAME="SECTION0010645000000000000000"><tt>Key</tt>, <tt>AttachKey</tt> and <tt>DetachKey</tt>
Member Functions</A></H3>
<P>
Program&nbsp;<A HREF="page286.html#prognarytree2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page286.html#prognarytree2c"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A> also defines three functions for manipulating
the root of an <I>N</I>-ary tree.
The first, <tt>Key</tt>, is an accessor which returns a reference to the
object contained in the root node of the tree.
Clearly, this operation is not defined for the empty tree.
If the tree is not empty, the running time of this routine is <I>O</I>(1).
<P>
The purpose of <tt>AttachKey</tt> is to insert the specified object into a
given <I>N</I>-ary tree at the root node.
This operation is only defined for an empty tree.
The <tt>AttachKey</tt> routine takes as its lone argument a reference to the
object to be inserted in the root node
and makes the <tt>key</tt> member variable point at the given object.
Since the node is no longer empty,
it must have exactly <I>N</I> subtrees.
Therefore, <I>N</I> new empty subtrees are created and attached to the node.
The running time is <I>O</I>(<I>N</I>) since <I>N</I> subtrees are created,
and the running time of the constructor for an empty <I>N</I>-ary tree takes <I>O</I>(1).
<P>
Finally, <tt>DetachKey</tt> is used
to remove the object from the root of a tree.
In order that the tree which remains still conforms
to Definition&nbsp;<A HREF="page255.html#defnnarytree" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page255.html#defnnarytree"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>,
it is only permissible to remove the root from a leaf node.
And upon removal, the leaf node becomes an empty tree.
The implementation given in Program&nbsp;<A HREF="page286.html#prognarytree2c" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page286.html#prognarytree2c"><IMG  ALIGN=BOTTOM ALT="gif" SRC="cross_ref_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/cross_ref_motif.gif"></A>
throws an exception if an attempt is made to remove the root
from a non-leaf node.
Otherwise, the node is a leaf which means that its <I>N</I> subtrees are all empty.
When the root is detached,
all the subtrees are deleted.
The running time of this routine is clearly <I>O</I>(<I>N</I>)
since there are <I>N</I> empty subtrees to be deleted
and the cost of deleting an empty <I>N</I>-ary tree is constant.
<P>
<HR><A NAME="tex2html5477" HREF="page288.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page288.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="next_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/next_motif.gif"></A> <A NAME="tex2html5475" HREF="page282.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page282.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="up_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/up_motif.gif"></A> <A NAME="tex2html5469" HREF="page286.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page286.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="previous_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/previous_motif.gif"></A> <A NAME="tex2html5479" HREF="page9.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page9.html"><IMG WIDTH=65 HEIGHT=24 ALIGN=BOTTOM ALT="contents" SRC="contents_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/contents_motif.gif"></A> <A NAME="tex2html5480" HREF="page620.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page620.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="index_motif.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/index_motif.gif"></A> <P><ADDRESS>
<img src="bruno.gif" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/icons/bruno.gif" alt="Bruno" align=right>
<a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/copyright.html">Copyright &#169; 1997</a> by <a href="javascript:if(confirm('http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html  \n\nThis file was not retrieved by Teleport Pro, because it is addressed on a domain or path outside the boundaries set for its Starting Address.  \n\nDo you want to open it from the server?'))window.location='http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html'" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.

</ADDRESS>
</BODY>
</HTML>
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -