McGraw-Hill OnlineMcGraw-Hill Higher EducationLearning Center
Student Center | Instructor's Center | Introduction to Algorithms | Home
Glossary A-B
Glossary B-D
Glossary D-F
Glossary F-J
Glossary J-M
Glossary M-O
Glossary O-P
Glossary P-S
Glossary S-T
Glossary T-Z
Chapter Objectives
Chapter Overview
Glossary
PowerPoint Slides
Algorithm Pseudocode
Feedback
Help Center


small text cover image
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
Augmenting Data Structures

Glossary


rank  an element's position in the linear order of the set
(See page 302)
order-statistic tree  a red-black tree with additional information stored in each node. Besides the usual red-black tree fields key[x], color[x], p[x], left[x], and right[x] in a node x, we have another field size[x]. This field contains the number of (internal) nodes in the subtree rooted at x (including x itself), that is, the size of the subtree.
(See page 303)
closed interval  an ordered pair of real numbers [t1, t2], with t1 ≤ t2.
(See page 311)
open interval  omits both endpoints from the set.
(See page 311)
half-open interval  omits one of the endpoints from the set
(See page 311)
low endpoint  if interval [t1, t2] is an object i, then field low[i] = t1 is the low endpoint.
(See page 311)
high endpoint  if interval [t1, t2] is an object i, then field high[i] = t2 is the high endpoint.
(See page 311)
overlap  Intervals i and i'  overlap if i ∩ i' ≠ Ø, that is, if low[i] ≤ high[i'] and
low[i'] ≤ high[i].
(See page 311)
interval trichotomy  Any two intervals i and i' satisfy the interval trichotomy; that is, exactly one of the following three properties holds:

a. i and i' overlap,

b. i is to the left of i' (i.e., high[i] < low[i']),

c. i is to the right of i' (i.e., high[i'] < low[i]).


(See page 311)
interval tree  a red-black tree that maintains a dynamic set of elements, with each element x containing an interval int[x].
(See page 312)
point of maximum overlap  a point that has the largest number of intervals in the database overlapping it.
(See page 318)
Josephus problem  Suppose that n people are arranged in a circle and that we are given a positive integer m ≤ n. Beginning with a designated first person, we proceed around the circle, removing every mth person. After each person is removed, counting continues around the circle that remains. This process continues until all n people have been removed.
(See page 318)








Copyright2002 McGraw-Hill Higher Education
Any use is subject to the Terms of Use and Privacy Policy.
McGraw-Hill Higher Education is one of the many fine businesses of The McGraw-Hill Companies.