Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
| mergeable min-heap | a mergeable heap which supports MINIMUM and EXTRACT-MIN. This is the default mergeable heap.
(See page 431)
|
 |
|
|
| mergeable max-heap | a mergeable heap which supports MAXIMUM and EXTRACT-MAX.
(See page 431)
|
|
|
|
| dynamic trees | maintain a forest of disjoint rooted trees. Each edge in each tree has a real-valued cost. Support queries to find parents, roots, edge costs, and the minimum edge cost on a path from a node up to a root. May be manipulated by cutting edges, updating all edge costs on a path from a node up to a root, linking a root into another tree, and making a node the root of the tree it appears in. Used in some of the asymptotically fastest network-flow algorithms.
(See page 432)
|
|
|
|
| splay trees | a form of binary search tree on which the standard search-tree operations run in O(lg n) amortized time. One application simplifies dynamic trees.
(See page 432)
|
|
|
|
| persistent data structures | allow queries, and sometimes updates as well, on past versions of a data structure.
(See page 432)
|
|
|
|
| fusion trees | allow faster dictionary operations when the universe is restricted to integers.
(See page 433)
|
|
|
|
| dynamic graph data structures | support various queries while allowing the structure of a graph to change through operations that insert or delete vertices or edges. Examples of the queries that are supported include vertex connectivity, edge connectivity, minimum spanning trees, biconnectivity, and transitive closure.
(See page 433)
|
|
|
|
| B-tree | a balanced search tree designed to work well on magnetic disks or other direct-access secondary storage devices. Similar to red-black trees, but they are better at minimizing disk I/O operations. Similar to red-black trees in that every n-node B-tree has height O(lg n), although the height of a B-tree can be considerably less than that of a red-black tree because its branching factor can be much larger. Differ from red-black trees in that B-tree nodes may have many children, from a handful to thousands. A B-tree T is a rooted tree (whose root is root[T]) having properties. See page 438-439 for a listing of properties.
(See page 434)
|
|
|
|
| primary or main memory | in a computer system normally consists of silicon memory chips.
(See page 434)
|
|
|
|
| secondary storage | computer memory based on magnetic disks. The amount of such secondary storage often exceeds the amount of primary memory by at least two orders of magnitude.
(See page 435)
|
|
|
|
| page | on a computer storage device consists of bits that appear consecutively within cylinders. Each disk read or write is of one or more entire pages.
(See page 435)
|
|
|
|
| B+-tree | A common variant on a B-tree. Stores all the satellite information in the leaves and stores only keys and child pointers in the internal nodes, thus maximizing the branching factor of the internal nodes.
(See page 438)
|
|
|
|
| minimum degree of a B-tree | determined by the lower and upper bounds on the number of keys a node can contain, expressed in terms of a fixed integer t ≥ 2.
(See page 439)
|
|
|
|
| full node | a node is full if it contains exactly 2t - 1 keys, where t is the minimum degree of the B-tree.
(See page 439)
|
|
|
|
| 2-3-4 tree | The simplest B-tree. Occurs when t = 2. Every internal node then has either 2, 3, or 4 children.
(See page 439)
|
|
|
|
| B*-tree | Another common variant on a B-tree. Requires each internal node to be at least 2/3 full, rather than at least half full, as a B-tree requires.
(See page 439)
|
|
|
|
| joining 2-3-4 trees | The join operation takes two dynamic sets S' and S'' and an element x such that for any x' ∈ S' and x'' ∈ S'', we have key[x'] < key[x] < key[x'']. It returns a set S = S' ∪ {x} ∪ S''.
(See page 453)
|
|
|
|
| splitting 2-3-4 trees | The split operation is like an "inverse" join; given a dynamic set S and an element x ∈ S, it creates a set S' consisting of all elements in S - {x} whose keys are less than key[x] and a set S'' consisting of all elements in S - {x} whose keys are greater than key[x].
(See page 453)
|
2002 McGraw-Hill Higher Education