Binary search tree

A binary tree whose left and right subtrees contain smaller and larger keys, respectively. This ordering supports search, insertion, deletion, and sorted traversal.

Tree traversal: A systematic method for visiting every node in a tree. In-order traversal visits keys in ascending order when the tree obeys its ordering rule.
AVL tree: A self-balancing binary search tree that keeps the heights of child subtrees within one of each other. It prevents the long chains that can make an ordinary search tree slow.
Ordered map: A key-value collection that maintains keys in sorted order and supports ordered operations. A search tree can implement an ordered map with dynamic updates.
Binary search: A search algorithm that repeatedly halves a sorted range by comparing its middle element with a target. Both methods use ordering to discard candidates, but a tree stores the decisions in its shape.
Binary tree: A tree data structure in which each node has at most two children. The search tree adds an ordering rule to this broader structure.
Red-black tree: A self-balancing binary search tree that uses node colors and invariants to bound its height. It trades stricter balance for updates that require relatively few rotations.
Range query: A query that retrieves records whose values fall within a specified interval. Subtree ordering lets a search tree skip keys outside the requested interval.
Recursion: A method of defining or solving a problem through smaller instances of the same problem. Search and updates naturally continue on one child subtree at a time.
Binary search tree insertion: The operation that adds a key to a binary search tree while preserving its ordering invariant. Insertion follows comparisons from the root to find an available position.
Treap: A randomized search tree that combines binary-search ordering by key with heap ordering by priority. Random priorities provide expected balance without explicit height constraints.

Linked from 8 pages