📄 page299.html

📁 wqeqwvrw rkjqhwrjwq jkhrjqwhrwq jkhrwq
💻 HTML
字号:
<HTML>
<HEAD>
<TITLE>Search Trees</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="tex2html5615" HREF="page300.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page300.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="tex2html5613" HREF="book.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/book.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="tex2html5607" HREF="page298.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page298.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="tex2html5617" 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="tex2html5618" 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>
<H1><A NAME="SECTION0011000000000000000000">Search Trees</A></H1>
<P>
<A NAME="chapsrchtree">&#160;</A>
<P>
In the preceding chapter we consider trees in which
the relative positions of the nodes in the tree are unconstrained.
In other words,
a given item may appear anywhere in the tree.
Clearly, this allows us complete flexibility
in the kind of tree that we may construct.
And depending on the application,
this may be precisely what we need.
However, if we lose track of an item,
in order to find it again it may be necessary
to do a complete traversal of the tree (in the worst case).
<P>
In this chapter we consider trees that are designed
to support efficient search operations.
In order to make it easier to search,
we constrain the relative positions of the items in the tree.
In addition,
we show that by constraining the <em>shape</em> of the tree
as well as the relative positions of the items in the tree,
search operations can be made even more efficient.
<P>
<BR> <HR>
<UL> 
<LI> <A NAME="tex2html5619" HREF="page300.html#SECTION0011100000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page300.html#SECTION0011100000000000000000">Basics</A>
<LI> <A NAME="tex2html5620" HREF="page303.html#SECTION0011200000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page303.html#SECTION0011200000000000000000">Searching a Search Tree</A>
<LI> <A NAME="tex2html5621" HREF="page306.html#SECTION0011300000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page306.html#SECTION0011300000000000000000">Average Case Analysis</A>
<LI> <A NAME="tex2html5622" HREF="page311.html#SECTION0011400000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page311.html#SECTION0011400000000000000000">Implementing Search Trees</A>
<LI> <A NAME="tex2html5623" HREF="page320.html#SECTION0011500000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page320.html#SECTION0011500000000000000000">AVL Search Trees</A>
<LI> <A NAME="tex2html5624" HREF="page330.html#SECTION0011600000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page330.html#SECTION0011600000000000000000"><I>M</I>-Way Search Trees</A>
<LI> <A NAME="tex2html5625" HREF="page340.html#SECTION0011700000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page340.html#SECTION0011700000000000000000">B-Trees</A>
<LI> <A NAME="tex2html5626" HREF="page349.html#SECTION0011800000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page349.html#SECTION0011800000000000000000">Applications</A>
<LI> <A NAME="tex2html5627" HREF="page350.html#SECTION0011900000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page350.html#SECTION0011900000000000000000">Exercises</A>
<LI> <A NAME="tex2html5628" HREF="page351.html#SECTION00111000000000000000000" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page351.html#SECTION00111000000000000000000">Projects</A>
</UL>
<HR><A NAME="tex2html5615" HREF="page300.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page300.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="tex2html5613" HREF="book.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/book.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="tex2html5607" HREF="page298.html" tppabs="http://dictator.uwaterloo.ca/Bruno.Preiss/books/opus4/html/page298.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="tex2html5617" 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="tex2html5618" 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 + -