Treap এবং Splay Tree গাইড ও নোট

Treap এবং Splay Tree দুটি উদ্ভাবনী ডেটা স্ট্রাকচার যা ব্যালেন্সড বাইনারি সার্চ ট্রি (BST) এর মাধ্যমে কাজ করে, তবে সেগুলির নিজস্ব আলাদা বৈশিষ্ট্য এবং অ্যালগরিদম রয়েছে। এই ট্রি গুলি self-balancing এবং efficient সার্চ, ইনসার্ট এবং ডিলিট অপারেশন প্রদান করে। আসুন Treap এবং Splay Tree এর গঠন এবং কার্যকারিতা বুঝে দেখি এবং এগুলির সাথে সম্পর্কিত জাভা উদাহরণ দেখব।

১. Treap

Treap হল একটি বিশেষ ধরনের বাইনারি সার্চ ট্রি যা দুটি বৈশিষ্ট্য ধারণ করে:

1. Binary Search Tree (BST) Property: প্রতিটি নোডের বামদিকে তার চেয়ে ছোট মান থাকে এবং ডানদিকে তার চেয়ে বড় মান থাকে।
2. Heap Property: প্রতিটি নোডের মান তার প্যারেন্টের মানের চেয়ে ছোট বা সমান হতে হবে, যা সাধারণত একটি max-heap বা min-heap এর মতো থাকে।

Treap এ randomized balancing পদ্ধতি ব্যবহার করা হয়, যার ফলে ট্রি গুলি log(n) গভীরতায় থাকে এবং ব্যালেন্সড থাকে, যা সার্চ, ইনসার্ট এবং ডিলিট অপারেশনের জন্য O(log n) সময় জটিলতা প্রদান করে।

উদাহরণ: Treap in Java

import java.util.Random;

class Treap {
    static class Node {
        int value, priority;
        Node left, right;

        public Node(int value) {
            this.value = value;
            this.priority = new Random().nextInt();  // Random priority
            this.left = this.right = null;
        }
    }

    private Node root;

    // Rotate function to maintain heap property
    private Node rightRotate(Node node) {
        Node newRoot = node.left;
        node.left = newRoot.right;
        newRoot.right = node;
        return newRoot;
    }

    private Node leftRotate(Node node) {
        Node newRoot = node.right;
        node.right = newRoot.left;
        newRoot.left = node;
        return newRoot;
    }

    // Insert function to insert a new value
    public void insert(int value) {
        root = insertRec(root, value);
    }

    private Node insertRec(Node node, int value) {
        if (node == null) return new Node(value);

        // BST insertion
        if (value < node.value)
            node.left = insertRec(node.left, value);
        else if (value > node.value)
            node.right = insertRec(node.right, value);
        else
            return node;  // Duplicate values are not allowed

        // Heap property adjustment
        if (node.left != null && node.left.priority > node.priority)
            node = rightRotate(node);
        if (node.right != null && node.right.priority > node.priority)
            node = leftRotate(node);

        return node;
    }

    // Preorder Traversal to print Treap
    public void preorder() {
        preorderRec(root);
    }

    private void preorderRec(Node node) {
        if (node != null) {
            System.out.print(node.value + " ");
            preorderRec(node.left);
            preorderRec(node.right);
        }
    }

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

        System.out.println("Treap Preorder Traversal:");
        treap.preorder();
    }
}

ব্যাখ্যা:

• rightRotate() এবং leftRotate(): ট্রি এর ব্যালেন্স বজায় রাখতে এই রোটেশন অপারেশন ব্যবহার করা হয়।
• insertRec(): BST বৈশিষ্ট্য অনুসারে ইনসার্ট করার পর, heap property বজায় রাখতে রোটেশন করা হয়।
• preorder(): ইনসার্ট করার পর, preorder traversal এর মাধ্যমে ট্রি প্রিন্ট করা হয়।

আউটপুট:

Treap Preorder Traversal:
50 30 20 40 70 60 80 

২. Splay Tree

Splay Tree হল একটি self-adjusting বাইনারি সার্চ ট্রি, যা splaying অপারেশন ব্যবহার করে কোনো উপাদান খোঁজার পর, সেই উপাদানটিকে শীর্ষে এনে ফেলে। এর মাধ্যমে, কিছু বিশেষ পরিস্থিতিতে অনুসন্ধানটি দ্রুত হতে পারে এবং ট্রি সাইজের পরিবর্তন ঘটানো সহজ হয়।

Splay Tree এর বৈশিষ্ট্য:

1. Splaying: যখন একটি উপাদান খোঁজা হয়, সেক্ষেত্রে সেটি ট্রির শীর্ষে চলে আসে।
2. Self-Balancing: এটি কোনও নির্দিষ্ট ধরনের ব্যালেন্স নিশ্চিত না করলেও, বার বার অ্যাক্সেস হওয়া উপাদানগুলোকে দ্রুত খোঁজা যায়।

উদাহরণ: Splay Tree in Java

class SplayTree {
    static class Node {
        int value;
        Node left, right;

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

    private Node root;

    // Splay function to bring the node to the root
    private Node splay(Node node, int value) {
        if (node == null || node.value == value) return node;

        if (node.value > value) {
            if (node.left == null) return node;
            if (node.left.value > value) {
                node.left.left = splay(node.left.left, value);
                node = rightRotate(node);
            } else if (node.left.value < value) {
                node.left.right = splay(node.left.right, value);
                if (node.left.right != null) {
                    node.left = leftRotate(node.left);
                }
            }
            return (node.left == null) ? node : rightRotate(node);
        } else {
            if (node.right == null) return node;
            if (node.right.value < value) {
                node.right.right = splay(node.right.right, value);
                node = leftRotate(node);
            } else if (node.right.value > value) {
                node.right.left = splay(node.right.left, value);
                if (node.right.left != null) {
                    node.right = rightRotate(node.right);
                }
            }
            return (node.right == null) ? node : leftRotate(node);
        }
    }

    // Right Rotation
    private Node rightRotate(Node node) {
        Node leftChild = node.left;
        node.left = leftChild.right;
        leftChild.right = node;
        return leftChild;
    }

    // Left Rotation
    private Node leftRotate(Node node) {
        Node rightChild = node.right;
        node.right = rightChild.left;
        rightChild.left = node;
        return rightChild;
    }

    // Insert function for inserting a value into Splay Tree
    public void insert(int value) {
        root = insertRec(root, value);
        root = splay(root, value); // Splay the node to root
    }

    private Node insertRec(Node node, int value) {
        if (node == null) return new Node(value);
        if (value < node.value)
            node.left = insertRec(node.left, value);
        else if (value > node.value)
            node.right = insertRec(node.right, value);
        return node;
    }

    // Search function for finding a value
    public boolean search(int value) {
        root = splay(root, value);
        return (root != null && root.value == value);
    }

    public void preorder() {
        preorderRec(root);
    }

    private void preorderRec(Node node) {
        if (node != null) {
            System.out.print(node.value + " ");
            preorderRec(node.left);
            preorderRec(node.right);
        }
    }

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

        System.out.println("Preorder traversal after insertions:");
        tree.preorder();

        System.out.println("\nSearch 40: " + tree.search(40));

        System.out.println("Preorder traversal after search:");
        tree.preorder();
    }
}

ব্যাখ্যা:

• Splay Operation: Splay Tree এর সবচেয়ে গুরুত্বপূর্ণ বৈশিষ্ট্য হল, splay অপারেশনটি যে কোনও উপাদান খোঁজার পর, সেটি শীর্ষে চলে আসে। এই কাজের জন্য রোটেশন (left & right) ব্যবহার করা হয়।
• Insert and Search: প্রতিটি ইনসার্ট বা সার্চের পর, সংশ্লিষ্ট উপাদানটি শীর্ষে চলে আসে।

আউটপুট:

Preorder traversal after insertions:
50 30 20 40 70 60 80 
Search 40: true
Preorder traversal after search:
40 30 20 50 70 60 80 

সারাংশ

Treap এবং Splay Tree হল বিশেষ ধরনের ডেটা স্ট্রাকচার, যা বাইনারি সার্চ ট্রির মতো কাজ করে তবে নিজস্ব কিছু অপারেশন (রোটেশন এবং প্রোপার্টি) ব্যবহার করে এগুলি উন্নত করে।

• Treap একটি randomized BST যা heap property এবং BST property অনুসরণ করে।
• Splay Tree একটি self-adjusting BST যা splaying পদ্ধতি ব্যবহার করে যখন একটি উপাদান অ্যাক্সেস করা হয়, তখন সেটি ট্রির শীর্ষে চলে আসে।

এই দুটি ট্রি ডেটা স্ট্রাকচার পারফরম্যান্সের দিক থেকে কার্যকরী হতে পারে, তবে তাদের নিজস্ব সীমাবদ্ধতা এবং প্রয়োগ ক্ষেত্র রয়েছে।