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

Taught in

References