Binary search tree
(Redirected from Binary Search Tree)
Jump to navigation
Jump to search
General Information
Abstract data structure: Sorted sequence
Implementation invariant:
- There is a tree item type with three components:
- key is of generic type
, - left and right of type "pointer to tree item of type
."
- key is of generic type
- An object of the binary search tree type contains a pointer root of type "pointer to tree item of type
." - 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.
- For each node
in the tree, no key in the left subtree of that node is greater than the key of , and no key in the right subtree of is less than the key of .
Remark
- Besides the methods of sorted sequences, binary search trees in the implementation chosen here have a private method Binary Search Tree:Remove node, which receives a pointer
to a binary search tree node and removes it (possibly by removing another node and overwriting the key to be removed with the key of the other node. Prerequisite: .left void. - 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
at any time (because the additional operations to maintain logarithmic height are linear in the height of the tree as well). - The mathematical concept behind this data structure is described in the section on binary search trees of page Directed Tree.