Binary search tree: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 3: | Line 3: | ||
== General Information == | == General Information == | ||
<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> | |||
<div style="font-size: 1.2em; margin:.5em 0 1em 0; text-align:center">whatever</div> | |||
<div style="font-size: 1.2em; margin:.5em 0 .5em 0;text-align:center">[[File:olw_logo1.png|20px]][https://openlearnware.tu-darmstadt.de/#!/resource/binary-search-tree-1938 Openlearnware]</div> | |||
</div> | |||
===Abstract Data Structure:=== | ===Abstract Data Structure:=== | ||
[[Sorted Sequence]] | [[Sorted Sequence]] | ||
| Line 13: | Line 21: | ||
# An object of the binary search tree type contains a pointer '''''root''''' 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. | # 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. | ||
Revision as of 22:38, 19 September 2014
General Information
Abstract Data Structure:
Implementation Invariant:
- There is a tree item type with three components:
- key is of generic type [math]\displaystyle{ \kappa }[/math]
- 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.