ট্রি ডেটা স্ট্রাকচার
একটি ট্রি হচ্ছে কিছু নোডের সংগ্রহ যা এজ দিয়ে সংযুক্ত। প্রতিটি নোড কিছু ডেটা এবং তার চাইল্ড রেফারেন্স ধারণ করে।
বাইনারি সার্চ ট্রি
বাইনারি সার্চ ট্রি হচ্ছে একটি বাইনারি ট্রি যেখানে কম মান वाले নোডগুলো বামে এবং বেশি মান والے নোডগুলো ডানে থাকে।
উদাহরণস্বরূপ, একটি বৈধ BST-এর ভিজুয়াল রিপ্রেজেন্টেশন:
25 / \ 20 36 / \ / \ 10 22 30 40
এখন জাভাস্ক্রিপ্টে আমাদের নিজস্ব বাইনারি সার্চ ট্রি বাস্তবায়ন করি।
ধাপ ১: Node ক্লাস
এই ক্লাসটি BST-র বিভিন্ন পয়েন্টে থাকা একটি একক নোডকে রিপ্রেজেন্ট করে।
class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; }; }; নতুন Node ইনস্ট্যান্স তৈরি করতে:
const newNode = new Node(23);
এটি ডেটা ২৩ সহ একটি নোড তৈরি করবে যেখানে left এবং right রেফারেন্স null থাকবে।
ধাপ ২: BinarySearchTree ক্লাস
class BinarySearchTree{ constructor(){ this.root = null; }; }; এটি BST ক্লাস তৈরি করে যা new কিওয়ার্ড দিয়ে কল করলে ট্রি ইনস্ট্যান্স বানাবে।
ধাপ ৩: BST-এ নোড ইনসার্ট করা
class BinarySearchTree{ constructor(){ this.root = null; } insert(data){ var newNode = new Node(data); if(this.root === null){ this.root = newNode; }else{ this.insertNode(this.root, newNode); }; }; insertNode(node, newNode){ if(newNode.data < node.data){ if(node.left === null){ node.left = newNode; }else{ this.insertNode(node.left, newNode); }; } else { if(node.right === null){ node.right = newNode; }else{ this.insertNode(node.right,newNode); }; }; }; }; উদাহরণ
পূর্ণ বাইনারি সার্চ ট্রি কোড:
class Node{ constructor(data) { this.data = data; this.left = null; this.right = null; }; }; class BinarySearchTree{ constructor(){ this.root = null; } insert(data){ var newNode = new Node(data); if(this.root === null){ this.root = newNode; }else{ this.insertNode(this.root, newNode); }; }; insertNode(node, newNode){ if(newNode.data < node.data){ if(node.left === null){ node.left = newNode; }else{ this.insertNode(node.left, newNode); }; } else { if(node.right === null){ node.right = newNode; }else{ this.insertNode(node.right,newNode); }; }; }; }; const BST = new BinarySearchTree(); BST.insert(1); BST.insert(3); BST.insert(2); 