Category:Binary Search Tree

General Information

Abstract Data Structure: Sorted Sequence

Implementation Invariant:

1. There is a tree item type with three components:
   1. Key is of generic type K
   2. left and right of type "pointer to tree item of type K"
2. An object of the binary search tree type contains a pointer root of type "pointer to tree item of type K"
3. The pointer root points to a well-formed binary search tree. In accordance with the definition of directed trees, "well-formed" means that, for any node, there is exactly one path from the root to that node.