 |  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
Binary Search Trees
Glossary
| binary-search-tree property | Let x be a node in a binary search tree. If y is a node in the left subtree of x, then key[y] ≤ key[x]. If y is a node in the right subtree of x, then key[x] ≤ key[y].
(See page 254)
| | | | | inorder tree walk | an algorithm so named because the key of the root of a subtree is printed between the values in its left subtree and those in its right subtree.
(See page 254)
| | | | | preorder tree walk | an algorithm so named because the key of the root of a subtree is printed before the values in either subtree.
(See page 254)
| | | | | postorder tree walk | an algorithm so named because the key of the root of a subtree is printed after the values in its subtrees.
(See page 254)
| | | | | randomly built binary search tree | defined on n keys as one that arises from inserting the keys in random order into an initially empty tree, where each of the n! permutations of the input keys is equally likely.
(See page 265)
| | | | | exponential height | We denote the height of a randomly built binary search on n keys by Xn, and we define the exponential height Yn = 2Xn.
(See page 265)
| | | | | lexicographically less than | Given two strings a = a0a1 . . . ap and b = b0b1 . . . bq, where each ai and each bj is in some ordered set of characters, we say that string a is lexicographically less than string b if either 1. there exists an integer j, where 0 ≤ j ≤ min(p, q), such that ai = bi for all i = 0, 1, . . . , j - 1 and aj < bj, or 2. p < q and ai = bi for all i = 0, 1, . . . , p.
(See page 269)
| | | | | total path length | We define the total path length P(T) of a binary tree T as the sum, over all nodes x in T, of the depth of node x, which we denote by
d(x, T).
(See page 270)
|
|
2002 McGraw-Hill Higher Education