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
Red-Black Trees

Glossary


red-black tree  a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK.
(See page 271)
balanced  By constraining the way nodes can be colored on any path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.
(See page 271)
red-black properties  A binary search tree is a red-black tree if it satisfies the following red-black properties:

1. Every node is either red or black.

2. The root is black.

3. Every leaf (NIL) is black.

4. If a node is red, then both its children are black.

5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.


(See page 271)
black-height  We call the number of black nodes on any path from, but not including, a node x down to a leaf the black-height of the node, denoted bh(x).
(See page 274)
rotation  We change the pointer structure through rotation, a local operation in a search tree that preserves the binary-search-tree property.
(See page 277)
right-converted  We say that a binary search tree T1 can be right-converted to binary search tree T2 if it is possible to obtain T2 from T1 via a series of calls to RIGHT-ROTATE.
(See page 279)
persistent  past versions of a dynamic set maintained as it is updated.
(See page 294)
AVL tree  An AVL tree is a binary tree that is height balanced
(See page 296)
height balanced  for each node x, the heights of the left and right subtrees of x differ by at most 1
(See page 296)
treap  a binary search tree with a modified way of ordering the nodes
(See page 297)
left spine  on a binary search tree T it is the path from the root to the node with the smallest key. In other words, the left spine is the path from the root that consists of only left edges.
(See page 298)
right spine  Symmetrically, the right spine of T is the path from the root consisting of only right edges.
(See page 298)
length  The length of a spine is the number of nodes it contains.
(See page 298)








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.