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.
