Lesson 3

Trees are one of the simplest and at the same time most important classes of graphs. Here are just some of their applications:

• Data structures:  search tree, heap, segment tree, suffix tree, disjoint-set representation using trees.


• Algorithms:  breadth-first search, depth-first search, minimum spanning tree, backtracking, branch and bound, alpha-beta pruning.


• Parse tree:  for arithmetic expressions and grammars.


• Recursive call tree:  we have already encountered them above.


• Genealogical tree:  family tree.


• Decision tree:  used both in practice (machine learning, data analysis, statistics) and in theory (for example, in the well-known proof of the lower bound \(\Omega(n\log n)\) for comparison-based sorting).


• Game tree:  a tree containing all possible game scenarios.


• Prefix code tree:  a tree containing all codewords.