Trees and Graphs

1. Trees

A tree is a hierarchical data structure that consists of nodes connected by edges. It's a non-linear structure that organizes data in a parent-child relationship. Unlike a linked list where data is sequential, a tree has a root node, and each node can have zero or more child nodes. This structure is fundamental in computer science for representing hierarchical relationships, such as file systems, organizational charts, or decision trees.

Key properties of a tree:

• It is a connected graph with no cycles.
• A tree with N nodes always has N-1 edges.
• There is a unique path between any two nodes in a tree.
• It has a designated root node.

Terminology associated with trees:

• Root: The topmost node of the tree.
• Node: An element in the tree.
• Edge: A connection between two nodes.
• Parent: The node directly above a given node.
• Child: A node directly below a given node.
• Leaf Node: A node with no children.
• Internal Node: A node with at least one child.
• Siblings: Nodes that share the same parent.
• Depth of a Node: The number of edges from the root to the node.
• Height of a Node: The number of edges from the node to the deepest leaf.
• Height of a Tree: The height of its root node.
• Degree of a Node: The number of children a node has.

1.1 Forests

A forest is a collection of disjoint trees. If a graph is acyclic, it can be decomposed into a forest. In simpler terms, imagine you have several separate tree structures, each with its own root, and none of them are connected to each other. This collection of individual trees is called a forest. Forests are often encountered when dealing with algorithms that process graphs, where removing edges might break a single connected component into multiple trees.

2. Binary Trees

A binary tree is a special type of tree data structure where each node has at most two children, referred to as the left child and the right child. This restriction makes binary trees simpler to manage and implement compared to general trees. They are widely used in various applications, including searching, sorting, and representing expressions.

A binary tree can be defined recursively:

• An empty tree is a binary tree.
• A node with a value, a left binary tree, and a right binary tree is a binary tree.

2.1 Types of Binary Trees

• Full Binary Tree: A tree where every node has either 0 or 2 children.
• Complete Binary Tree: A binary tree in which all levels are completely filled except possibly the last level, and the last level has all keys as left as possible.
• Perfect Binary Tree: A binary tree in which all interior nodes have two children and all leaves are at the same level.
• Balanced Binary Tree: A binary tree where the height difference between the left and right subtrees of any node is not more than one.

2.2 Tree Traversal

Tree traversal is the process of visiting each node in the tree exactly once. There are several ways to traverse a binary tree, typically categorized as depth-first (preorder, inorder, postorder) and breadth-first.

• Inorder Traversal (Left, Root, Right): Visits the left subtree, then the root node, then the right subtree. For a Binary Search Tree, this traversal visits nodes in ascending order.
• Preorder Traversal (Root, Left, Right): Visits the root node first, then the left subtree, then the right subtree. Useful for copying a tree.
• Postorder Traversal (Left, Right, Root): Visits the left subtree, then the right subtree, then the root node. Useful for deleting a tree.
• Level Order Traversal (Breadth-First): Visits nodes level by level, from left to right.

2.3 Representation of Binary Trees

Binary trees can be represented using two primary methods:

• Array Representation: Suitable for complete binary trees. If a node is at index `i`, its left child is at `2*i + 1` and its right child is at `2*i + 2`. The parent is at `floor((i-1)/2)`. This can be space-inefficient for sparse trees.
• Linked Representation: Each node is an object or structure containing data and pointers (or references) to its left and right children. This is more flexible and space-efficient for non-complete trees.

3. Threaded Binary Trees

A threaded binary tree is a modified binary tree in which the null left and right pointers are used to point to the inorder predecessor and successor of a node, respectively. This technique improves the efficiency of inorder traversal by eliminating the need for recursion or an explicit stack.

There are two types of threads:

• Single Threaded: Only one type of null pointer (e.g., right pointer) is used for threading.
• Double Threaded: Both null left and right pointers are used for threading.

In a threaded binary tree, each node typically has an additional flag for each pointer to indicate whether the pointer points to a child node or an inorder predecessor/successor.

4. Binary Search Trees (BST)

A Binary Search Tree (BST) is a binary tree data structure that satisfies the following properties:

• The left subtree of a node contains only nodes with keys lesser than the node's key.
• The right subtree of a node contains only nodes with keys greater than the node's key.
• The left and right subtrees each must also be a binary search tree.
• There must be no duplicate nodes (though variations exist that allow duplicates).

These properties make BSTs very efficient for searching, insertion, and deletion operations, typically taking O(log n) time on average, where 'n' is the number of nodes. However, in the worst case (e.g., a skewed tree resembling a linked list), these operations can degrade to O(n).

4.1 Operations on BST

• Search: Start at the root. If the key matches, return the node. If the key is less than the current node's key, go left. If the key is greater, go right. Repeat until found or a null pointer is encountered (key not present).
• Insertion: Search for the key. If found, it might be an error or handled based on BST variant rules. If not found, insert the new node at the position where the search ended (where a null pointer was encountered).
• Deletion: This is more complex.
  • If the node to be deleted is a leaf node, simply remove it.
  • If the node has one child, replace the node with its child.
  • If the node has two children, find its inorder successor (the smallest node in its right subtree) or inorder predecessor (the largest node in its left subtree). Replace the node's data with the successor/predecessor's data, and then delete the successor/predecessor node (which will have at most one child).

5. AVL Trees

An AVL tree is a self-balancing binary search tree. It was the first type of self-balancing BST to be invented. The key feature of an AVL tree is that it maintains a 'balance factor' for each node, which is the difference between the height of its left subtree and the height of its right subtree. For an AVL tree, this balance factor must always be -1, 0, or 1.

Balance Factor = Height(Left Subtree) - Height(Right Subtree)

If an insertion or deletion operation causes the balance factor of any node to become less than -1 or greater than 1, the tree performs rotations to restore the balance. These rotations ensure that the height of the tree remains O(log n), guaranteeing efficient search, insertion, and deletion operations in O(log n) time even in the worst case.

5.1 Rotations in AVL Trees

There are four types of rotations used to rebalance an AVL tree:

• Left Rotation (LL imbalance): Used when an insertion into the left subtree of the left child causes imbalance.
• Right Rotation (RR imbalance): Used when an insertion into the right subtree of the right child causes imbalance.
• Left-Right Rotation (LR imbalance): A left rotation on the left child, followed by a right rotation on the node itself. Used when an insertion into the right subtree of the left child causes imbalance.
• Right-Left Rotation (RL imbalance): A right rotation on the right child, followed by a left rotation on the node itself. Used when an insertion into the left subtree of the right child causes imbalance.

These rotations restructure the tree locally to satisfy the AVL property without violating the BST property.

6. B-Tree Variants

A B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. Unlike binary search trees, B-trees are optimized for systems that read and write large blocks of data, such as disk-based file systems and databases. They have a high branching factor, meaning each node can have many children, which reduces the height of the tree and minimizes disk I/O operations.

A B-tree of order 'm' has the following properties:

• Every node has at most 'm' children.
• Every internal node (non-leaf) has at least ceil(m/2) children, except possibly the root which can have at least 2 children if it's not a leaf.
• All leaves appear at the same level.
• A non-leaf node with 'k' children contains 'k-1' keys.
• Keys in a node are stored in sorted order.
• For a node with keys K₁, K₂, ..., K_n-1 and children C₁, C₂, ..., C_n:
  • All keys in the subtree rooted at C₁ are less than K₁.
  • All keys in the subtree rooted at C_i (for 1 < i < n) are greater than K_i-1 and less than K_i.
  • All keys in the subtree rooted at C_n are greater than K_n-1.

6.1 B+ Tree

A B+ tree is a variation of the B-tree that is commonly used in database systems and file systems. It optimizes for efficient retrieval of data, especially range queries.

Key characteristics of B+ trees:

• All data is stored only in the leaf nodes. Internal nodes only store keys to guide the search.
• Leaf nodes are linked together sequentially, forming a linked list. This allows for efficient range queries (e.g., finding all records between two keys).
• Each non-leaf node has as many children as possible (up to the order 'm').
• Each leaf node can store multiple keys and associated data pointers.

The primary advantage of B+ trees over B-trees for database systems is their ability to handle range queries efficiently due to the linked list of leaf nodes and the fact that all data resides at the leaf level.

6.2 B* Tree

A B* tree is another variation that aims to improve space utilization compared to B-trees. When a node is full, instead of splitting it into two, a B* tree attempts to redistribute keys and children with a sibling node. If redistribution is not possible, then the node splits into two, but it tries to split into two nodes that are two-thirds full rather than half full. This leads to a higher average number of keys per node and thus a lower tree height.

7. Graphs

A graph is a data structure consisting of a set of vertices (or nodes) and a set of edges that connect pairs of vertices. Graphs are used to model real-world relationships between objects, such as social networks, road maps, computer networks, and the World Wide Web.

Graphs can be:

• Directed (Digraphs): Edges have a direction. An edge from vertex A to vertex B does not imply an edge from B to A.
• Undirected: Edges are bidirectional. An edge between A and B means A is connected to B and B is connected to A.

Other properties:

• Weighted Graph: Each edge has an associated weight or cost.
• Unweighted Graph: All edges have a weight of 1 (or no weight is considered).
• Connected Graph: For an undirected graph, there is a path between every pair of vertices.
• Disconnected Graph: Not connected.
• Cyclic Graph: Contains at least one cycle.
• Acyclic Graph (e.g., Tree): Contains no cycles.
• Complete Graph: Every pair of distinct vertices is connected by a unique edge.
• Sparse Graph: Has relatively few edges compared to the maximum possible number of edges.
• Dense Graph: Has many edges.

7.1 Representation of Graphs

Graphs can be represented in several ways:

• Adjacency Matrix: A 2D array (matrix) `G[V][V]` where `V` is the number of vertices. `G[i][j] = 1` (or the weight) if there's an edge from vertex `i` to vertex `j`, and `0` otherwise. For undirected graphs, the matrix is symmetric. This is efficient for dense graphs but space-inefficient for sparse graphs (O(V^2) space).
• Adjacency List: An array of lists, where each index `i` corresponds to vertex `i`. The list at index `i` contains all vertices adjacent to vertex `i`. This is space-efficient for sparse graphs (O(V+E) space) and efficient for iterating over neighbors.
• Incidence Matrix: A `V x E` matrix where each column represents an edge and each row represents a vertex. `M[i][j] = 1` if vertex `i` is incident to edge `j`.

7.2 Graph Traversal Algorithms

These algorithms visit all vertices reachable from a starting vertex.

• Breadth-First Search (BFS): Explores the graph level by level. It uses a queue to keep track of vertices to visit. BFS is often used to find the shortest path in an unweighted graph.
• Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. It typically uses recursion or an explicit stack. DFS is useful for finding cycles, topological sorting, and connectivity problems.

7.3 Applications of Graphs

• Shortest Path Algorithms: Dijkstra's algorithm, Bellman-Ford algorithm (for weighted graphs).
• Minimum Spanning Tree (MST): Prim's algorithm, Kruskal's algorithm (for finding a subset of edges that connects all vertices with the minimum total edge weight).
• Network Flow: Ford-Fulkerson algorithm.
• Topological Sorting: Ordering vertices in a directed acyclic graph (DAG) such that for every directed edge from vertex u to vertex v, u comes before v in the ordering.
• Cycle Detection: Identifying cycles in directed or undirected graphs.