by Jasleen Chhabra | Updated on 24 August 2024

Deletion in trees is a crucial operation that maintains the structure and properties of various types of trees. This guide will cover the deletion process in Binary Trees, Binary Search Trees (BSTs), AVL Trees, and B-Trees, providing detailed algorithms and C++ implementations.

Deleting from a Binary Tree

In a binary tree, deleting a node can be a bit tricky since the tree must remain connected after the deletion. The typical approach is to delete the deepest node in the tree.

Algorithm for Deletion in a Binary Tree:

1. If the tree is empty, return.
2. If the tree has only one node, delete it and return.
3. Find the deepest node in the tree.
4. Replace the node to be deleted with the deepest node's value.
5. Delete the deepest node.

C++ Implementation:

#include <iostream>

#include <queue>

 

struct Node {

    int data;

    Node* left;

    Node* right;

    Node(int value) : data(value), left(nullptr), right(nullptr) {}

};

 

void deleteDeepest(Node* root, Node* d_node) {

    std::queue<Node*> q;

    q.push(root);

    while (!q.empty()) {

        Node* temp = q.front();

        q.pop();

        if (temp == d_node) {

            temp = nullptr;

            delete d_node;

            return;

        }

        if (temp->right) {

            if (temp->right == d_node) {

                temp->right = nullptr;

                delete d_node;

                return;

            } else {

                q.push(temp->right);

            }

        }

        if (temp->left) {

            if (temp->left == d_node) {

                temp->left = nullptr;

                delete d_node;

                return;

            } else {

                q.push(temp->left);

            }

        }

    }

}

 

Node* deletionBT(Node* root, int key) {

    if (root == nullptr) return nullptr;

    if (root->left == nullptr && root->right == nullptr) {

        if (root->data == key) return nullptr;

        else return root;

    }

    std::queue<Node*> q;

    q.push(root);

    Node* temp;

    Node* key_node = nullptr;

    while (!q.empty()) {

        temp = q.front();

        q.pop();

        if (temp->data == key) key_node = temp;

        if (temp->left) q.push(temp->left);

        if (temp->right) q.push(temp->right);

    }

    if (key_node != nullptr) {

        int x = temp->data;

        deleteDeepest(root, temp);

        key_node->data = x;

    }

    return root;

}

 

void inOrderTraversal(Node* root) {

    if (root == nullptr) return;

    inOrderTraversal(root->left);

    std::cout << root->data << " ";

    inOrderTraversal(root->right);

}

 

int main() {

    Node* root = new Node(10);

    root->left = new Node(11);

    root->left->left = new Node(7);

    root->left->right = new Node(12);

    root->right = new Node(9);

    root->right->left = new Node(15);

    root->right->right = new Node(8);

   

    std::cout << "In-order traversal before deletion: ";

    inOrderTraversal(root);

    std::cout << std::endl;

   

    root = deletionBT(root, 11);

   

    std::cout << "In-order traversal after deletion: ";

    inOrderTraversal(root);

    return 0;

}

---

Deleting from a Binary Search Tree (BST)

In a BST, the deletion operation needs to ensure that the tree remains a valid BST after the node is deleted. There are three cases to handle: deleting a leaf node, deleting a node with one child, and deleting a node with two children.

Algorithm for Deletion in a BST:

1. If the node to be deleted is a leaf node, simply remove it.
2. If the node to be deleted has one child, replace it with its child.
3. If the node to be deleted has two children, find its in-order successor (the smallest node in the right subtree), replace the node's value with the in-order successor's value, and delete the in-order successor.

C++ Implementation:

struct BSTNode {

    int data;

    BSTNode* left;

    BSTNode* right;

    BSTNode(int value) : data(value), left(nullptr), right(nullptr) {}

};

 

BSTNode* minValueNode(BSTNode* node) {

    BSTNode* current = node;

    while (current && current->left != nullptr) current = current->left;

    return current;

}

 

BSTNode* deleteNode(BSTNode* root, int key) {

    if (root == nullptr) return root;

    if (key < root->data) {

        root->left = deleteNode(root->left, key);

    } else if (key > root->data) {

        root->right = deleteNode(root->right, key);

    } else {

        if (root->left == nullptr) {

            BSTNode* temp = root->right;

            delete root;

            return temp;

        } else if (root->right == nullptr) {

            BSTNode* temp = root->left;

            delete root;

            return temp;

        }

        BSTNode* temp = minValueNode(root->right);

        root->data = temp->data;

        root->right = deleteNode(root->right, temp->data);

    }

    return root;

}

 

void inOrderTraversalBST(BSTNode* root) {

    if (root == nullptr) return;

    inOrderTraversalBST(root->left);

    std::cout << root->data << " ";

    inOrderTraversalBST(root->right);

}

 

int main() {

    BSTNode* root = new BSTNode(50);

    root->left = new BSTNode(30);

    root->right = new BSTNode(70);

    root->left->left = new BSTNode(20);

    root->left->right = new BSTNode(40);

    root->right->left = new BSTNode(60);

    root->right->right = new BSTNode(80);

   

    std::cout << "In-order traversal before deletion: ";

    inOrderTraversalBST(root);

    std::cout << std::endl;

   

    root = deleteNode(root, 50);

   

    std::cout << "In-order traversal after deletion: ";

    inOrderTraversalBST(root);

    return 0;

}

---

Deleting from an AVL Tree

In an AVL Tree, the deletion operation needs to ensure that the tree remains balanced after the node is deleted. The balancing operations include rotations (LL, LR, RR, RL).

Algorithm for Deletion in an AVL Tree:

1. Perform standard BST deletion.
2. Update the height of the current node.
3. Get the balance factor of the current node.
4. Perform appropriate rotations to balance the tree.

C++ Implementation:

struct AVLNode {

    int data;

    AVLNode* left;

    AVLNode* right;

    int height;

    AVLNode(int value) : data(value), left(nullptr), right(nullptr), height(1) {}

};

 

int height(AVLNode* node) {

    return node ? node->height : 0;

}

 

int getBalanceFactor(AVLNode* node) {

    return node ? height(node->left) - height(node->right) : 0;

}

 

AVLNode* rightRotate(AVLNode* y) {

    AVLNode* x = y->left;

    AVLNode* T2 = x->right;

    x->right = y;

    y->left = T2;

    y->height = std::max(height(y->left), height(y->right)) + 1;

    x->height = std::max(height(x->left), height(x->right)) + 1;

    return x;

}

 

AVLNode* leftRotate(AVLNode* x) {

    AVLNode* y = x->right;

    AVLNode* T2 = y->left;

    y->left = x;

    x->right = T2;

    x->height = std::max(height(x->left), height(x->right)) + 1;

    y->height = std::max(height(y->left), height(y->right)) + 1;

    return y;

}

 

AVLNode* minValueNode(AVLNode* node) {

    AVLNode* current = node;

    while (current->left != nullptr) current = current->left;

    return current;

}

 

AVLNode* deleteNode(AVLNode* root, int key) {

    if (root == nullptr) return root;

    if (key < root->data) {

        root->left = deleteNode(root->left, key);

    } else if (key > root->data) {

        root->right = deleteNode(root->right, key);

    } else {

        if ((root->left == nullptr) || (root->right == nullptr)) {

            AVLNode* temp = root->left ? root->left : root->right;

            if (temp == nullptr) {

                temp = root;

                root = nullptr;

            } else {

                *root = *temp;

            }

            delete temp;

        } else {

            AVLNode* temp = minValueNode(root->right);

            root->data = temp->data;

            root->right = deleteNode(root->right, temp->data);

        }

    }

    if (root == nullptr) return root;

    root->height = std::max(height(root->left), height(root->right)) + 1;

    int balance = getBalanceFactor(root);

    if (balance > 1 && getBalanceFactor(root->left) >= 0) return rightRotate(root);

    if (balance > 1 && getBalanceFactor(root->left) < 0) {

        root->left = leftRotate(root->left);

        return rightRotate(root);

    }

    if (balance < -1 && getBalanceFactor(root->right) <= 0) return leftRotate(root);

    if (balance < -1 && getBalanceFactor(root->right) > 0) {

        root->right = rightRotate(root->right);

        return leftRotate(root);

    }

    return root;

}

 

void inOrderTraversalAVL(AVLNode* root) {

    if (root == nullptr) return;

    inOrderTraversalAVL(root->left);

    std::cout << root->data << " ";

    inOrderTraversalAVL(root->right);

}

 

int main() {

    AVLNode* root = new AVLNode(9);

    root->left = new AVLNode(5);

    root->right = new AVLNode(10);

    root->left->left = new AVLNode(1);

    root->left->right = new AVLNode(6);

    root->right->right = new AVLNode(11);

   

    std::cout << "In-order traversal before deletion: ";

    inOrderTraversalAVL(root);

    std::cout << std::endl;

   

    root = deleteNode(root, 10);

   

    std::cout << "In-order traversal after deletion: ";

    inOrderTraversalAVL(root);

    return 0;

}

---

Deleting from a B-Tree

In a B-Tree, deletion is a complex process because it needs to ensure that the properties of the B-Tree are maintained. The deletion process involves several cases, such as deleting from a leaf node, deleting from an internal node, and handling underflow by borrowing or merging nodes.

Algorithm for Deletion in a B-Tree:

1. If the key is in a leaf node, remove it.
2. If the key is in an internal node, replace it with the predecessor or successor key and delete the predecessor or successor key.
3. If the key is not present, recurse down to the appropriate child.
4. Handle underflow by borrowing from siblings or merging nodes if necessary.

C++ Implementation:

class BTreeNode {

public:

    int* keys;

    int t;

    BTreeNode** C;

    int n;

    bool leaf;

   

    BTreeNode(int _t, bool _leaf);

    void traverse();

    BTreeNode* search(int k);

    int findKey(int k);

    void insertNonFull(int k);

    void splitChild(int i, BTreeNode* y);

    void remove(int k);

    void removeFromLeaf(int idx);

    void removeFromNonLeaf(int idx);

    int getPred(int idx);

    int getSucc(int idx);

    void fill(int idx);

    void borrowFromPrev(int idx);

    void borrowFromNext(int idx);

    void merge(int idx);

 

    friend class BTree;

};

 

class BTree {

    BTreeNode* root;

    int t;

public:

    BTree(int _t) {

        root = nullptr;

        t = _t;

    }

    void traverse() {

        if (root != nullptr) root->traverse();

    }

    BTreeNode* search(int k) {

        return (root == nullptr) ? nullptr : root->search(k);

    }

    void insert(int k);

    void remove(int k);

};

 

BTreeNode::BTreeNode(int t1, bool leaf1) {

    t = t1;

    leaf = leaf1;

    keys = new int[2 * t - 1];

    C = new BTreeNode*[2 * t];

    n = 0;

}

 

int BTreeNode::findKey(int k) {

    int idx = 0;

    while (idx < n && keys[idx] < k) ++idx;

    return idx;

}

 

void BTreeNode::remove(int k) {

    int idx = findKey(k);

    if (idx < n && keys[idx] == k) {

        if (leaf) removeFromLeaf(idx);

        else removeFromNonLeaf(idx);

    } else {

        if (leaf) {

            std::cout << "The key " << k << " is not present in the tree.\n";

            return;

        }

        bool flag = (idx == n);

        if (C[idx]->n < t) fill(idx);

        if (flag && idx > n) C[idx - 1]->remove(k);

        else C[idx]->remove(k);

    }

}

 

void BTreeNode::removeFromLeaf(int idx) {

    for (int i = idx + 1; i < n; ++i) keys[i - 1] = keys[i];

    n--;

}

 

void BTreeNode::removeFromNonLeaf(int idx) {

    int k = keys[idx];

    if (C[idx]->n >= t) {

        int pred = getPred(idx);

        keys[idx] = pred;

        C[idx]->remove(pred);

    } else if (C[idx + 1]->n >= t) {

        int succ = getSucc(idx);

        keys[idx] = succ;

        C[idx + 1]->remove(succ);

    } else {

        merge(idx);

        C[idx]->remove(k);

    }

}

 

int BTreeNode::getPred(int idx) {

    BTreeNode* cur = C[idx];

    while (!cur->leaf) cur = cur->C[cur->n];

    return cur->keys[cur->n - 1];

}

 

int BTreeNode::getSucc(int idx) {

    BTreeNode* cur = C[idx + 1];

    while (!cur->leaf) cur = cur->C[0];

    return cur->keys[0];

}

 

void BTreeNode::fill(int idx) {

    if (idx != 0 && C[idx - 1]->n >= t) borrowFromPrev(idx);

    else if (idx != n && C[idx + 1]->n >= t) borrowFromNext(idx);

    else {

        if (idx != n) merge(idx);

        else merge(idx - 1);

    }

}

 

void BTreeNode::borrowFromPrev(int idx) {

    BTreeNode* child = C[idx];

    BTreeNode* sibling = C[idx - 1];

    for (int i = child->n - 1; i >= 0; --i) child->keys[i + 1] = child->keys[i];

    if (!child->leaf) {

        for (int i = child->n; i >= 0; --i) child->C[i + 1] = child->C[i];

    }

    child->keys[0] = keys[idx - 1];

    if (!child->leaf) child->C[0] = sibling->C[sibling->n];

    keys[idx - 1] = sibling->keys[sibling->n - 1];

    child->n += 1;

    sibling->n -= 1;

}

 

void BTreeNode::borrowFromNext(int idx) {

    BTreeNode* child = C[idx];

    BTreeNode* sibling = C[idx + 1];

    child->keys[child->n] = keys[idx];

    if (!child->leaf) child->C[child->n + 1] = sibling->C[0];

    keys[idx] = sibling->keys[0];

    for (int i = 1; i < sibling->n; ++i) sibling->keys[i - 1] = sibling->keys[i];

    if (!sibling->leaf) {

        for (int i = 1; i <= sibling->n; ++i) sibling->C[i - 1] = sibling->C[i];

    }

    child->n += 1;

    sibling->n -= 1;

}

 

void BTreeNode::merge(int idx) {

    BTreeNode* child = C[idx];

    BTreeNode* sibling = C[idx + 1];

    child->keys[t - 1] = keys[idx];

    for (int i = 0; i < sibling->n; ++i) child->keys[i + t] = sibling->keys[i];

    if (!child->leaf) {

        for (int i = 0; i <= sibling->n; ++i) child->C[i + t] = sibling->C[i];

    }

    for (int i = idx + 1; i < n; ++i) keys[i - 1] = keys[i];

    for (int i = idx + 2; i <= n; ++i) C[i - 1] = C[i];

    child->n += sibling->n + 1;

    n--;

    delete sibling;

}

 

void BTreeNode::traverse() {

    int i;

    for (i = 0; i < n; i++) {

        if (leaf == false) C[i]->traverse();

        std::cout << " " << keys[i];

    }

    if (leaf == false) C[i]->traverse();

}

 

BTreeNode* BTreeNode::search(int k) {

    int i = 0;

    while (i < n && k > keys[i]) i++;

    if (keys[i] == k) return this;

    if (leaf == true) return nullptr;

    return C[i]->search(k);

}

 

void BTree::insert(int k) {

    if (root == nullptr) {

        root = new BTreeNode(t, true);

        root->keys[0] = k;  // Insert key

        root->n = 1;  // Update number of keys in root

    } else {

        if (root->n == 2 * t - 1) {

            BTreeNode* newRoot = new BTreeNode(t, false);

            newRoot->C[0] = root;  // Old root becomes child of new root

            newRoot->splitChild(0, root);  // Split the old root

            int i = 0;

            if (newRoot->keys[0] < k) i++;  // Choose the child to insert

            newRoot->C[i]->insertNonFull(k);

            root = newRoot;  // Update root

        } else {

            root->insertNonFull(k);

        }

    }

}

 

void BTreeNode::insertNonFull(int k) {

    int i = n - 1;

    if (leaf) {

        while (i >= 0 && keys[i] > k) {

            keys[i + 1] = keys[i];  // Shift keys to the right

            i--;

        }

        keys[i + 1] = k;  // Insert new key

        n++;  // Increase count of keys

    } else {

        while (i >= 0 && keys[i] > k) i++;

        if (C[i + 1]->n == 2 * t - 1) {  // If the child is full

            splitChild(i + 1, C[i + 1]);

            if (keys[i + 1] < k) i++;  // Determine which child to insert

        }

        C[i + 1]->insertNonFull(k);  // Recur on the child

    }

}

 

int main() {

    BTree t(3);  // A B-Tree with minimum degree 3

 

    t.insert(10);

    t.insert(20);

    t.insert(5);

    t.insert(6);

    t.insert(12);

    t.insert(30);

    t.insert(7);

    t.insert(17);

 

    std::cout << "Traversal of the B-tree is: ";

    t.traverse();

    std::cout << std::endl;

 

    t.remove(6);

    std::cout << "Traversal after deleting 6: ";

    t.traverse();

    std::cout << std::endl;

 

    t.remove(13);  // Attempt to delete a non-existing key

    std::cout << "Traversal after trying to delete 13 (non-existent): ";

    t.traverse();

    std::cout << std::endl;

 

    t.remove(7);

    std::cout << "Traversal after deleting 7: ";

    t.traverse();

    std::cout << std::endl;

 

    t.remove(10);

    std::cout << "Traversal after deleting 10: ";

    t.traverse();

    std::cout << std::endl;

 

    return 0;

}

---

Summary

• Deletion in Trees is essential for maintaining the structure and properties of different types of trees.
• Binary Trees allow for deletion by replacing the node with the deepest node's value.
• Binary Search Trees (BST) require careful handling based on whether the node has zero, one, or two children.
• AVL Trees maintain balance through rotations after deletion.
• B-Trees handle deletion while ensuring that the tree remains balanced and adheres to the B-Tree properties.

Understanding these deletion algorithms is crucial for effectively managing tree data structures in various applications.

 

---