Binary search tree: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 22: Line 22:
## '''''left''''' and '''''right''''' of type "pointer to tree item of 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>"
# 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 tree|directed trees]], "well-formed" means that, for any node, there is exactly one [[path]] from the root to that node.


== Remark ==
== Remark ==

Revision as of 11:42, 26 September 2014


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

Remark

  • Besides the methos of sorted sequences, binary search trees have a private method Binary Search Tree:Remove node, which receives a pointer p to a binary search tree node and removes id (possibly by removeing another node and overwriting the key to be removed with the key of the other node. Prerequisite: [math]\displaystyle{ p.left \neq void }[/math]
  • There are variants on binary search trees, such as AVL trees and red-black-trees, for which the height of the tree is guaranteed to be in [math]\displaystyle{ O \log{n} }[/math] in these variants (because the additional operations in these methods are necessary to maintain logatihmic height are linear in the height of the tree as well=.
  • For further information, see section "Binary search tree" of page Directed tree.