 |  Introduction to Algorithms, 2/e Thomas H. Cormen,
Dartmouth College
Charles E. Leiserson,
Massachusetts Institute of Technology
Ronald L. Rivest,
Massachusetts Institute of Technology
Clifford Stein,
Columbia University
Data Structures for Disjoint Sets
Glossary
| representative | some member of the set. In some applications, it doesn't matter which member is used as the representative; we only care that if we ask for the representative of the dynamic set twice without modifying the set between the requests, we get the same answer both times. In other applications, there may be a prespecified rule for choosing the representative, such as choosing the smallest member in the set (assuming, of course, that the elements can be ordered).
(See page 498)
| | | | | weighted-union heuristic | each list includes the length of the list and we always append the smaller list onto the longer, with ties broken arbitrarily.
(See page 503)
| | | | | disjoint-set forest | each member points only to its parent. The root of each tree contains the representative and is its own parent.
(See page 505)
| | | | | find path | For the disjoint-set forest, three disjoint-set operations are performed as follows: A MAKE-SET operation simply creates a tree with just one node. A FIND-SET operation is performed by following parent pointers until the root of the tree is found. The nodes visited on this path toward the root constitute the find path.
(See page 506)
| | | | | union by rank | A heuristic to improve the running time. Similar to the weighted-union heuristic used with the linked-list representation. The idea is to make the root of the tree with fewer nodes point to the root of the tree with more nodes. Rather than explicitly keeping track of the size of the subtree rooted at each node, an approach that eases the analysis is used. In each node, a rank is maintained that is an upper bound on the height of the node. In union by rank, the root with smaller rank is made to point to the root with larger rank during a UNION operation.
(See page 506)
| | | | | path compression | simple and very effective heuristic. Used during FIND-SET operations to make each node on the find path point directly to the root. Path compression does not change any ranks.
(See page 506)
| | | | | rank | the upper bound on the height of a node.
(See page 506)
| | | | | two-pass method | used by the FIND-SET procedure, it makes one pass up the find path to find the root, and it makes a second pass back down the find path to update each node so that it points directly to the root.
(See page 508)
| | | | | off-line minimum problem | to maintain a dynamic set T of elements from the domain {1, 2, . . . , n} under the operations INSERT and EXTRACT-MIN. Given a sequence S of n INSERT and m EXTRACT-MIN calls, where each key in {1, 2, . . . , n} is inserted exactly once, determine which key is returned by each EXTRACT-MIN call. Specifically, fill in an array extracted[1..m], where for
i = 1, 2, . . . , m, extracted[i] is the key returned by the ith EXTRACT-MIN call. The problem is "off-line" in the sense that it processes the entire sequence S before determining any of the returned keys.
(See page 518)
| | | | | least common ancestor | of two nodes u and v in a rooted tree T is the node w that is an ancestor of both u and v and that has the greatest depth in T.
(See page 521)
| | | | | off-line least-common-ancestors problem | Given a rooted tree T and an arbitrary set P = {{u, v}} of unordered pairs of nodes in T, determine the least common ancestor of each pair in P.
(See page 521)
|
|
2002 McGraw-Hill Higher Education