Unit 4: Trees Flashcards
Binary Tree
Definition: A binary tree is a hierarchical structure where each node has at most two children, referred to as the left child and the right child.
Properties:
Maximum number of nodes at level l is 2^l. Maximum number of nodes in a binary tree of height h is 2^(h+1) - 1.
Binary Tree Traversals
In-order: Left, Root, Right.
Pre-order: Root, Left, Right.
Post-order: Left, Right, Root.
Binary Tree Structure
typedef struct BTreeNode {
int data;
struct BTreeNode *left;
struct BTreeNode *right;
} BTreeNode;
In-order Traversal (Recursive)
void inOrder(BTreeNode *root) {
if (root) {
inOrder(root->left);
printf(“%d “, root->data);
inOrder(root->right);
}
}
Pre-order Traversal (Recursive)
void preOrder(BTreeNode *root) {
if (root) {
printf(“%d “, root->data);
preOrder(root->left);
preOrder(root->right);
}
}
Post-order Traversal (Recursive)
void postOrder(BTreeNode *root) {
if (root) {
postOrder(root->left);
postOrder(root->right);
printf(“%d “, root->data);
}
}
Height of a Binary Tree
Definition: The height of a binary tree is the length of the longest path from the root to a leaf node.
function height(node):
if node is NULL:
return -1
return 1 + max(height(node.left), height(node.right))
int height(BTreeNode *node) {
if (node == NULL) return -1;
return 1 + max(height(node->left), height(node->right));
}
Binary Search Tree (BST)
Definition: A BST is a binary tree with the left subtree containing only nodes with values less than the parent node, and the right subtree containing only nodes with values greater.
Properties:
Fast search, insert, and delete operations.
Insertion in BST
function insert(node, key):
if node is NULL:
return new_node(key)
if key < node.key:
node.left = insert(node.left, key)
else if key > node.key:
node.right = insert(node.right, key)
return node
Searching in BST
Pseudocode:
function search(node, key):
if node is NULL or node.key == key:
return node
if key < node.key:
return search(node.left, key)
return search(node.right, key)
Deletion in BST
function delete(node, key):
if node is NULL:
return node
if key < node.key:
node.left = delete(node.left, key)
else if key > node.key:
node.right = delete(node.right, key)
else:
// Node with only one child or no child
if node.left is NULL:
return node.right
else if node.right is NULL:
return node.left
// Node with two children: Get the inorder successor
temp = minValueNode(node.right)
node.key = temp.key
node.right = delete(node.right, temp.key)
return node
AVL Tree
Definition: An AVL tree is a self-balancing binary search tree where the difference between the heights of left and right subtrees cannot be more than one for all nodes.
Balancing Factor: For each node, it’s the height of the left subtree minus the height of the right subtree.
Rotations in AVL Trees
Types:
Right Rotation: Used when a left-heavy tree is unbalanced. Left Rotation: Used when a right-heavy tree is unbalanced. Left-Right Rotation: A combination used when the left subtree is right-heavy. Right-Left Rotation: A combination used when the right subtree is left-heavy.
Insertion in AVL Tree
function insert(node, key):
if node is NULL:
return new_node(key)
if key < node.key:
node.left = insert(node.left, key)
else if key > node.key:
node.right = insert(node.right, key)
node.height = 1 + max(height(node.left), height(node.right))
balance = getBalance(node)
// Perform rotations based on balance
return node
Deletion in AVL Tree
function delete(node, key):
if node is NULL:
return node
if key < node.key:
node.left = delete(node.left, key)
else if key > node.key:
node.right = delete(node.right, key)
else:
// Node with one child or no child
// Perform rotations if needed
return node
Graph Definition
Definition: A graph is a collection of nodes (vertices) connected by edges. It can be directed or undirected, weighted or unweighted.
Components:
Vertices (V): The individual points in the graph. Edges (E): The connections between vertices.
Graph Representation
Adjacency Matrix: A 2D array to represent graph connections.
Adjacency List: A list of lists to represent graph connections.
Adjacency Matrix Representation
define MAX 100
int adjMatrix[MAX][MAX];
adjMatrix[u][v] = 1
Adjacency List Representation
typedef struct Node {
int vertex;
struct Node* next;
} Node;
typedef struct Graph {
int numVertices;
Node** adjLists;
} Graph;
Graph Traversal: BFS
Breadth-First Search (BFS): Explores all neighbors at the present depth prior to moving on to nodes at the next depth level.
Algorithm:
Start at the root (or any arbitrary node). Mark it as visited and enqueue it. While the queue is not empty, dequeue a vertex, print it, and enqueue its unvisited neighbors.
BFS Implementation in C
void BFS(Graph* graph, int startVertex) {
bool visited[MAX] = {false};
Queue q;
enqueue(&q, startVertex);
visited[startVertex] = true;
while (!isEmpty(&q)) {
int currentVertex = dequeue(&q);
printf("%d ", currentVertex);
Node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (!visited[adjVertex]) {
enqueue(&q, adjVertex);
visited[adjVertex] = true;
}
temp = temp->next;
}
} }
Graph Traversal: DFS
Depth-First Search (DFS): Explores as far as possible along each branch before backing up.
Algorithm:
Start at the root (or any arbitrary node). Mark it as visited and recursively visit each unvisited neighbor.
DFS Implementation in C
void DFS(Graph* graph, int vertex, bool visited[]) {
visited[vertex] = true;
printf(“%d “, vertex);
Node* temp = graph->adjLists[vertex];
while (temp) {
int adjVertex = temp->vertex;
if (!visited[adjVertex]) {
DFS(graph, adjVertex, visited);
}
temp = temp->next;
} }
Graph Applications
Applications:
Social Networks: Representing users and connections. Routing Algorithms: Finding shortest paths. Network Flow Problems: Optimizing the flow of resources.
Shortest Path Algorithms
Dijkstra’s Algorithm: Used for finding the shortest path from a single source vertex to all other vertices in a graph with non-negative weights.
Bellman-Ford Algorithm: Computes shortest paths from a single source vertex to all other vertices, allowing for negative weights.
Dijkstra’s Algorithm Pseudocode
function Dijkstra(graph, source):
create a priority queue Q
for each vertex v in graph:
dist[v] = ∞
prev[v] = NULL
dist[source] = 0
Q.add(source, dist[source])
while Q is not empty:
u = Q.extract_min()
for each neighbor v of u:
alt = dist[u] + length(u, v)
if alt < dist[v]:
dist[v] = alt
prev[v] = u
Q.decrease_priority(v, alt)
Dijkstra’s Algorithm Implementation in C
void Dijkstra(Graph* graph, int startVertex) {
int dist[MAX]; // Distance from startVertex to each vertex
bool visited[MAX] = {false};
for (int i = 0; i < graph->numVertices; i++) {
dist[i] = INT_MAX;
}
dist[startVertex] = 0;
for (int i = 0; i < graph->numVertices - 1; i++) {
int u = minDistance(dist, visited, graph->numVertices);
visited[u] = true;
Node* temp = graph->adjLists[u];
while (temp) {
int v = temp->vertex;
if (!visited[v] && dist[u] != INT_MAX && dist[u] + getEdgeWeight(graph, u, v) < dist[v]) {
dist[v] = dist[u] + getEdgeWeight(graph, u, v);
}
temp = temp->next;
}
} }
Bellman-Ford Algorithm Pseudocode
function BellmanFord(graph, source):
for each vertex v in graph:
dist[v] = ∞
dist[source] = 0
for i from 1 to |V| - 1:
for each edge (u, v) in graph:
if dist[u] + weight(u, v) < dist[v]:
dist[v] = dist[u] + weight(u, v)
for each edge (u, v) in graph:
if dist[u] + weight(u, v) < dist[v]:
return "Negative weight cycle detected"
Bellman-Ford Implementation in C
void BellmanFord(Graph* graph, int startVertex) {
int dist[MAX];
for (int i = 0; i < graph->numVertices; i++) {
dist[i] = INT_MAX;
}
dist[startVertex] = 0;
for (int i = 1; i < graph->numVertices; i++) {
for (int u = 0; u < graph->numVertices; u++) {
Node* temp = graph->adjLists[u];
while (temp) {
int v = temp->vertex;
if (dist[u] != INT_MAX && dist[u] + getEdgeWeight(graph, u, v) < dist[v]) {
dist[v] = dist[u] + getEdgeWeight(graph, u, v);
}
temp = temp->next;
}
}
} }
Bubble Sort
Definition: A simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.
Complexity: O(n²) in the average and worst cases.
Bubble Sort Implementation in C
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
Selection Sort
Definition: A sorting algorithm that divides the input into two parts: a sorted and an unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the sorted part.
Complexity: O(n²) in all cases.
Selection Sort Implementation in C
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int minIndex = i;
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[minIndex])
minIndex = j;
}
// swap arr[minIndex] and arr[i]
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
}
Insertion Sort
Definition: A simple sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms.
Complexity: O(n²) in the average and worst cases.
Insertion Sort Implementation in C
void insertionSort(int arr[], int n) {
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
Merge Sort
Definition: A divide-and-conquer algorithm that sorts by recursively dividing the array in half, sorting each half, and then merging the sorted halves.
Complexity: O(n log n) in all cases.
Merge Sort Implementation in C
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++)
L[i] = arr[l + i];
for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
i = 0; j = 0; k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++; k++;
}
while (j < n2) {
arr[k] = R[j];
j++; k++;
} }
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
Complexity Analysis
Definition: The analysis of the efficiency of algorithms in terms of time and space complexity.
Big O Notation: Used to describe the upper limit of the time complexity in terms of the input size.
Space Complexity
Definition: The amount of memory space required by an algorithm as a function of the size of the input to the program.
Factors:
Auxiliary Space: Extra space or temporary space used by an algorithm.
Time Complexity Examples
O(1): Constant time (e.g., accessing an array element).
O(n): Linear time (e.g., linear search).
O(n log n): Log-linear time (e.g., merge sort).
O(n²): Quadratic time (e.g., bubble sort).
Recursion
Definition: A method of solving problems where the solution depends on solutions to smaller instances of the same problem.
Components:
Base Case: The condition under which the recursion ends. Recursive Case: The part of the function where the recursion occurs.
Applications of Hashing
Database Indexing: Fast data retrieval.
Caching: Storing frequently accessed data.
Data Integrity Checks: Ensuring data has not been altered.
Graphs vs Trees
Definition: Both are data structures used to represent hierarchical data.
Graphs:
Can have cycles. Can be directed or undirected.
Trees:
A special case of graphs with no cycles. Always directed.
Tree Traversals
In-Order Traversal: Left, Root, Right.
Pre-Order Traversal: Root, Left, Right.
Post-Order Traversal: Left, Right, Root.
Recursive In-Order Traversal:
void inOrder(BTreeNode* root) {
if (root) {
inOrder(root->left);
printf(“%d “, root->data);
inOrder(root->right);
}
}
Iterative In-Order Traversal:
void inOrderIterative(BTreeNode* root) {
Stack s = createStack();
BTreeNode* current = root;
while (current || !isEmpty(s)) {
while (current) {
push(s, current);
current = current->left;
}
current = pop(s);
printf("%d ", current->data);
current = current->right;
} }
Applications of Trees
File Systems: Hierarchical storage systems.
Databases: For indexing and retrieval.
Decision Making: Representing decisions and outcomes.
Sorting vs Searching Algorithms
Sorting Algorithms: Rearrange items in a specific order.
Searching Algorithms: Find a specific item in a collection.
Searching Algorithms Overview
Linear Search: O(n)
Binary Search: O(log n) - requires a sorted array.
Binary Search Implementation in C
int binarySearch(int arr[], int n, int key) {
int left = 0, right = n - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == key)
return mid; // Found
else if (arr[mid] < key)
left = mid + 1; // Search right
else
right = mid - 1; // Search left
}
return -1; // Not found
