Binary search tree: Difference between revisions

Revision as of 22:36, 19 September 2014

There is a tree item type with three components:
1. key is of generic type [math]\displaystyle{ \kappa }[/math]
2. left and right of type "pointer to tree item of type [math]\displaystyle{ \kappa }[/math]"
An object of the binary search tree type contains a pointer root of type "pointer to tree item of type [math]\displaystyle{ \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.

Binary Search Tree

whatever

@@ Line 1: / Line 1: @@
 [[Category:Data Structures]]
 [[Category:Trees]]
+== 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.
 <div class="plainlinks" style="float:right;margin:0 0 5px 5px; border:1px solid #AAAAAA; width:auto; padding:1em; margin: 0px 0px 1em 1em;">
 <div style="font-size: 1.8em;font-weight:bold;text-align: center;margin:0.2em 0 1em 0">Binary Search Tree</div>