16: Trees and searches
- Page ID
- 83482
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
- 16.1: Motivation
- Reducing redundancy. You have set up your own tree-fort communication system out of tin cans and strings.
- 16.2: Basics
- Trivial Path: a path that consists of a single vertex
- 16.3: Identifying Trees
- Theorem: Characterizations of trees. The following are equivalent for a graph G=(V,E) with |V|=n vertices.
- 16.4: Depth-first and breadth-first searches
- Let G be a graph. Given vertices v,v′ of G, we might wish to find a path from v to v′, if one exists. We can do this by constructing a tree T⪯G.
- 16.5: Spanning Trees
- Spanning Subgraph: a subgraph that contains all the vertices of the parent graph
- 16.6: Binary Searches
- Binary Search Tree: a tree in which every node has degree 1 or 3, except for a single node of degree 2.