When Trees Instead of Lists

Lists are linear; trees branch out. Hierarchies, area-specific searches, and logarithmic height favor trees. Sequential scans and end operations favor lists or deques.

Be able to briefly explain structure diagrams, traversal order, and height arguments.

Where used

Logarithmic search and sorted iteration outperform linear lists as n grows and ordering or range queries become significant. Flat lists remain appropriate for small n and pure append workloads.

Depth

Lists model a linear order and excel at sequential traversal as well as local modifications. Trees model hierarchies or create shorter search paths through ordering. The structure should follow from the dominant operations.

An unordered tree does not automatically improve key searches. Only additional invariants such as search order and balance provide reliable logarithmic path lengths. This makes insertion and deletion more complex.

Hierarchical data like file systems or syntax trees already have a natural parent-child structure. Linear storage is possible, but it would need to reconstruct relationships through additional indices.

Difficulty levels

1. Distinguish between linear and hierarchical relationships.
2. Evaluate operation profiles for structure selection.
3. Explain the costs of additional ordering and balancing invariants.

Pitfalls

The mere use of nodes does not make search fast. In cases of frequent complete traversal, a compact linear structure may be more efficient despite poorer asymptotic search performance.