graph theory unit 5 study guides

What Are Trees?

• Trees are connected acyclic graphs consisting of nodes (vertices) and edges
• Every pair of nodes in a tree is connected by exactly one path
• Trees have a hierarchical structure with a designated root node at the top
• Each node in a tree has a unique parent node, except for the root which has no parent
• Nodes with the same parent are called siblings
• Nodes without children are called leaves or external nodes, while nodes with children are internal nodes
• The depth of a node is the number of edges from the root to that node
• The height of a tree is the maximum depth among all nodes in the tree

Tree Properties and Terminology

• Trees are minimally connected graphs, meaning removing any edge disconnects the graph
• The number of nodes in a tree is always one more than the number of edges ($n = m + 1$, where $n$ is the number of nodes and $m$ is the number of edges)
• Trees have no cycles, so there is a unique path between any two nodes
• The degree of a node in a binary tree is at most 2, while in a general tree, there is no restriction on the degree
• Subtrees are smaller trees within a larger tree, formed by selecting a node as the root and including all its descendants
• A forest is a collection of disjoint trees
• The diameter of a tree is the number of edges in the longest path between any two nodes
• The level of a node is the number of edges on the path from the root to that node

Types of Trees

• Binary trees have at most two children for each node (left child and right child)
  • Full binary trees have either 0 or 2 children for every node
  • Complete binary trees have all levels filled, except possibly the last level, which is filled from left to right
  • Perfect binary trees have all levels completely filled
• N-ary trees allow nodes to have more than two children
• Balanced trees have heights that are logarithmic in the number of nodes (e.g., AVL trees, Red-Black trees)
• Trie (prefix tree) is a tree-like data structure used for efficient string searching and retrieval
• Huffman trees are used for data compression by assigning shorter codes to more frequent characters
• B-trees are self-balancing trees used in databases and file systems to minimize disk accesses

Tree Traversal Algorithms

• Preorder traversal visits the root, then recursively visits the left subtree, followed by the right subtree
• Inorder traversal recursively visits the left subtree, then the root, and finally the right subtree
  • Inorder traversal of a binary search tree yields nodes in ascending order
• Postorder traversal recursively visits the left subtree, then the right subtree, and finally the root
• Level-order traversal (Breadth-First Search) visits nodes level by level, from left to right
• Depth-First Search (DFS) explores as far as possible along each branch before backtracking
• Traversal algorithms can be implemented using recursion or iteration (with the help of a stack or queue)

Forests and Their Characteristics

• A forest is a disjoint union of trees, i.e., a graph whose connected components are trees
• Forests can be created by removing edges from a tree or combining multiple trees
• The number of trees in a forest is equal to the number of connected components in the graph
• Forests have no cycles, and there is a unique path between any two nodes within the same tree
• Many tree algorithms can be extended to work on forests by applying them to each tree independently
• Forests can be used to model hierarchical relationships or represent disjoint sets

Applications of Trees in Graph Theory

• Trees are used to model hierarchical relationships (e.g., family trees, organizational charts)
• Spanning trees are subgraphs that include all vertices of a graph and have no cycles
  • Minimum spanning trees (MSTs) have the smallest total edge weight among all spanning trees
• Trees can represent decision-making processes or game trees (e.g., chess, tic-tac-toe)
• Prefix trees (tries) are used for efficient string searching and retrieval in text processing
• Huffman coding uses trees to compress data by assigning shorter codes to more frequent symbols
• Trees are used in network routing protocols to avoid loops and efficiently propagate information

Problem-Solving with Trees

• Many graph problems can be solved efficiently using tree algorithms
• Checking if a graph is a tree can be done by verifying it is connected and has $n-1$ edges
• Finding the shortest path between two nodes in a tree is straightforward since there is only one path
• Lowest Common Ancestor (LCA) problem finds the deepest node that is an ancestor of two given nodes
• Diameter of a tree can be found by running two depth-first searches from an arbitrary node
• Tree isomorphism problem determines if two trees have the same structure, ignoring node labels
• Counting the number of distinct trees with $n$ nodes is given by the Catalan numbers: $C_n = \frac{1}{n+1}\binom{2n}{n}$

Advanced Tree Concepts

• Self-balancing trees (e.g., AVL trees, Red-Black trees) maintain logarithmic height through rotations
  • Rotations are local operations that rebalance the tree while preserving the binary search tree property
• Splay trees are self-adjusting binary search trees that move recently accessed nodes closer to the root
• Treaps combine the binary search tree property with heap-like priorities for efficient searching and updates
• Persistent trees allow efficient access to multiple versions of a tree, useful for undo/redo operations
• Suffix trees represent all suffixes of a string, enabling fast pattern matching and substring queries
• Tree decomposition and tree-width are used to solve graph problems by exploiting the tree-like structure of graphs
• Dynamic trees support efficient updates and queries on trees that change over time (e.g., link-cut trees)