📄 partiii.htm
字号:
<HTML><HEAD><TITLE>Intro to Algorithms: PART III: Data Structures</TITLE></HEAD><BODY BGCOLOR="#FFFFFF"><a href="chap11.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="chap10.htm"><img align=right src="../../images/prev.gif" alt="Previous Chapter" border=0></A><h1><a name="07a2_0001"><a name="07a2_0002">PART III: Data Structures<a name="07a2_0002"></h1><P><h1>Introduction</h1><P><a name="07a4_13b7">Sets are as fundamental to computer science as they are to mathematics. Whereas mathematical sets are unchanging, the sets manipulated by algorithms can grow, shrink, or otherwise change over time. We call such sets <I><B>dynamic</I></B>. The next five chapters present some basic techniques for representing finite dynamic sets and manipulating them on a computer.<P><a name="07a4_13b8"><a name="07a4_13b9"><a name="07a4_13ba"><a name="07a4_13bb"><a name="07a4_13bc">Algorithms may require several different types of operations to be performed on sets. For example, many algorithms need only the ability to insert elements into, delete elements from, and test membership in a set. A dynamic set that supports these operations is called a <I><B>dictionary.</I></B> Other algorithms require more complicated operations. For example, priority queues, which were introduced in Chapter 7 in the context of the heap data structure, support the operations of inserting an element into and extracting the smallest element from a set. Not surprisingly, the best way to implement a dynamic set depends upon the operations that must be supported.<P><h2>Elements of a dynamic set</h2><P><a name="07a5_13bd"><a name="07a5_13be">In a typical implementation of a dynamic set, each element is represented by an object whose fields can be examined and manipulated if we have a pointer to the object. (Chapter 11 discusses the implementation of objects and pointers in programming environments that do not contain them as basic data types.) Some kinds of dynamic sets assume that one of the object's fields is an identifying <I><B>key </I></B>field. If the keys are all different, we can think of the dynamic set as being a set of key values. The object may contain <I><B>satellite data </I></B>, which are carried around in other object fields but are otherwise unused by the set implementation. It may also have fields that are manipulated by the set operations; these fields may contain data or pointers to other objects in the set.<P>Some dynamic sets presuppose that the keys are drawn from a totally ordered set, such as the real numbers, or the set of all words under the usual alphabetic ordering. (A totally ordered set satisfies the trichotomy property, defined on page 31.) A total ordering allows us to define the minimum element of the set, for example, or speak of the next element larger than a given element in a set.<P><P><h2>Operations on dynamic sets</h2><P><a name="07a6_13bf"><a name="07a6_13c0"><a name="07a6_13c1">Operations on a dynamic set can be grouped into two categories: <I><B>queries</I></B>, which simply return information about the set, and <I><B>modifying operations</I></B> , which change the set. Here is a list of typical operations. Any specific application will usually require only a few of these to be implemented.<P><a name="07a6_13c2"><FONT FACE="Courier New" SIZE=2>SEARCH</FONT>(<I>S, k</I>) A query that, given a set <I>S</I> and a key value <I>k</I>, returns a pointer <I>x</I> to an element in <I>S</I> such that <I>key</I>[<I>x</I>] = <I>k</I>, or <FONT FACE="Courier New" SIZE=2>NIL</FONT> if no such element belongs to <I>S</I>.<P><a name="07a6_13c3"><FONT FACE="Courier New" SIZE=2>INSERT</FONT>(<I>S, x</I>) A modifying operation that augments the set <I>S</I> with the element pointed to by <I>x</I>. We usually assume that any fields in element <I>x</I> needed by the set implementation have already been initialized.<P><a name="07a6_13c4"><FONT FACE="Courier New" SIZE=2>DELETE</FONT>(<I>S, x</I>) A modifying operation that, given a pointer <I>x</I> to an element in the set <I>S</I>, removes <I>x</I> from <I>S</I>. (Note that this operation uses a pointer to an element <I>x</I>, not a key value.)<P><FONT FACE="Courier New" SIZE=2>MINIMUM</FONT>(<I>S</I>) A query on a totally ordered set <I>S</I> that returns the element of <I>S</I> with the smallest key.<P><a name="07a6_13c5"><FONT FACE="Courier New" SIZE=2>MAXIMUM</FONT>(<I>S</I>) A query on a totally ordered set <I>S</I> that returns the element of <I>S</I> with the largest key.<P><a name="07a6_13c6"><FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT>(<I>S, x</I>) A query that, given an element <I>x</I> whose key is from a totally ordered set <I>S</I>, returns the next larger element in <I>S</I>, or <FONT FACE="Courier New" SIZE=2>NIL</FONT> if <I>x</I> is the maximum element.<P><a name="07a6_13c7"><FONT FACE="Courier New" SIZE=2>PREDECESSOR</FONT>(<I>S, x</I>) A query that, given an element <I>x</I> whose key is from a totally ordered set <I>S</I>, returns the next smaller element in <I>S</I>, or <FONT FACE="Courier New" SIZE=2>NIL</FONT> if <I>x</I> is the minimum element.<P><a name="07a6_13c8">The queries <FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT> and <FONT FACE="Courier New" SIZE=2>PREDECESSOR</FONT> are often extended to sets with nondistinct keys. For a set on <I>n</I> keys, the normal presumption is that a call to <FONT FACE="Courier New" SIZE=2>MINIMUM</FONT> followed by <I>n</I> - 1 calls to <FONT FACE="Courier New" SIZE=2>SUCCESSOR</FONT> enumerates the elements in the set in sorted order.<P>The time taken to execute a set operation is usually measured in terms of the size of the set given as one of its arguments. For example, Chapter 14 describes a data structure that can support any of the operations listed above on a set of size <I>n</I> in time <I>O</I>(1g <I>n</I>).<P><P><h2>Overview of Part III</h2><P>Chapters 11--15 describe several data structures that can be used to implement dynamic sets; many of these will be used later to construct efficient algorithms for a variety of problems. Another important data structure--the heap--has already been introduced in Chapter 7.<P>Chapter 11 presents the essentials of working with simple data structures such as stacks, queues, linked lists, and rooted trees. It also shows how objects and pointers can be implemented in programming environments that do not support them as primitives. Much of this material should be familiar to anyone who has taken an introductory programming course.<P>Chapter 12 introduces hash tables, which support the dictionary operations <FONT FACE="Courier New" SIZE=2>INSERT</FONT>, <FONT FACE="Courier New" SIZE=2>DELETE</FONT>, and <FONT FACE="Courier New" SIZE=2>SEARCH</FONT>. In the worst case, hashing requires <img src="../images/bound.gif">(<I>n</I>) time to perform a <FONT FACE="Courier New" SIZE=2>SEARCH</FONT> operation, but the expected time for hash-table operations is <I>O</I>(1). The analysis of hashing relies on probability, but most of the chapter requires no background in the subject.<P>Binary search trees, which are covered in Chapter 13, support all the dynamic-set operations listed above. In the worst case, each operation takes <img src="../images/bound.gif">(<I>n</I>) time on a tree with <I>n</I> elements, but on a randomly built binary search tree, the expected time for each operation is <I>O</I>(1g <I>n</I>). Binary search trees serve as the basis for many other data structures.<P>Red-black trees, a variant of binary search trees, are introduced in Chapter 14. Unlike ordinary binary search trees, red-black trees are guaranteed to perform well: operations take <I>O</I>(1g <I>n</I>) time in the worst case. A red-black tree is a balanced search tree; Chapter 19 presents another kind of balanced search tree, called a B-tree. Although the mechanics of red-black trees are somewhat intricate, you can glean most of their properties from the chapter without studying the mechanics in detail. Nevertheless, walking through the code can be quite instructive.<P>In Chapter 15, we show how to augment red-black trees to support operations other than the basic ones listed above. First, we augment them so that we can dynamically maintain order statistics for a set of keys. Then, we augment them in a different way to maintain intervals of real numbers.<P><P><P><P><P><center>Go to <a href="chap11.htm">Chapter 11</A> Back to <a href="toc.htm">Table of Contents</A></P></center></BODY></HTML>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -