Next: Optimal Binary Trees
Up: Binary Trees
Previous: Binary Search Trees
If a given sequence of nodes is used to build a binary tree, the tree is
called alphabetic iff the leaf nodes of the tree obey the order of the
initial sequence from left to right.
An alphabetic key constraint does not imply a binary search mechanism.
Thus the internal nodes of the alphabetic tree do not have to
provide information for locating the leaf nodes of the tree.
An alphabetic binary search tree on the other hand implies that the initial sequence of
nodes will appear with preserved alphabetic order as leaf nodes of tree but the
internal nodes of the tree will also contain the required information so that
a binary search procedure can be used to locate an arbitrary node from the
initial sequence in the crown of the tree.