Trees and Hierarchical Storage

Hierarchical Structures

A tree stores data hierarchically with a single root node at the top. Every node has child nodes, each non-root node has one parent, and nodes with no children are leaves. Trees model naturally-nested data like file systems and org charts.

A binary tree restricts each node to at most two children. The binary search tree (BST) adds an invariant: for any node, all values in its left subtree are smaller, and its right subtree are greater. Searching means comparing and going left or right, discarding half the tree each step.

Balance and Operations

When a BST is balanced, its subtrees stay roughly equal in height, making search, insertion, and deletion $O(\log n)$ operations. Each operation walks a single path from root to leaf, where the tree's height is about $\log n$.

$$\text{balanced height} \approx \log_2 n$$

A balanced tree ensures logarithmic operations. Common pitfall: assuming a BST is always $O(\log n)$. Inserting already-sorted data degenerates the tree into a linked list of height $n$, making operations $O(n)$. Self-balancing trees (AVL, red-black) prevent this degradation.