page300.html

来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 53 行

HTML
53 行
字号 
<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">&#160;</A><P><BLOCKQUOTE> <b>Definition (<I>M</I>-way Search Tree)</b><A NAME="defnmwaytree">&#160;</A>An <em><I>M</I>-way search tree</em><A NAME=18000>&#160;</A><A NAME=18001>&#160;</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>&#160;</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>&#160;</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&nbsp;<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">&#160;</A><A NAME="figtree11">&#160;</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 &#169; 2003</a> by <a href="../signature.html">Bruno R. Preiss, P.Eng.</a>  All rights reserved.</ADDRESS></BODY></HTML>

page300.html - 源码说明

本页面展示了「Data Structures And Algorithms With Object-Oriented Design Patterns In Python (2003) source code and」中的 page300.html 源码文件，采用 HTML 编程语言编写，共 53 行代码。您可以在线阅读完整代码内容，也可以返回资源详情页下载完整源码包进行本地学习和开发。

虫虫下载站收录了大量与Object-Oriented相关的技术资源，包括源代码、技术文档、电路图等，是电子工程师和嵌入式开发者的专业学习平台。

⌨️ 快捷键说明

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