আমরা BST-এ রিকার্শিভভাবে নতুন নোড ইনসার্ট করতে পারি। সেক্ষেত্রে প্রতিটি সাবট্রির রুটের অ্যাড্রেস রিটার্ন করা হয়। এখানে আমরা অন্য একটি অ্যাপ্রোচ দেখব, যেখানে প্যারেন্ট পয়েন্টার মেইন্টেইন করতে হবে। প্যারেন্ট পয়েন্টার একটি নোডের আনসেস্টর খুঁজে বের করতে সাহায্য করে।
আইডিয়া হলো লেফট এবং রাইট সাবট্রির অ্যাড্রেস সংরক্ষণ করা, আমরা রিকার্শিভ কলের পর রিটার্ন করা পয়েন্টারগুলোর প্যারেন্ট পয়েন্টার সেট করি। এটি নিশ্চিত করে যে ইনসার্শনের সময় সব প্যারেন্ট পয়েন্টার সেট হয়েছে। রুটের প্যারেন্ট NULL সেট করা হয়।
অ্যালগরিদম
insert(node, key) −
begin if node is null, then create a new node and return if the key is less than the key of node, then create a new node with key add the new node with the left pointer or node else if key is greater or equal to the key of node, then create a new node with key add the new node at the right pointer of the node end if return node end
উদাহরণ
#include<iostream> using namespace std; class Node { public: int data; Node *left, *right, *parent; }; struct Node *getNode(int item) { Node *temp = new Node; temp->data = item; temp->left = temp->right = temp->parent = NULL; return temp; } void inorderTraverse(struct Node *root) { if (root != NULL) { inorderTraverse(root->left); cout << root->data << " "; if (root->parent == NULL) cout << "NULL" << endl; else cout << root->parent->data << endl; inorderTraverse(root->right); } } struct Node* insert(struct Node* node, int key) { if (node == NULL) return getNode(key); if (key < node->data) { //to the left subtree Node *left_child = insert(node->left, key); node->left = left_child; left_child->parent = node; } else if (key > node->data) { // to the right subtree Node *right_child = insert(node->right, key); node->right = right_child; right_child->parent = node; } return node; } int main() { struct Node *root = NULL; root = insert(root, 100); insert(root, 60); insert(root, 40); insert(root, 80); insert(root, 140); insert(root, 120); insert(root, 160); inorderTraverse(root); }
আউটপুট
40 60 60 100 80 60 100 NULL 120 140 140 100 160 140
