Binary search trees - Data Structures and Problem Solving Using Java - page 763

key concepts
AA-tree A balanced search tree that is the tree of choice when an O (log N )
worst case is needed, a casual implementation is acceptable, and deletions
are needed. (728)
AVL tree A binary search tree with the additional balance property that, for
any node in the tree, the height of the left and right subtrees can differ by
at most 1. As the first balanced search tree, it has historical significance. It
also illustrates most of the ideas that are used in other search tree
schemes. (706)
balanced binary search tree A tree that has an added structure property to
guarantee logarithmic depth in the worst case. Updates are slower than
with the binary search tree, but accesses are faster. (706)
binary search tree A data structure that supports insertion, searching, and dele-
tion in O (log N ) average time. For any node in the binary search tree, all
smaller keyed nodes are in the left subtree and all larger keyed nodes are
in the right subtree. Duplicates are not allowed. (688)
B-tree The most popular data structure for disk-bound searching. There are
many variations of the same idea. (757)
double rotation Equivalent to two single rotations. (712)
external path length The sum of the cost of accessing all external tree nodes in
a binary tree, which measures the cost of an unsuccessful search. (704)
external tree node The null node. (705)
horizontal link In an AA-tree, a connection between a node and a child of
equal levels. A horizontal link should go only to the right, and there
should not be two consecutive horizontal links. (729)
internal path length The sum of the depths of the nodes in a binary tree, which
measures the cost of a successful search. (704)
lazy deletion A method that marks items as deleted but does not actually
delete them. (728)
level of a node In an AA-tree, the number of left links on the path to the
nullNode sentinel. (729)
M -ary tree A tree that allows M -way branching, and as branching increases,
the depth decreases. (757)
red-black tree A balanced search tree that is a good alternative to the AVL tree
because a single top-down pass can be used during the insertion and dele-
tion routines. Nodes are colored red and black in a restricted way that
guarantees logarithmic depth. The coding details tend to give a faster
implementation. (715)