26.1. Trees

A tree is a hierarchical data structure with a root node and sub-nodes (children), where each node (except the root) has exactly one parent. It is an abstract model of hierarchical structures.

Key Terms:

• Root: Topmost node.
• Leaf: Node with no children.
• Internal Node: Node with at least one child.
• Depth: Length of the path from root to the node.
• Height: Longest path from the node to a leaf.

A tree is a data structure that represents information in a hierarchy. It starts from a single top node, called the root, and branches out into child nodes. Each of these child nodes can have its own children, forming a tree-like structure. In a tree:

• The root is the starting point, like the trunk of a tree.
• Leaves are the nodes at the end of branches that do not lead to any other nodes, similar to the leaves at the tip of a branch.
• Internal nodes are those that continue to branch out and have at least one child.
• Depth refers to how far a node is from the root, akin to how many branch levels you must pass through to reach that node.
• Height indicates how tall the tree is, measured from a specific node to the furthest leaf beneath it.

Think of a family tree: the grandparent at the top is like the root. Their children are the next level down (internal nodes), and the grandchildren are the leaves. Just like how you find how many generations away someone is based on how far you must go from the root, trees in data structures help organize and retrieve data efficiently.

A binary tree is a tree in which each node has at most two children, typically called left and right.

Traversal Methods:

• In-order (LNR): Left → Node → Right
• Pre-order (NLR): Node → Left → Right
• Post-order (LRN): Left → Right → Node
• Level-order: Breadth-first traversal using a queue.

A binary tree is a specific type of tree where each node can have a maximum of two children, referred to as the left child and the right child. This structure allows for efficient data representation.

• Traversal methods are ways to visit each node in the tree:
  • In-order (LNR) goes to the left child, visits the node, and then goes to the right child, resulting in a sorted output for binary search trees.
  • Pre-order (NLR) visits the node first, then goes to the left child and the right child, useful for copying the tree.
  • Post-order (LRN) visits both children before the node, often used when deleting trees.
  • Level-order uses breadth-first search to visit nodes level by level, which is useful for certain applications like printing out a tree.

Imagine a binary tree like a decision-making process. Each question (node) can lead to two possible answers (children). You might ask everyone what type of pet they prefer (binary choice: dog or cat), and based on the answers (traversal methods), you can organize everyone’s preferences in different ways.

A Binary Search Tree maintains a sorted structure:

• Left subtree contains nodes with values less than the parent node.
• Right subtree contains nodes with values greater than the parent node.

Operations:

• Insert: O(log n) average
• Search: O(log n) average
• Delete: O(log n) average (Worst-case for unbalanced trees: O(n))

A Binary Search Tree (BST) is designed to maintain sorted data. In a BST:

• All values in the left subtree of a node are less than the node's value, while all values in the right subtree are greater. This property allows for efficient searching, insertion, and deletion operations.
• The average time complexity for inserting, searching, and deleting nodes is O(log n), which means it scales well as the number of nodes increases. However, in the worst case (e.g., when the tree becomes a linear chain), these operations may take up to O(n).

Think of a library organized by genres, authors, and titles. Each genre acts as a parent category that groups similar books together (left for those with earlier titles, right for those with later). Just like finding a book, a BST allows you to efficiently locate items because you systematically narrow down the possibilities with every question you ask.

AVL Tree (Adelson-Velsky and Landis)

• A self-balancing BST.
• Balance factor (height left - height right) must be in [-1, 0, 1].

Red-Black Tree

• A binary tree with nodes marked red or black.
• Ensures O(log n) time for insertion, deletion, and lookup.

Balanced trees, like AVL Trees and Red-Black Trees, are special BSTs that ensure the tree remains balanced after every insertion or deletion.

• An AVL Tree checks the height of subtrees and maintains a balance factor (the difference in height between the left and right subtrees). If the balance factor exceeds 1 or -1, rotations are performed to maintain balance.
• A Red-Black Tree uses a coloring system (red or black) for the nodes to ensure that the tree remains balanced, enabling guaranteed O(log n) time for all operations.

Imagine a balance scale. If you add weight to one side (insert a node in a certain way), it tips over. To keep it balanced (like maintaining tree height), you might redistribute the weights or move them to the other side. In these tree structures, balance ensures that we can always find information quickly, much like keeping a scale level lets you weigh accurately.

A heap is a complete binary tree used to implement priority queues.

• Min-Heap: Parent ≤ children
• Max-Heap: Parent ≥ children

Operations:

• Insert: O(log n)
• Extract-Min/Max: O(log n)
• Build-Heap: O(n)

Heaps are a type of binary tree that serves as an efficient priority queue, where the highest or lowest priority element can be accessed quickly. There are two types:

• In a Min-Heap, the parent node is always less than or equal to its children, ensuring the smallest element is at the root.
• In a Max-Heap, the opposite is true: the parent is greater than or equal to its children, placing the largest element at the root.
• Insertion and extraction of minimum or maximum values has a time complexity of O(log n), while building a heap from an array can be done in O(n).

Think of a priority list of tasks. The most urgent task is at the top (root), and as tasks are added or completed, the list adjusts itself to keep the most pressing task visible. Just like in a heap, where the next most important task can be accessed quickly, helping you stay organized and efficient.

A tree-based data structure for storing strings, used especially for autocomplete and spell checking.

• Each node represents a character of the string.
• Fast lookup: O(length of word)

Tries, also known as prefix trees, are specialized trees used to store strings, allowing for fast retrieval based on prefixes.

• Each node corresponds to a character, so a path from the root to any node represents a prefix of one or more words. This helps in operations like autocomplete, where it quickly suggests words that start with a certain set of characters. The lookup time is efficient, typically O(length of the word).

Imagine a library catalog system where you can type the first few letters of a book title. The system then fetches possible titles matching that prefix. Tries function similarly, allowing users to quickly access relevant suggestions without scanning the entire list of words, just like how browsing through categorized sections in a library makes finding a book easier.

--