📄 page300.html
字号:
<HTML><HEAD><TITLE>M-Way 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="tex2html4660" HREF="page301.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4658" HREF="page299.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4652" HREF="page299.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4662" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H2><A NAME="SECTION0010110000000000000000"><I>M</I>-Way Search Trees</A></H2><A NAME="secsrchtreemwaytree"> </A><P><BLOCKQUOTE> <b>Definition (<I>M</I>-way Search Tree)</b><A NAME="defnmwaytree"> </A>An <em><I>M</I>-way search tree</em><A NAME=18000> </A><A NAME=18001> </A> <I>T</I> is a finite set of keys.Either the set is empty, <IMG WIDTH=40 HEIGHT=27 ALIGN=MIDDLE ALT="tex2html_wrap_inline62991" SRC="img1064.gif" >; orthe set consists of <I>n</I> <I>M</I>-way subtrees <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63001" SRC="img1066.gif" >, <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62767" SRC="img1038.gif" >, ..., <IMG WIDTH=32 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline63719" SRC="img1168.gif" >,and <I>n</I>-1 keys, <IMG WIDTH=13 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63723" SRC="img1169.gif" >, <IMG WIDTH=13 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63725" SRC="img1170.gif" >, ..., <IMG WIDTH=31 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline63727" SRC="img1171.gif" >,<P> <IMG WIDTH=385 HEIGHT=16 ALIGN=BOTTOM ALT="displaymath63695" SRC="img1172.gif" ><P>where <IMG WIDTH=76 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63729" SRC="img1173.gif" >, such that the keys and nodes satisfythe following <em>data ordering properties</em><A NAME=18007> </A>:<OL><LI> The keys in each node are distinct and ordered, i.e., <IMG WIDTH=61 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63731" SRC="img1174.gif" > for <IMG WIDTH=91 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63733" SRC="img1175.gif" >.<LI> All the keys contained in subtree <IMG WIDTH=29 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline63735" SRC="img1176.gif" > are less than <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63737" SRC="img1177.gif" >. The tree <IMG WIDTH=29 HEIGHT=20 ALIGN=MIDDLE ALT="tex2html_wrap_inline63735" SRC="img1176.gif" > is called the <em>left subtree</em><A NAME=18013> </A> with respect to the key <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63737" SRC="img1177.gif" >.<LI> All the keys contained in subtree <IMG WIDTH=14 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62823" SRC="img1051.gif" > are greater than <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63737" SRC="img1177.gif" >. The tree <IMG WIDTH=29 HEIGHT=23 ALIGN=MIDDLE ALT="tex2html_wrap_inline63747" SRC="img1178.gif" > is called the <em>right subtree</em> with respect to the key <IMG WIDTH=12 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63737" SRC="img1177.gif" >.</OL></BLOCKQUOTE><P>Figure <A HREF="page300.html#figtree11"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> gives an example of an <I>M</I>-way search tree for <I>M</I>=4.In this case,each of the non-empty nodes of the tree has between one and three keysand at most four subtrees.All the keys in the tree satisfy the data ordering properties.Specifically, the keys in each node are orderedand for each key in the tree,all the keys in the left subtree with respect to the given key areare less than the given key,and all the keys in the right subtree with respect to the given keyare larger than than the given key.Finally, it is important to note that the topology of the treeis not determined by the particular set of keys it contains.<P><P><A NAME="18062"> </A><A NAME="figtree11"> </A> <IMG WIDTH=575 HEIGHT=244 ALIGN=BOTTOM ALT="figure18019" SRC="img1179.gif" ><BR><STRONG>Figure:</STRONG> An <I>M</I>-way search tree.<BR><P><HR><A NAME="tex2html4660" HREF="page301.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4658" HREF="page299.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4652" HREF="page299.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4662" 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 + -