সি++-এ বাইনারি ট্রিতে ডিলিশন (Deletion)

ডিলিশন করা হবে ডিলিট করা নোডকে বটম এবং রাইটমোস্ট নোড দিয়ে রিপ্লেস করে।

প্রথমে স্ট্রাক্ট ডিফাইন করি যা ট্রি নোড রিপ্রেজেন্ট করবে যাতে ডেটা এবং এর বাম ও ডান চাইল্ড নোড থাকে। যদি এটি প্রথম নোড হয় তবে এটি রুট নোড হবে অন্যথায় চাইল্ড নোড।

struct Node { 
    int data; 
    struct Node *leftChild, *rightChild; 
};

পরবর্তীতে newNode(int data) ফাংশন তৈরি করি যা একটি int মান নেয় এবং সেটি নোডের ডেটা মেম্বরে অ্যাসাইন করে। ফাংশনটি তৈরি হওয়া struct Node-এর পয়েন্টার ফেরত দেয়। এছাড়া নতুন নোডের বাম ও ডান চাইল্ড নাল সেট করা হয়।

struct Node* newNode(int data){ 
    struct Node* newNode = new Node; 
    newNode->data = data; 
    newNode->leftChild = newNode->rightChild = NULL; 
    return (newNode); 
}

deletion(struct Node* root, int data) ফাংশন দেওয়া ডেটা ভ্যালুওয়ালা নোড ডিলিট করতে ব্যবহৃত হয়। এটি রুট নোড এবং সার্চ ও ডিলিট করার ডেটা মান নেয়। যদি কোনো চাইল্ড নোড নেই এবং ডেটা মান রুটের ডেটা মানের সমান হয় তবে NULL ফেরত দেয় অন্যথায় রুট নোড ফেরত দেয়।

Node* deletion(struct Node* root, int data){ 
    if (root == NULL) 
        return NULL; 
    if (root->leftChild == NULL && root->rightChild == NULL) { 
        if (root->data == data) 
            return NULL; 
        else 
            return root; 
    }

এখন struct Node * টাইপের একটি কিউ q তৈরি করি এবং রুট নোড q-তে পুশ করি। আমরা temp এবং data_node ডিক্লেয়ার করি যারা Node-এর পয়েন্টার এবং data_node কে NULL সেট করা হয়।

struct Node* temp; 
struct Node* data_node = NULL;

পরবর্তীতে, লেভেল অর্ডার ট্রাভার্সাল করি সবচেয়ে গভীর নোড বের করতে। হয়ে যাওয়া পর্যন্ত while লুপ চলে। কিউ FIFO ডেটা স্ট্রাকচার তাই কিউয়ের লাস্ট এলিমেন্ট হবে রাইটমোস্ট ডিপেস্ট নোড যেহেতু আমরা লেভেল অর্ডার ট্রাভার্সাল করছি। temp সবসময় কিউয়ের ফ্রন্টে পয়েন্ট করে এবং এলিমেন্টগুলো ফ্রন্ট থেকে পপ করা হয়।

while (!q.empty()) { 
    temp = q.front(); 
    q.pop(); 
    if (temp->data == data) 
        data_node = temp; 
    if (temp->leftChild) 
        q.push(temp->leftChild); 
    if (temp->rightChild) 
        q.push(temp->rightChild); 
}

পরবর্তীতে যদি data_node NULL না হয় তবে ডিলিট হোনোর নোডের ডেটা x-এ স্ট্রোর করি এবং ডিপেস্ট নোড যা temp সেটি ডিলিট করি। data_node-এর মান ডিপেস্ট নোডের মান দিয়ে রিপ্লেস করা হয় এবং ডিপেস্ট নোড ডিলিট করা হয়। ডিলিশন ও রিপ্লেসমেন্টের পর নতুন নোড ফাংশন থেকে ফেরত দেওয়া হয়।

if (data_node != NULL) { 
    int x = temp->data; 
    deleteDeepest(root, temp); 
    data_node->data = x; 
}

deleteDeepest(struct Node* root, struct Node* deepestNode) ফাংশন চেক করে পাস করা নোড কি আসলে ডিপেস্ট নোড নাকি এর ডান বা বাম চাইল্ড ডিপেস্ট নোড যাতে প্যারেন্ট যেটি ডিপেস্ট নোড সেটিকে নাল সেট করে ডিলিট করার আগে।

void deleteDeepest(struct Node* root, 
    struct Node* deepestNode){ 
    queue<struct Node*> q; 
    q.push(root); 
    struct Node* temp; 
    while (!q.empty()) { 
        temp = q.front(); 
        q.pop(); 
        if (temp == deepestNode) { 
            temp = NULL; 
            delete (deepestNode); 
            return; 
        } 
        if (temp->rightChild) { 
            if (temp->rightChild == deepestNode) { 
                temp->rightChild = NULL; 
                delete (deepestNode); 
                return; 
            } 
            else 
                q.push(temp->rightChild); 
        } 
        if (temp->leftChild) { 
            if (temp->leftChild == deepestNode) { 
                temp->leftChild = NULL; 
                delete (deepestNode); 
                return; 
            } 
            else 
                q.push(temp->leftChild); 
        } 
    } 
}

উদাহরণ

বাইনারি ট্রিতে ডিলিশন দেখার ইমপ্লিমেন্টেশন:

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

struct Node { 
    int data; 
    struct Node *leftChild, *rightChild; 
}; 

struct Node* NewNode(int data){ 
    struct Node* temp = new Node; 
    temp->data = data; 
    temp->leftChild = temp->rightChild = NULL; 
    return temp; 
}; 

void inorder(struct Node* temp){ 
    if (!temp) 
        return; 
    inorder(temp->leftChild); 
    cout << temp->data << " "; 
    inorder(temp->rightChild); 
} 

void deleteDeepest(struct Node* root, 
    struct Node* deepestNode){ 
    queue<struct Node*> q; 
    q.push(root); 
    struct Node* temp; 
    while (!q.empty()) { 
        temp = q.front(); 
        q.pop(); 
        if (temp == deepestNode) { 
            temp = NULL; 
            delete (deepestNode); 
            return; 
        } 
        if (temp->rightChild) { 
            if (temp->rightChild == deepestNode) { 
                temp->rightChild = NULL; 
                delete (deepestNode); 
                return; 
            } 
            else 
                q.push(temp->rightChild); 
        } 
        if (temp->leftChild) { 
            if (temp->leftChild == deepestNode) { 
                temp->leftChild = NULL; 
                delete (deepestNode); 
                return; 
            } 
            else 
                q.push(temp->leftChild); 
        } 
    } 
} 

Node* deletion(struct Node* root, int data){ 
    if (root == NULL) 
        return NULL; 
    if (root->leftChild == NULL && root->rightChild == NULL) { 
        if (root->data == data) 
            return NULL; 
        else 
            return root; 
    } 
    queue<struct Node*> q; 
    q.push(root); 
    struct Node* temp; 
    struct Node* data_node = NULL; 
    while (!q.empty()) { 
        temp = q.front(); 
        q.pop(); 
        if (temp->data == data) 
            data_node = temp; 
        if (temp->leftChild) 
            q.push(temp->leftChild); 
        if (temp->rightChild) 
            q.push(temp->rightChild); 
    } 
    if (data_node != NULL) { 
        int x = temp->data; 
        deleteDeepest(root,temp); 
        data_node->data = x; 
    } 
    return root; 
} 

// Driver code 
int main(){ 
    struct Node* root = NewNode(12); 
    root->leftChild = NewNode(13); 
    root->leftChild->leftChild = NewNode(9); 
    root->leftChild->rightChild = NewNode(14); 
    root->rightChild = NewNode(11); 
    root->rightChild->leftChild = NewNode(17); 
    root->rightChild->rightChild = NewNode(10); 
    cout << "Inorder traversal before deletion : "; 
    inorder(root); 
    int data = 13; 
    root = deletion(root, data); 
    cout << endl << "Inorder traversal after deletion : "; 
    inorder(root); 
    return 0; 
}

আউটপুট

Inorder traversal before deletion : 9 13 14 12 17 11 10 Inorder traversal after deletion : 9 10 14 12 17 11