📄 chap13.htm
字号:
<HTML><HEAD><TITLE>Intro to Algorithms: CHAPTER 13: BINARY SEARCH TREES</TITLE></HEAD><BODY BGCOLOR="#FFFFFF"><a href="chap14.htm"><img align=right src="../../images/next.gif" alt="Next Chapter" border=0></A><a href="toc.htm"><img align=right src="../../images/toc.gif" alt="Return to Table of Contents" border=0></A><a href="chap12.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A><h1><a name="07d7_0001">CHAPTER 13: BINARY SEARCH TREES<a name="07d7_0001"></h1><P>Search trees are data structures that support many dynamic-set operations, including <FONT FACE="Courier New" SIZE=2>SEARCH</FONT>, <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>MAXIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>PREDECESSOR</FONT>, <FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT>, <FONT FACE="Courier New" SIZE=2>INSERT</FONT>, and <FONT FACE="Courier New" SIZE=2>DELETE</FONT>. Thus, a search tree can be used both as a dictionary and as a priority queue.<P>Basic operations on a binary search tree take time proportional to the height of the tree. For a complete binary tree with <I>n</I> nodes, such operations run in <img src="../images/bound.gif">(lg <I>n</I>) worst-case time. If the tree is a linear chain of <I>n</I> nodes, however, the same operations take <img src="../images/bound.gif">(<I>n</I>) worst-case time. We shall see in Section 13.4 that the height of a randomly built binary search tree is <I>O</I>(lg <I>n</I>), so that basic dynamic-set operations take <img src="../images/bound.gif">(lg <I>n</I>) time.<P>In practice, we can't always guarantee that binary search trees are built randomly, but there are variations of binary search trees whose worst-case performance on basic operations can be guaranteed to be good. Chapter 14 presents one such variation, red-black trees, which have height <I>O</I>(lg <I>n</I>). Chapter 19 introduces B-trees, which are particularly good for maintaining data bases on random-access, secondary (disk) storage.<P>After presenting the basic properties of binary search trees, the following sections show how to walk a binary search tree to print its values in sorted order, how to search for a value in a binary search tree, how to find the minimum or maximum element, how to find the predecessor or successor of an element, and how to insert into or delete from a binary search tree. The basic mathematical properties of trees were introduced in Chapter 5.<P><h1><a name="07d9_1488">13.1 What is a binary search tree?<a name="07d9_1488"></h1><P><a name="07d9_147e"><a name="07d9_147f"><a name="07d9_1480">A binary search tree is organized, as the name suggests, in a binary tree, as shown in Figure 13.1. Such a tree can be represented by a linked data structure in which each node is an object. In addition to a <I>key</I> field, each node contains fields <I>left, right,</I> and <I>p</I> that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate field contains the value <FONT FACE="Courier New" SIZE=2>NIL</FONT>. The root node is the only node in the tree whose parent field is <FONT FACE="Courier New" SIZE=2>NIL</FONT>.<P><img src="245_a.gif"><P><h4><a name="07d9_1489">Figure 13.1 Binary search trees. For any node x, the keys in the left subtree of x are at most key[x], and the keys in the right subtree of x are at least key[x]. Different binary search trees can represent the same set of values. The worst-case running time for most search-tree operations is proportional to the height of the tree. (a) A binary search tree on 6 nodes with height 2. (b) A less efficient binary search tree with height 4 that contains the same keys.<a name="07d9_1489"></sub></sup></h4><P><a name="07d9_1481">The keys in a binary search tree are always stored in such a way as to satisfy the <I><B>binary-search-tree property</I></B>:<P>Let <I>x</I> be a node in a binary search tree. If <I>y</I> is a node in the left subtree of <I>x,</I> then <I>key</I>[<I>y</I>]<I> </I><img src="../images/lteq12.gif"> key<I>[</I>x<I>]</I>.<I> If </I>y<I> is a node in the right subtree of </I>x,<I> then </I>key<I>[</I>x<I>]</I> <I><img src="../images/lteq12.gif"> key</I>[<I>y</I>]<I>.</I><P>Thus, in Figure 13.1(a), the key of the root is 5, the keys 2, 3, and 5 in its left subtree are no larger than 5, and the keys 7 and 8 in its right subtree are no smaller than 5. The same property holds for every node in the tree. For example, the key 3 in Figure 13.1(a) is no smaller than the key 2 in its left subtree and no larger than the key 5 in its right subtree.<P><a name="07d9_1482"><a name="07d9_1483"><a name="07d9_1484"><a name="07d9_1485"><a name="07d9_1486">The binary-search-tree property allows us to print out all the keys in a binary search tree in sorted order by a simple recursive algorithm, called an <I><B>inorder tree walk</I></B><I>.</I> This algorithm derives its name from the fact that the key of the root of a subtree is printed between the values in its left subtree and those in its right subtree. (Similarly, a <I><B>preorder tree walk</I></B> prints the root before the values in either subtree, and a <I><B>postorder tree walk</I></B> prints the root after the values in its subtrees.) To use the following procedure to print all the elements in a binary search tree <I>T</I>, we call <FONT FACE="Courier New" SIZE=2>INORDER</FONT>-<FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>WALK</FONT>( <I>root</I>[<I>T</I>]).<P><pre><a name="07d9_1487">INORDER-TREE-WALK(<I>x</I>)</sub></sup></pre><P><pre>1 <B>if</B> <I>x</I> <img src="../images/noteq.gif"> NIL</sub></sup></pre><P><pre>2 <B>then</B> INORDER-TREE-WALK (<I>left</I>[<I>x</I>])</sub></sup></pre><P><pre>3 print <I>key</I>[<I>x</I>]</sub></sup></pre><P><pre>4 INORDER-TREE-WALK (<I>right</I>[<I>x</I>])</sub></sup></pre><P>As an example, the inorder tree walk prints the keys in each of the two binary search trees from Figure 13.1 in the order 2, 3, 5, 5, 7, 8. The correctness of the algorithm follows by induction directly from the binary-search-tree property. It takes <img src="../images/bound.gif">(<I>n</I>) time to walk an <I>n</I>-node binary search tree, since after the initial call, the procedure is called recursively exactly twice for each node in the tree--once for its left child and once for its right child.<P><h2><a name="07da_148c">Exercises<a name="07da_148c"></h2><P><a name="07da_148d">13.1-1<a name="07da_148d"><P>Draw binary search trees of height 2, 3, 4, 5, and 6 on the set of keys {1, 4, 5, 10, 16, 17, 21}.<P><a name="07da_148e">13.1-2<a name="07da_148e"><P><a name="07da_1488"><a name="07da_1489">What is the difference between the binary-search-tree property and the heap property (7.1)? Can the heap property be used to print out the keys of an <I>n</I>-node tree in sorted order in <I>O</I>(<I>n</I>) time? Explain how or why not.<P><a name="07da_148f">13.1-3<a name="07da_148f"><P><a name="07da_148a">Give a nonrecursive algorithm that performs an inorder tree walk. (<I>Hint: </I>There is an easy solution that uses a stack as an auxiliary data structure and a more complicated but elegant solution that uses no stack but assumes that two pointers can be tested for equality.)<P><a name="07da_1490">13.1-4<a name="07da_1490"><P>Give recursive algorithms that perform preorder and postorder tree walks in <img src="../images/bound.gif">(<I>n</I>) time on a tree of <I>n</I> nodes.<P><a name="07da_1491">13.1-5<a name="07da_1491"><P><a name="07da_148b">Argue that since sorting <I>n</I> elements takes <img src="../images/omega12.gif"> (<I>n </I>lg<I> n</I>) time in the worst case in the comparison model, any comparison-based algorithm for constructing a binary search tree from an arbitrary list of <I>n</I> elements takes <img src="../images/omega12.gif"> (<I>n </I>lg<I> n</I>)<I> </I>time in the worst case.<P><P><P><h1><a name="07db_148d">13.2 Querying a binary search tree<a name="07db_148d"></h1><P><a name="07db_148c">The most common operation performed on a binary search tree is searching for a key stored in the tree. Besides the <FONT FACE="Courier New" SIZE=2>SEARCH</FONT> operation, binary search trees can support such queries as <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>MAXIMUM</FONT>, <FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT>, and <FONT FACE="Courier New" SIZE=2>PREDECESSOR</FONT>. In this section, we shall examine these operations and show that each can be supported in time <I>O</I>(<I>h</I>) on a binary search tree of height <I>h.</I><P><img src="247_a.gif"><P><h4><a name="07db_148e">Figure 13.2 Queries on a binary search tree. To search for the key 13 in the tree, the path 15 <img src="../images/arrow12.gif"> 6 <img src="../images/arrow12.gif"> 7 <img src="../images/arrow12.gif"> 13 is followed from the root. The minimum key in the tree is 2, which can be found by following left pointers from the root. The maximum key 20 is found by following right pointers from the root. The successor of the node with key 15 is the node with key 17, since it is the minimum key in the right subtree of 15. The node with key 13 has no right subtree, and thus its successor is its lowest ancestor whose left child is also an ancestor. In this case, the node with key 15 is its successor.<a name="07db_148e"></sub></sup></h4><P><h2>Searching</h2><P><a name="07dc_148d"><a name="07dc_148e">We use the following procedure to search for a node with a given key in a binary search tree. Given a pointer to the root of the tree and a key <I>k,</I> <FONT FACE="Courier New" SIZE=2>TREE-</FONT><FONT FACE="Courier New" SIZE=2>SEARCH</FONT> returns a pointer to a node with key <I>k</I> if one exists; otherwise, it returns <FONT FACE="Courier New" SIZE=2>NIL</FONT>.<P><pre><a name="07dc_148f">TREE-SEARCH (<I>x, k</I>)</sub></sup></pre><P><pre>1 <B>if</B> <I>x</I> = NIL or <I>k = key</I>[<I>x</I>]</sub></sup></pre><P><pre>2 <B>then return</B> <I>x</I></sub></sup></pre><P><pre>3 <B>if</B> <I>k < key</I>[<I>x</I>]</sub></sup></pre><P><pre>4 <B>then return</B> TREE-SEARCH <I>(left</I>[<I>x</I>],<I> k)</I></sub></sup></pre><P><pre>5 <B>else return</B> TREE-SEARCH <I>(right</I>[<I>x</I>],<I> k)</I></sub></sup></pre><P>The procedure begins its search at the root and traces a path downward in the tree, as shown in Figure 13.2. For each node <I>x </I>it encounters, it compares the key <I>k</I> with <I>key</I>[<I>x</I>]<I>.</I> If the two keys are equal, the search terminates. If <I>k</I> is smaller than <I>key</I>[<I>x</I>]<I>,</I> the search continues in the left subtree of <I>x,</I> since the binary-search-tree property implies that <I>k</I> could not be stored in the right subtree. Symmetrically, if <I>k</I> is larger than <I>key</I>[<I>k</I>]<I>,</I> the search continues in the right subtree. The nodes encountered during the recursion form a path downward from the root of the tree, and thus the running time of <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>SEARCH</FONT> is <I>O</I>(<I>h</I>)<I>,</I> where <I>h</I> is the height of the tree.<P>The same procedure can be written iteratively by "unrolling" the recursion into a <B>while</B> loop. On most computers, this version is more efficient.<P><pre><a name="07dc_1490">ITERATIVE-TREE-SEARCH (<I>x,k</I>)</sub></sup></pre><P><pre>1 <B>while</B> <I>x</I> <img src="../images/noteq.gif"> NIL and <I>k</I> <img src="../images/noteq.gif"> <I>key</I>[<I>x</I>]</sub></sup></pre><P><pre>2 <B>do if</B> <I>k</I> < <I>key</I>[<I>x</I>]</sub></sup></pre><P><pre>3 <B>then</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>left</I>[<I>x</I>]</sub></sup></pre><P><pre>4 <B>else</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>right</I>[<I>x</I>]</sub></sup></pre><P><pre>5 <B>return</B> <I>x</I></sub></sup></pre><P><P><h2>Minimum and maximum</h2><P><a name="07dd_1491"><a name="07dd_1492"><a name="07dd_1493"><a name="07dd_1494">An element in a binary search tree whose key is a minimum can always be found by following <I>left</I> child pointers from the root until a <FONT FACE="Courier New" SIZE=2>NIL</FONT> is encountered, as shown in Figure 13.2. The following procedure returns a pointer to the minimum element in the subtree rooted at a given node <I>x.</I><P><pre><a name="07dd_1495">TREE-MINIMUM (<I>x</I>)</sub></sup></pre><P><pre>1 <B>while</B> <I>left</I>[<I>x</I>] <img src="../images/noteq.gif"> NIL</sub></sup></pre><P><pre>2 <B>do</B> <I>x</I> <img src="../images/arrlt12.gif"> <I>left</I>[<I>x</I>]</sub></sup></pre><P><pre>3 <B>return</B> <I>x</I></sub></sup></pre><P>The binary-search-tree property guarantees that <FONT FACE="Courier New" SIZE=2>TREE</FONT>-<FONT FACE="Courier New" SIZE=2>MINIMUM</FONT> is correct. If a node <I>x</I> has no left subtree, then since every key in the right subtree of <I>x</I> is at least as large as <I>key</I>[<I>x</I>]<I>,</I> the minimum key in the subtree rooted at <I>x</I> is <I>key</I>[<I>x</I>]<I>.</I> If node <I>x</I> has a left subtree, then since no key in the right subtree is smaller than <I>key</I>[<I>x</I>] and every key in the left subtree is not larger than <I>key</I>[<I>x</I>], the minimum key in the subtree rooted at <I>x</I> can be found in the subtree rooted at <I>left</I>[<I>x</I>]<I>.</I><P>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -