C++UCS301
Trees & ApplicationsC++17

Tree Applications

Trees power file systems, syntax trees, indexes, autocomplete, routing, compression, and hierarchical user interfaces.

What to understand

  • Expression trees
  • Tries
  • Decision trees
  • Database indexes

Remember this

  1. 1Choose the invariant for the query
  2. 2Balance is valuable when updates are dynamic
  3. 3Hierarchy and ordered search are different needs

Detailed notes

Different tree invariants optimise different questions. Tries index prefixes by characters, expression trees encode operator structure, decision trees encode choices, and interval or segment trees aggregate ranges.

The word tree describes shape, not performance. The useful guarantee comes from an additional rule—ordering, balance, prefix edges, heap order, spatial containment, or stored aggregates.

How it works

  1. 1Translate the domain relationship into nodes and edges.
  2. 2Identify the query that must be fast.
  3. 3Select and maintain an invariant supporting that query.
  4. 4Choose traversal order from the output or update requirement.

Where it is used

  • Autocomplete and spell checking
  • Compilers and calculators
  • Hierarchical permissions and user interfaces

Common mistakes

  • Using a BST for prefix queries better served by a trie
  • Assuming every hierarchy needs key ordering
  • Ignoring update cost of stored aggregates

Implementation perspective

This is primarily a conceptual or selection topic. Use the linked implementation topics in this section to see the invariant expressed in C++.

Exam & viva

Open a prompt when you are ready to check your answer.