page304.html
来自「Data Structures And Algorithms With Obje」· HTML 代码 · 共 63 行
HTML
63 行
<HTML><HEAD><TITLE>Searching a Binary Tree</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="tex2html4702" HREF="page305.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4700" HREF="page302.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4696" HREF="page303.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4704" HREF="page611.html"><IMG WIDTH=43 HEIGHT=24 ALIGN=BOTTOM ALT="index" SRC="../icons/index_motif.gif"></A> <BR><HR><H3><A NAME="SECTION0010202000000000000000">Searching a Binary Tree</A></H3><P>The search method described above applies directly to binary search trees.As above, the search begins at the root node of the tree.If the object of the search, <I>x</I>, matches the root <I>r</I>,the search terminates successfully.If it does not,then if <I>x</I> is less than <I>r</I>,the left subtree is searched;otherwise <I>x</I> must be greater than <I>r</I>,in which case the right subtree is searched.<P>Figure <A HREF="page304.html#figtree13"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A> shows two binary search trees.The tree <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62787" SRC="img1046.gif" > is an example of a particularly bad search treebecause it is not really very tree-like at all.In fact, it is topologically isomorphic with a linear, linked list.In the worst case, a tree which contains <I>n</I> items has height <I>O</I>(<I>n</I>).Therefore, in the worst case an unsuccessful search must visit <I>O</I>(<I>n</I>)internal nodes.<P><P><A NAME="18372"> </A><A NAME="figtree13"> </A> <IMG WIDTH=575 HEIGHT=316 ALIGN=BOTTOM ALT="figure18194" SRC="img1183.gif" ><BR><STRONG>Figure:</STRONG> Examples of search trees.<BR><P><P>On the other hand,tree <IMG WIDTH=15 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline62789" SRC="img1047.gif" > in Figure <A HREF="page304.html#figtree13"><IMG ALIGN=BOTTOM ALT="gif" SRC="../icons/cross_ref_motif.gif"></A>is an example of a particularly good binary search tree.This tree is an instance ofa <em>perfect binary tree</em><A NAME=18377> </A>.<P><BLOCKQUOTE> <b>Definition (Perfect Binary Tree)</b><A NAME="defnperfectbt"> </A>A <em>perfect binary tree</em> of height <IMG WIDTH=37 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63063" SRC="img1074.gif" >is a binary tree <IMG WIDTH=108 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63151" SRC="img1087.gif" > with the following properties:<OL><LI> If <I>h</I>=0, then <IMG WIDTH=47 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63843" SRC="img1184.gif" > and <IMG WIDTH=49 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63845" SRC="img1185.gif" >.<LI> Otherwise, <I>h</I><I>></I>0, in which case both <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63147" SRC="img1085.gif" > and <IMG WIDTH=18 HEIGHT=22 ALIGN=MIDDLE ALT="tex2html_wrap_inline63149" SRC="img1086.gif" > are both perfect binary trees of height <I>h</I>-1.</OL></BLOCKQUOTE><P>It is fairly easy to show that a perfect binary tree of height <I>h</I>has exactly <IMG WIDTH=58 HEIGHT=26 ALIGN=MIDDLE ALT="tex2html_wrap_inline63175" SRC="img1089.gif" > internal nodes.Conversely, the height of a perfect binary tree with <I>n</I> internal nodesis <IMG WIDTH=76 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63861" SRC="img1186.gif" >.If we have a search tree that has the shape of a perfect binary tree,then every unsuccessful search visits exactly <I>h</I>+1 internal nodes,where <IMG WIDTH=106 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline63865" SRC="img1187.gif" >.Thus, the worst case for unsuccessful search in a perfect tree is <IMG WIDTH=56 HEIGHT=24 ALIGN=MIDDLE ALT="tex2html_wrap_inline59347" SRC="img400.gif" >.<P><HR><A NAME="tex2html4702" HREF="page305.html"><IMG WIDTH=37 HEIGHT=24 ALIGN=BOTTOM ALT="next" SRC="../icons/next_motif.gif"></A> <A NAME="tex2html4700" HREF="page302.html"><IMG WIDTH=26 HEIGHT=24 ALIGN=BOTTOM ALT="up" SRC="../icons/up_motif.gif"></A> <A NAME="tex2html4696" HREF="page303.html"><IMG WIDTH=63 HEIGHT=24 ALIGN=BOTTOM ALT="previous" SRC="../icons/previous_motif.gif"></A> <A NAME="tex2html4704" 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 + =
减小字号Ctrl + -
显示快捷键?