A tree is a connected, acyclic graph. Its two fundamental operations are insertion (place a new node in its correct position) and search (find a node by key). Both operations traverse from the root toward a leaf, making a comparison at each node to determine which child to follow.
The performance of these operations depends on tree height. A balanced tree with N nodes has height O(log N). An unbalanced tree (a pathological case where each node has only one child) has height O(N) — equivalent to a linked list.
Three factors vary across tree variants: - Branching factor — how many children a node can have (binary = 2, B-tree = hundreds) - Balance guarantee — whether the tree maintains equal height across branches (BST: none by default; AVL, Red-Black, B-tree: guaranteed) - Node size — how much data fits in a node (BST: one key; B-tree: hundreds of keys, sized to match a disk page)
Each production tree variant chooses these factors based on the constraints of where it lives.