AVL Tree | Heap | B- Tree | B+ Tree | CSE205 : DATA STRUCTURES AND ALGORITHMS | B.Tech CSE

AVL Tree | Heap | B- Tree | B+ Tree

⭐AVL Tree

• A self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1.
• Tree is said to be balanced if balance factor of each node is in between -1 to 1

• Balance Factor (k) = height (left(k)) - height (right(k))
• Balance factor = 1. Therefore, left sub-tree is one level higher than the right sub-tree.
• Balance factor = 0. Therefore, left sub-tree and right sub-tree contain equal height.
• Balance factor = -1. Therefore, left sub-tree is one level lower than the right sub-tree

⭐AVL Tree: Rotations

• Single Rotations:
• Right-Right (RR) - Single left rotation

• Left-Left (LL) - Single right rotation

• Double Rotations:
• Left-Right (LR) - Left rotation followed by a right rotation

• Right-Left (RL) - Right rotation followed by a left rotation

⭐AVL Tree: Operations

1) AVL TREE - Insertion

Let us construct an AVL Tree by inserting numbers from 1 to 8

2) AVL TREE - Deletion

Delete node 28 & 30 and draw the tree after each deletion

CODE:

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    int height;
};

int getHeight(Node* node) {
    return node ? node->height : 0;
}

int getBalanceFactor(Node* node) {
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
}

Node* createNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = node->right = nullptr;
    node->height = 1;
    return node;
}

Node* rotateRight(Node* y) {
    Node* x = y->left;
    y->left = x->right;
    x->right = y;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    return x;
}

Node* rotateLeft(Node* x) {
    Node* y = x->right;
    x->right = y->left;
    y->left = x;
    x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
    y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
    return y;
}

// Recursive function to insert a new node into the AVL tree
Node* insert(Node* node, int data) {
    if (!node) { 
        return createNode(data);
    }

    if (data < node->data) { 
        node->left = insert(node->left, data);
    }
    else if (data > node->data) { 
        node->right = insert(node->right, data);
    }    
    else { 
        return node;
    }    

    node->height = 1 + max(getHeight(node->left), getHeight(node->right));
    int balance = getBalanceFactor(node);

    if (balance > 1 && data < node->left->data) { 
        return rotateRight(node);
    }
    if (balance < -1 && data > node->right->data) { 
        return rotateLeft(node);
    }
    if (balance > 1 && data > node->left->data) {
        node->left = rotateLeft(node->left);
        return rotateRight(node);
    }
    if (balance < -1 && data < node->right->data) {
        node->right = rotateRight(node->right);
        return rotateLeft(node);
    }
    return node;
}

// Function to find the node with the minimum value in a tree
Node* minValueNode(Node* node) {
    Node* current = node;
    while (current->left){ 
        current = current->left;
    }
    return current;
}

// Recursive function to delete a node from the AVL tree
Node* deleteNode(Node* root, int data) {
    if (!root){ 
        return root;
    }

    if (data < root->data) { 
        root->left = deleteNode(root->left, data);
    }
    else if (data > root->data) { 
        root->right = deleteNode(root->right, data);
    }
    else {
        if (!root->left || !root->right) {
            Node* temp = root->left ? root->left : root->right;
            if (!temp) {
                temp = root;
                root = nullptr;
            } 
            else { 
                *root = *temp;
            }
            delete temp;
        } else {
            Node* temp = minValueNode(root->right);
            root->data = temp->data;
            root->right = deleteNode(root->right, temp->data);
        }
    }
    if (!root) { 
        return root;
    }

    root->height = 1 + max(getHeight(root->left), getHeight(root->right));
    int balance = getBalanceFactor(root);

    if (balance > 1 && getBalanceFactor(root->left) >= 0) { 
        return rotateRight(root);
    }
    if (balance > 1 && getBalanceFactor(root->left) < 0) {
        root->left = rotateLeft(root->left);
        return rotateRight(root);
    }
    if (balance < -1 && getBalanceFactor(root->right) <= 0) { 
        return rotateLeft(root);
    }
    if (balance < -1 && getBalanceFactor(root->right) > 0) {
        root->right = rotateRight(root->right);
        return rotateLeft(root);
    }
    return root;
}

// Function for in-order traversal of the tree
void inorderTraversal(Node* root) {
    if (!root){ 
        return;
    }
    inorderTraversal(root->left);
    cout << root->data << " ";
    inorderTraversal(root->right);
}

int main() {
    Node* root = nullptr;
    root = insert(root, 10);
    root = insert(root, 20);
    root = insert(root, 30);
    root = insert(root, 40);
    root = insert(root, 50);
    root = insert(root, 25);

    cout << "Inorder traversal of the AVL tree: ";
    inorderTraversal(root);
    cout << endl;

    root = deleteNode(root, 40);
    cout << "Inorder traversal after deletion of 40: ";
    inorderTraversal(root);
    cout << endl;

    return 0;
}

OUTPUT:

Inorder traversal of the AVL tree: 10 20 25 30 40 50 

Inorder traversal after deletion of 40: 10 20 25 30 50

⭐HEAP:

• A Heap is a special tree-based data structure in which the tree is a complete binary tree.

• Complete Binary Tree
• A binary tree is said to be a complete binary tree if all its levels, except possibly the last level, have the maximum number of possible nodes, and all the nodes in the last level appear as far left as possible.

⭐ Differences Between Max Heap and Min Heap

Feature	Max Heap	Min Heap
Definition	The parent node is greater than its children.	The parent node is less than its children.
Root Node	Contains the maximum value.	Contains the minimum value.
Insertion	New elements are added at the end and then "bubbled up."	New elements are added at the end and then "bubbled up."
Deletion	Typically removes the root and restructures.	Typically removes the root and restructures.
Use Cases	Used in priority queues where the highest priority element is served first.	Used in priority queues where the lowest priority element is served first.
Implementation	Often implemented using arrays (parent-child relationships).	Often implemented using arrays (parent-child relationships).

⭐Heap: Operations

1) Heap - Insertion

Create the max heap tree 44, 33, 77, 11, 55

2) Heap - Deletion

⭐Max Heap:

CODE:

#include <stdio.h>

// Swap function
void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

// Function to maintain the max-heap property
void maxHeapify(int arr[], int size, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < size && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < size && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        
        maxHeapify(arr, size, largest);
    }
}

// Function to build a max heap from an array
void buildMaxHeap(int arr[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, size, i);
    }
}

// Function to insert an element into the Max Heap
void insertElement(int arr[], int *size, int value) {
    arr[*size] = value;
    (*size)++;
    
    //buildMaxHeap(arr, *size);
    //can be used inplace of below lines but it make O(long n) to 0(n)

    int i = *size - 1;
    while (i != 0 && arr[(i - 1) / 2] < arr[i]) {
        swap(&arr[i], &arr[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

//Function to delete given element from heap
void deleteElement(int arr[], int* size, int value) {
    int indexToDelete = -1;
    for (int i = 0; i < *size; i++) {
        if (arr[i] == value) {
            indexToDelete = i;
            break;
        }
    }

    if (indexToDelete == -1){
        printf("Element not found\n");
        return;
    }

    arr[indexToDelete] = arr[*size - 1];
    (*size)--;

    maxHeapify(arr, *size, indexToDelete);
}

// Function to delete the root (largest) element from the heap
void deleteRoot(int arr[], int *size) {
    if (*size <= 0) {
        return;
    }
    
    arr[0] = arr[*size - 1];
    (*size)--;
    
    maxHeapify(arr, *size, 0);
}

// Function to print the Max Heap
void displayMaxHeap(int arr[], int size) {
    printf("Max Heap: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Function to perform heap sort
void heapSort(int arr[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        maxHeapify(arr, size, i);
    }

    for (int i = size - 1; i >= 1; i--) {
        swap(&arr[0], &arr[i]);

        maxHeapify(arr, i, 0);
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    
    int size = 0;
    
    // Insert all values into the max-heap
    for (int i = 0; i < n; i++) {
        int value;
        scanf("%d", &value);
        insertElement(arr, &size, value);
    }

    // Build the initial max-heap
    //buildMaxHeap(arr, size);
    //use it when element are not inserted using "insertElement"

    // Display the max-heap
    displayMaxHeap(arr, size);
    
    // Delete the root node and display it
    printf("Root node: %d\n", arr[0]);
    deleteRoot(arr, &size);
    
    // Display the max-heap
    displayMaxHeap(arr, size);
    
    //Delete element from the max-heap and restore the heap
    int key;
    scanf("%d", &key);
    deleteElement(arr, &size, key);
    
    // Display the max-heap
    displayMaxHeap(arr, size);
    
    //heap short descending order:
    heapSort(arr, size);
    
    // Display the max-heap
    displayMaxHeap(arr, size);
    
    return 0;
}

INPUT:

5

1 23 40 11 66

4

OUTPUT:

Max Heap: 66 40 23 1 11 

Root node: 66

Max Heap: 40 11 23 1 

Element not found

Max Heap: 40 11 23 1 

Max Heap: 1 11 23 40 

⭐Min Heap:

CODE:

#include <stdio.h>

// Swap function
void swap(int *x, int *y) {
    int temp = *x;
    *x = *y;
    *y = temp;
}

// Function to ensure the min-heap property
void minHeapify(int arr[], int size, int i) {
    int smallest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < size && arr[left] < arr[smallest]) {
        smallest = left;
    }

    if (right < size && arr[right] < arr[smallest]) {
        smallest = right;
    }

    if (smallest != i) {
        swap(&arr[i], &arr[smallest]);
        
        minHeapify(arr, size, smallest);
    }
}

// Function to build a min-heap from an array
void buildMinHeap(int arr[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        minHeapify(arr, size, i);
    }
}

// Function to insert an element into the min-heap
void insertElement(int arr[], int *size, int value) {
    arr[*size] = value;
    (*size)++;
    
    //buildMinHeap(arr, *size);
    //can be used inplace of below lines but it make O(long n) to 0(n)
    
    int i = *size - 1;
    while (i > 0 && arr[(i - 1) / 2] > arr[i]) {
        swap(&arr[i], &arr[(i - 1) / 2]);
        i = (i - 1) / 2;
    }
}

//Function to delete given element from heap
void deleteElement(int arr[], int* size, int value) {
    int indexToDelete = -1;
    for (int i = 0; i < *size; i++) {
        if (arr[i] == value) {
            indexToDelete = i;
            break;
        }
    }

    if (indexToDelete == -1){
        printf("Element not found\n");
        return;
    }

    arr[indexToDelete] = arr[*size - 1];
    (*size)--;

    minHeapify(arr, *size, indexToDelete);
}

// Function to delete the root (smallest) element from the heap
void deleteRoot(int arr[], int *size) {
    if (*size <= 0){
        return;
    }
    
    arr[0] = arr[*size - 1];
    (*size)--;

    minHeapify(arr, *size, 0);
}

// Function to display the min-heap
void displayMinHeap(int arr[], int size) {
    printf("Min Heap: ");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Function to perform heap sort
void heapSort(int arr[], int size) {
    for (int i = size / 2 - 1; i >= 0; i--) {
        minHeapify(arr, size, i);
    }

    for (int i = size - 1; i >= 1; i--) {
        swap(&arr[0], &arr[i]);

        minHeapify(arr, i, 0);
    }
    
    //bubbleSort for Descending order
    for (int i = 0; i < size - 1; i++) {
        for (int j = 0; j < size - 1 - i; j++) {
            // Compare adjacent elements and swap if necessary
            if (arr[j] < arr[j + 1]) {
                // Swap elements
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

int main() {
    int n;
    scanf("%d", &n);
    int arr[n];
    
    int size = 0;
    
    // Insert all values into the min-heap
    for (int i = 0; i < n; i++) {
        int value;
        scanf("%d", &value);
        insertElement(arr, &size, value);
    }

    // Build the initial min-heap
    //buildMinHeap(arr, size);
    //use it when element are not inserted using "insertElement"
    
    // Display the min-heap
    displayMinHeap(arr, size);
    
    // Delete the root node and display it
    printf("Root node: %d\n", arr[0]);
    deleteRoot(arr, &size);
    
    // Display the min-heap
    displayMinHeap(arr, size);
    
    //Delete element from the min-heap and restore the heap
    int key;
    scanf("%d", &key);
    deleteElement(arr, &size, key);
    
    // Display the min-heap
    displayMinHeap(arr, size);
    
    //heap short ascending order:
    heapSort(arr, size);
    
    // Display the min-heap
    displayMinHeap(arr, size);
    
    return 0;
}

INPUT:

5

1 23 40 11 66

4

OUTPUT:

Min Heap: 1 11 40 23 66 

Root node: 1

Min Heap: 11 23 40 66 

Element not found

Min Heap: 11 23 40 66 

Min Heap: 66 40 23 11 

⭐B- Tree:

• B-tree is a special type of self-balancing search tree in which each node can contain more than one key and can have more than two children.
• It is also known as a height-balanced m-way tree.

• B-tree Properties:
• For each node x, the keys are stored in increasing order.
• In each node, there is a boolean value x.leaf which is true if x is a leaf.
• If n is the order of the tree, each internal node can contain at most n - 1 keys along with a pointer to each child.
• Each node except root can have at most n children and at least n/2 children.
• All leaves have the same depth (i.e. height-h of the tree).
• The root has at least 2 children and contains a minimum of 1 key.
• If n ≥ 1, then for any n-key B-tree of height h and minimum degree t ≥ 2, h ≥ logt (n+1)/2.

EXAMPLE:

#Question
Consider an initially empty B-Tree of order 3. Perform the following operations step-by-step, showing the state of the tree after each operation:
Insert the following elements: 10, 20, 5, 6, 12, 30, 7, 17
Search for the elements: 6, 15, and 20
Delete the elements: 6, 17, and 10
Display the tree with an in-order traversal

#Solution
Let's go through each operation step-by-step:

#Step 1: Insert Elements
Insert 10:
Since the tree is empty, we insert 10 into the root node.
Tree after inserting 10:
[10]
Insert 20:
20 goes to the right of 10 in the root node since there's still space.
Tree after inserting 20:
[10, 20]
Insert 5:
5 goes to the left of 10 in the root node.
Tree after inserting 5:
[5, 10, 20]
Insert 6:
Adding 6 will exceed the maximum number of keys in a node (2 for order 3). We split the node.
Split around the middle element 10. 10 moves up to become the new root.
5 remains in the left child, and 20 remains in the right child.
Now we insert 6 in the left child.
Tree after inserting 6:
       [10]
      /    \
   [5, 6]  [20]
Insert 12:
12 goes to the right of 10 but to the left of 20 in the right child.
Tree after inserting 12:
       [10]
      /    \
   [5, 6]  [12, 20]
Insert 30:
30 goes to the right of 20 in the right child.
Tree after inserting 30:
       [10]
      /    \
   [5, 6]  [12, 20, 30]
Insert 7:
7 goes into the left child [5, 6]. However, adding 7 will exceed the node’s capacity, so we split this node.
Split around 6. 6 moves up to the root.
The root now contains [6, 10], and 5 and 7 become the left child.
Tree after inserting 7:
        [6, 10]
       /    |    \
    [5]   [7]   [12, 20, 30]
Insert 17:
17 goes into the right child [12, 20, 30], but this will exceed its capacity, so we split it around 20.
20 moves up to the root.
Now the root contains [6, 10, 20].
12 becomes the left child of 20, and 30 becomes its right child.
Tree after inserting 17:
         [6, 10, 20]
       /     |     |    \
    [5]    [7]   [12, 17] [30]

#Step 2: Search for Elements
Search for 6:
Start from the root. 6 is found in the root node.
Search for 15:
15 is not found in the B-tree.
Search for 20:
Start from the root. 20 is found in the root node.

#Step 3: Delete Elements
Delete 6:
6 is in the root node. Since the right child [7] can support a merge, we replace 6 with 7.
Tree after deleting 6:
        [7, 10, 20]
       /     |     |    \
    [5]     []   [12, 17] [30]
Delete 17:
17 is in the [12, 17] node. We simply remove 17 from this node.
Tree after deleting 17:
        [7, 10, 20]
       /     |     |    \
    [5]     []    [12]   [30]
Delete 10:
10 is in the root. We replace 10 with the next smallest element in the subtree, 12.
Tree after deleting 10:
        [7, 12, 20]
       /     |     |    \
    [5]     []    []   [30]

#Step 4: In-Order Traversal
Performing an in-order traversal, we visit nodes in ascending order:

#In-Order Traversal Output:
5, 7, 12, 20, 30

⭐B+ Tree:

• A B+ tree is an advanced form of a self-balancing tree in which all the values are present in the leaf level.
• An important concept to be understood before learning B+ tree is multilevel indexing. 
• In multilevel indexing, the index of indices is created as in figure below. 
• It makes accessing the data easier and faster.

• Properties of a B+ Tree
• All leaves are at the same level.
• The root has at least two children.
• Each node except root can have a maximum of m children and at least m/2 children.
• Each node can contain a maximum of m - 1 keys and a minimum of ⌈m/2⌉ - 1 keys.

EXAMPLE:

#Question
Consider an initially empty B+ Tree of order 3. Perform the following operations, showing the state of the tree after each:
Insert the following elements: 10, 20, 5, 6, 12, 30, 7, 17
Search for the elements: 6, 15, and 20
Delete the elements: 6, 17, and 10
Display the tree with an in-order traversal

#Solution
We’ll go through each operation, explaining the steps and showing the tree's structure after each.

#Step 1: Insert Elements
Insert 10:
Start with an empty B+ Tree.
Insert 10 into a new leaf node, as it's the first element.
Tree after inserting 10:
Leaf Nodes: [10]
Insert 20:
20 is added to the same leaf node as 10 since there's still space.
Tree after inserting 20:
Leaf Nodes: [10, 20]
Insert 5:
5 is added to the leaf node containing 10 and 20, but this causes the node to exceed its capacity (2 keys for order 3).
Split this leaf node:
The node is split around 10, making 10 the new root key.
5 is in the left leaf node, and 10, 20 is in the right leaf node.
Tree after inserting 5:
       [10]
      /     \
   [5]     [10, 20]
Insert 6:
6 goes to the leaf node [5] since it’s less than 10.
Insert 6 in sorted order.
Tree after inserting 6:
       [10]
      /     \
   [5, 6]  [10, 20]
Insert 12:
12 goes to the leaf node [10, 20] since it’s greater than 10.
Tree after inserting 12:
       [10]
      /     \
   [5, 6]  [10, 12, 20]
Insert 30:
30 goes to the leaf node [10, 12, 20], but adding it exceeds capacity, so we split this node.
Split around 20, promoting 20 to the root.
The tree now has 10 and 20 as internal nodes in the root.
10, 12 is the left leaf of 20, and 30 is the right leaf of 20.
Tree after inserting 30:
       [10, 20]
      /    |    \
   [5, 6] [10, 12] [30]
Insert 7:
7 goes to the leaf node [5, 6]. Adding 7 causes it to exceed capacity, so we split around 6.
6 is promoted to the root.
5 remains in the leftmost leaf node, and 7 forms a new leaf node.
Tree after inserting 7:
       [6, 10, 20]
      /   |     |    \
   [5]   [7]  [10, 12] [30]
Insert 17:
17 goes to the leaf node [10, 12] and is added in sorted order.
Tree after inserting 17:
       [6, 10, 20]
      /   |     |    \
   [5]   [7]  [10, 12, 17] [30]

#Step 2: Search for Elements
Search for 6:
Start from the root, find 6 in the root keys, and check the left child. 6 is found in the left leaf node.
Search for 15:
Traverse from the root. Since 15 is between 10 and 20, go to the child [10, 12, 17]. 15 is not found here.
Search for 20:
20 is found directly in the root keys.

#Step 3: Delete Elements
Delete 6:
6 is in the root and the leaf node [5]. After removing it, we merge [5] and [7] into [5, 7].
The tree root becomes [10, 20].
Tree after deleting 6:
       [10, 20]
      /    |    \
   [5, 7] [10, 12, 17] [30]
Delete 17:
17 is in the leaf [10, 12, 17]. Simply remove 17 from this leaf.
Tree after deleting 17:
       [10, 20]
      /    |    \
   [5, 7] [10, 12] [30]
Delete 10:
10 is in the root. Remove 10, and promote 12 to the root to keep the tree balanced.
Tree after deleting 10:
       [12, 20]
      /    |    \
   [5, 7]   []   [30]

#Step 4: In-Order Traversal
Performing an in-order traversal:

#In-Order Traversal Output:
5, 7, 12, 20, 30

---

🚨Thanks for visiting classpdfindia✨

Welcome to a hub for 😇Nerds and knowledge seekers! Here, you'll find everything you need to stay updated on education, notes, books, and daily trends.

💗 Bookmark our site to stay connected and never miss an update!

💌 Have suggestions or need more content? Drop a comment below, and let us know what topics you'd like to see next! Your support means the world to us. 😍