Binary Search Tree
Subject: Computer and Technology noun /ˈbaɪ.nər.i ˈsɜːrtʃ triː/ 1 definition
- data-structures
- tree-algorithms
- search-algorithms
- computer-science
-
Definition (noun)
Entry #41 · UpdatedA Binary Search Tree (BST) is a rooted binary tree data structure that stores comparable keys in sorted order by enforcing an ordering invariant at every node: all keys in the left subtree are smaller than the node's key, and all keys in the right subtree are larger. This structure supports search, insertion, deletion, minimum and maximum lookups, and range queries in O(log n) average time while enabling sorted output via in-order traversal. Unlike a hash table, a BST preserves key ordering, though an unbalanced tree can degrade into a linear chain with O(n) worst-case performance under skewed insertions.
Common Types
Unbalanced Binary Search Tree: Inserts and removes nodes solely through key comparisons without restructuring, offering a minimal implementation with O(log n) average performance on random inputs that degrades to O(n) height on sorted data.
AVL Tree: Maintains strict height balance by tracking each node's balance factor and applying single or double rotations whenever a node's left and right subtrees differ in height by more than one, guaranteeing O(log n) worst-case lookups.
Red-Black Tree: Assigns a red or black color bit to each node and enforces structural invariants through recoloring and rotations, bounding tree height to O(log n) with fewer rebalancing rotations during insertions and deletions than AVL trees.
Splay Tree: Moves any accessed, inserted, or deleted node to the root via splaying rotations without storing balance metadata, achieving O(log n) amortized complexity and fast repeated access for skewed workloads.
Example
An observability service indexes 1,000,000 metric entries in a balanced binary search tree keyed by millisecond Unix timestamp so records stay sorted as events stream in. When a dashboard queries metrics between
1700000100000and1700000160000, the engine locates the lower bound in roughly 20 comparisons from the root and collects matching entries via an in-order traversal without scanning the entire dataset.