decision tree
A tree in which each internal node is a question or choice and each path from the root to a leaf is one complete outcome.
In more detail
In sorting, each node is a comparison and each leaf one possible ordering, and the tree's depth is the worst-case number of comparisons. In backtracking, each node is a partial solution and each branch one choice, and pruning cuts off whole subtrees. The same picture explains both a lower bound and a search strategy.
Related terms
- comparison sort lower bound — The proven fact that any sort that only compares pairs must make at least about n log n comparisons in the worst case.
- backtracking — A search technique that builds a solution one choice at a time and undoes the latest choice as soon as it cannot lead to a valid solution.
- search space — The set of all candidate solutions an algorithm might consider, often pictured as a tree of choices.
Taught in
- Comparison Sorts: Insertion, Merge And Quicksort — Algorithms & Data Structures for Working Engineers
- Backtracking: Search With Pruning — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers