binary search tree
A binary tree in which every key in a node's left subtree is smaller than the node's key and every key in its right subtree is larger.
In more detail
Searching compares with the node and moves left or right, discarding one side each step, so search, insert and delete cost O(h). With random insertion order the height is about O(log n), but sorted insertion makes the tree a chain of height n. Self-balancing variants such as AVL trees keep the height logarithmic whatever the order.
Related terms
- BST property — The rule that keeps a binary search tree searchable: left subtree keys are smaller than the node, right subtree keys are larger.
- in-order successor — The node with the next larger key in a binary search tree, which is the smallest key in the node's right subtree.
- degenerate tree — A search tree in which every node has only one child, so it is really a linked list with height n minus one.
- AVL tree — A self-balancing binary search tree in which the heights of every node's two subtrees differ by at most one.
- balanced tree — A tree kept close to its minimum possible height, O(log n), so that searches never take long paths.
Taught in
- Binary Trees And Their Traversals — Algorithms & Data Structures for Working Engineers
- Binary Search Trees: Search, Insert And Delete — Algorithms & Data Structures for Working Engineers
- AVL Trees: Rotations That Keep The Guarantee — Algorithms & Data Structures for Working Engineers
- B-Trees: The Structure Behind Every Database Index — Algorithms & Data Structures for Working Engineers