📄 page298.html
字号:
<HTML><HEAD><TITLE>Search Trees</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="tex2html4626" HREF="page299.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4624" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4618" HREF="page297.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4628" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H1><A NAME="SECTION0010000000000000000000">Search Trees</A></H1><P><A NAME="chapsrchtree"> </A><P>In the preceding chapter we consider trees in whichthe 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 flexibilityin 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 necessaryto do a complete traversal of the tree (in the worst case).<P>In this chapter we consider trees that are designedto 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 treeas 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="tex2html4629" HREF="page299.html#SECTION0010100000000000000000">Basics</A><LI> <A NAME="tex2html4630" HREF="page302.html#SECTION0010200000000000000000">Searching a Search Tree</A><LI> <A NAME="tex2html4631" HREF="page305.html#SECTION0010300000000000000000">Average Case Analysis</A><LI> <A NAME="tex2html4632" HREF="page310.html#SECTION0010400000000000000000">Implementing Search Trees</A><LI> <A NAME="tex2html4633" HREF="page319.html#SECTION0010500000000000000000">AVL Search Trees</A><LI> <A NAME="tex2html4634" HREF="page330.html#SECTION0010600000000000000000"><I>M</I>-Way Search Trees</A><LI> <A NAME="tex2html4635" HREF="page340.html#SECTION0010700000000000000000">B-Trees</A><LI> <A NAME="tex2html4636" HREF="page348.html#SECTION0010800000000000000000">Applications</A><LI> <A NAME="tex2html4637" HREF="page349.html#SECTION0010900000000000000000">Exercises</A><LI> <A NAME="tex2html4638" HREF="page350.html#SECTION00101000000000000000000">Projects</A></UL><HR><A NAME="tex2html4626" HREF="page299.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4624" HREF="book.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4618" HREF="page297.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4628" 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 + -