Binary search tree
General Information
Abstract data structure: Sorted sequence
Implementation invariant:
- There is a tree item type with three components:
- key is of generic type [math]\mathcal{K}[/math],
- left and right of type "pointer to tree item of type [math]\mathcal{K}[/math]."
- An object of the binary search tree type contains a pointer root of type "pointer to tree item of type [math]\mathcal{K}[/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.
- For each node [math]x[/math] in the tree, no key in the left subtree of that node is greater than the key of [math]x[/math], and no key in the right subtree of [math]x[/math] is less than the key of [math]x[/math].
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 [math]p[/math] 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: [math] p[/math].left [math]\neq[/math]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 [math]O(\log{n})[/math] 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.