|
|
| Line 1: |
Line 1: |
| == General Information ==
| |
| ===Abstract Data Structure:===
| |
| [[Sorted Sequence]]
| |
|
| |
|
| ===Implementation Invariant:===
| |
|
| |
| # There is a tree item type with three components:
| |
| ## '''''key''''' is of generic type <math>\kappa</math>
| |
| ## '''''left''''' and '''''right''''' of type "pointer to tree item of type <math>\kappa</math>"
| |
| # An object of the binary search tree type contains a pointer '''''root''''' of type "pointer to tree item of type <math>\kappa</math>"
| |
| # 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.
| |