Binary Tree এবং Binary Search Tree (BST) এর ধারণা গাইড ও নোট

1. Binary Tree

Binary Tree হল একটি বিশেষ ধরনের ডেটা স্ট্রাকচার যা প্রতি নোডে সর্বাধিক দুটি চাইল্ড (পুত্র) নোড ধারণ করতে পারে। এটি একটি হায়ারার্কিকাল ডেটা স্ট্রাকচার, যেখানে একটি রুট (root) নোড থাকে এবং প্রতিটি নোডের দুটি সাপোর্টিং নোড থাকতে পারে: লেফট চাইল্ড (left child) এবং রাইট চাইল্ড (right child)।

Binary Tree এর মূল উপাদান:

• Root: মূল নোড যেখানে থেকে বৃক্ষটি শুরু হয়।
• Parent Node: যে নোডের একটি বা দুটি চাইল্ড নোড থাকে।
• Child Node: একটি পিতার অধীনে থাকা নোড, যা লেফট বা রাইট চাইল্ড হতে পারে।
• Leaf Node: একটি নোড যার কোন চাইল্ড নেই।
• Subtree: একটি নোড এবং তার সমস্ত ডেসেনডেন্টরা মিলে একটি সাবট্রি তৈরি করে।

Binary Tree এর কাঠামো:

class Node {
    int data;
    Node left, right;

    public Node(int data) {
        this.data = data;
        left = right = null;
    }
}

public class BinaryTree {
    Node root;

    public BinaryTree() {
        root = null;
    }

    // Inorder Traversal
    public void inorderTraversal(Node node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        System.out.print(node.data + " ");
        inorderTraversal(node.right);
    }

    public static void main(String[] args) {
        BinaryTree tree = new BinaryTree();
        tree.root = new Node(1);
        tree.root.left = new Node(2);
        tree.root.right = new Node(3);
        tree.root.left.left = new Node(4);
        tree.root.left.right = new Node(5);

        System.out.println("Inorder Traversal of Binary Tree:");
        tree.inorderTraversal(tree.root); // Output: 4 2 5 1 3
    }
}

ব্যাখ্যা:

• এখানে, একটি সাধারণ Binary Tree তৈরি করা হয়েছে যেখানে প্রতিটি নোডে একটি ডেটা এবং দুটি চাইল্ড (left এবং right) রয়েছে।
• inorderTraversal একটি জনপ্রিয় ট্রাভার্সাল মেথড যা বৃক্ষের নোডগুলো in-order সিকোয়েন্সে প্রদর্শন করে (লেফট, রুট, রাইট)।

2. Binary Search Tree (BST)

Binary Search Tree (BST) হল একটি বিশেষ ধরনের Binary Tree যেখানে প্রতিটি নোডের একটি নির্দিষ্ট সিকোয়েন্স থাকে:

• প্রতিটি নোডের বাম চাইল্ড এর মান ঐ নোডের মানের চেয়ে কম।
• প্রতিটি নোডের ডান চাইল্ড এর মান ঐ নোডের মানের চেয়ে বেশি।

BST একটি সার্চ অপটিমাইজড ট্রী যা ডেটা ইনসার্ট এবং সার্চ অপারেশনকে দ্রুত করতে সাহায্য করে, কারণ প্রতিটি নোডে একটি নির্দিষ্ট সিকোয়েন্স থাকে।

BST এর প্রধান অপারেশন:

• Insertion: নতুন মান যোগ করা।
• Deletion: একটি নোড মুছে ফেলা।
• Search: একটি নির্দিষ্ট মান খোঁজা।
• Traversal: বৃক্ষের নোডগুলো ভিজিট করা (ইন-অর্ডার, প্রি-অর্ডার, পোস্ট-অর্ডার)।

BST এর কাঠামো:

class BSTNode {
    int data;
    BSTNode left, right;

    public BSTNode(int data) {
        this.data = data;
        left = right = null;
    }
}

public class BinarySearchTree {
    BSTNode root;

    public BinarySearchTree() {
        root = null;
    }

    // Insert a node in BST
    public void insert(int data) {
        root = insertRec(root, data);
    }

    private BSTNode insertRec(BSTNode root, int data) {
        if (root == null) {
            root = new BSTNode(data);
            return root;
        }

        if (data < root.data) {
            root.left = insertRec(root.left, data);
        } else if (data > root.data) {
            root.right = insertRec(root.right, data);
        }

        return root;
    }

    // Inorder Traversal
    public void inorderTraversal(BSTNode node) {
        if (node == null) {
            return;
        }
        inorderTraversal(node.left);
        System.out.print(node.data + " ");
        inorderTraversal(node.right);
    }

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();
        tree.insert(50);
        tree.insert(30);
        tree.insert(20);
        tree.insert(40);
        tree.insert(70);
        tree.insert(60);
        tree.insert(80);

        System.out.println("Inorder Traversal of Binary Search Tree:");
        tree.inorderTraversal(tree.root);  // Output: 20 30 40 50 60 70 80
    }
}

ব্যাখ্যা:

• insert: একটি নতুন মান BST-তে যোগ করার জন্য এই মেথডটি ব্যবহৃত হয়। প্রতিটি নতুন নোড সংযোজনের সময়, BST নিয়ম অনুসরণ করে সঠিক স্থানে যোগ করা হয়।
• inorderTraversal: inorder ট্রাভার্সাল মেথডটি BST-তে গঠিত নোডগুলো ইন-অর্ডারে প্রদর্শন করে, যা BST এ সজ্জিত ডেটাকে সঠিকভাবে ক্রমানুসারে প্রদর্শন করে।

3. Binary Tree এবং Binary Search Tree এর পার্থক্য

4. Binary Tree এবং BST এর ব্যবহারিক প্রয়োগ

• Binary Tree:
  • হিয়ারার্কিক্যাল ডেটা: ফাইল সিস্টেমের গঠন বা বিভাগীয় কাঠামো।
  • অ্যালগরিদমে ব্যবহার: হাফ (heap) বা প্রিভিউ কাঠামো (priority queue) গঠন করতে।
• Binary Search Tree (BST):
  • ডেটা অনুসন্ধান: দ্রুত ডেটা অনুসন্ধান এবং সন্নিবেশ জন্য।
  • ডেটা অর্গানাইজেশন: মেমরি ব্যবস্থাপনা এবং ডেটা ফিল্টারিংয়ের জন্য।
  • পরিসংখ্যান বিশ্লেষণ: ডেটা সেটের ট্রেন্ড, পরিসংখ্যান বা সঠিক মান খোঁজা।

সারাংশ

Binary Tree এবং Binary Search Tree (BST) হল গাছের (tree) দুই ধরনের জনপ্রিয় ডেটা স্ট্রাকচার। Binary Tree একটি সাধারণ গঠন যেখানে প্রতিটি নোডের দুটি চাইল্ড থাকে এবং এটি সাধারণত ট্রাভার্সাল অপারেশনগুলিতে ব্যবহৃত হয়। অন্যদিকে, Binary Search Tree (BST) একটি বিশেষ ধরনের বাইনারি ট্রি যা ডেটাকে সঠিকভাবে সাজিয়ে রাখে, যা সার্চ এবং সন্নিবেশ অপারেশনগুলিকে কার্যকরী এবং দ্রুত করে তোলে। DBMS, গেম ডেভেলপমেন্ট, ইন্টারনেট সার্চ ইঞ্জিন এবং বিভিন্ন অ্যালগরিদমে এই ডেটা স্ট্রাকচার দুটি গুরুত্বপূর্ণ ভূমিকা পালন করে।