বাইনারি ট্রি বা কিভাবে বাইনারি সার্চ ট্রি প্রস্তুত করবেন

প্রস্তাবনা

এই নিবন্ধটি বাইনারি অনুসন্ধান গাছ সম্পর্কে. আমি সম্প্রতি সম্পর্কে একটি নিবন্ধ লিখেছিলাম হাফম্যান পদ্ধতি দ্বারা ডেটা সংকোচন। সেখানে আমি সত্যিই বাইনারি গাছগুলিতে মনোযোগ দিইনি, কারণ অনুসন্ধান, সন্নিবেশ করা, মুছে ফেলার পদ্ধতিগুলি প্রাসঙ্গিক ছিল না। এখন আমি গাছ সম্পর্কে একটি নিবন্ধ লিখতে সিদ্ধান্ত নিয়েছে. সম্ভবত আমরা শুরু করব।

একটি ট্রি হল একটি ডাটা স্ট্রাকচার যা কিনারা দ্বারা সংযুক্ত নোড নিয়ে গঠিত। আমরা বলতে পারি যে একটি গাছ একটি গ্রাফের একটি বিশেষ ক্ষেত্রে। এখানে একটি উদাহরণ গাছ আছে:

এটি একটি বাইনারি অনুসন্ধান গাছ নয়! সবই তো কাটার নিচে!

পরিভাষা

মূল

গাছের মূল শীর্ষস্থানীয় নোড। উদাহরণে, এটি একটি নোড। আসলে, যেকোনো নোডকে এই নোডের সাথে সম্পর্কিত সাবট্রির মূল হিসাবে বিবেচনা করা যেতে পারে।

পিতামাতা/সন্তান

রুট ব্যতীত সমস্ত নোডের ঠিক এক প্রান্ত থাকে যা অন্য নোড পর্যন্ত যায়। বর্তমান নোডের উপরের নোডকে বলা হয় অভিভাবক এই নোড বর্তমানের নীচে অবস্থিত এবং এটির সাথে সংযুক্ত একটি নোডকে বলা হয় বংশধর এই নোড একটা উদাহরণ নেওয়া যাক। নোড B নিন, তাহলে এর প্যারেন্ট হবে নোড A, এবং এর বাচ্চারা হবে নোড D, E এবং F।

চাদর

যে নোডের কোন সন্তান নেই তাকে গাছের পাতা বলে। উদাহরণে, নোড D, E, F, G, I, J, K পাতা হবে।

এটি মৌলিক পরিভাষা। অন্যান্য ধারণা পরে আলোচনা করা হবে. সুতরাং, একটি বাইনারি গাছ হল একটি গাছ যেখানে প্রতিটি নোডে দুটির বেশি সন্তান থাকবে না। আপনি যেমন অনুমান করেছেন, উদাহরণ থেকে গাছটি বাইনারি হবে না, কারণ নোড B এবং H এর দুটির বেশি সন্তান রয়েছে। এখানে একটি বাইনারি গাছের উদাহরণ রয়েছে:

গাছের নোডগুলিতে যে কোনও তথ্য থাকতে পারে। একটি বাইনারি অনুসন্ধান গাছ হল একটি বাইনারি গাছ যার নিম্নলিখিত বৈশিষ্ট্য রয়েছে:

1. বাম এবং ডান উপবৃক্ষ উভয়ই বাইনারি অনুসন্ধান গাছ।
2. একটি নির্বিচারে নোড X এর বাম সাবট্রির সমস্ত নোডের ডেটা কী মান নোড X এর ডেটা কী মানের চেয়ে কম।
3. একটি নির্বিচারে নোড X-এর ডান সাবট্রির সমস্ত নোডের ডেটা কী মান নোড X-এর ডেটা কী-এর মানের থেকে বেশি বা সমান।

চাবি - নোডের কিছু বৈশিষ্ট্য (উদাহরণস্বরূপ, একটি সংখ্যা)। এই কীটি যে গাছটির সাথে মিলে যায় তার উপাদানটি খুঁজে পেতে সক্ষম হওয়ার জন্য কীটির প্রয়োজন। বাইনারি অনুসন্ধান গাছ উদাহরণ:

গাছ দেখুন

আমি এগিয়ে যাওয়ার সাথে সাথে আপনার বোঝার উন্নতি করার জন্য আমি কিছু (সম্ভবত অসম্পূর্ণ) কোডের টুকরো অন্তর্ভুক্ত করব। সম্পূর্ণ কোড নিবন্ধের শেষে থাকবে।

গাছটি নোড দিয়ে তৈরি। নোড গঠন:

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }
    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }
//...остальные методы узла
}

প্রতিটি নোডের দুটি সন্তান রয়েছে (এটি বেশ সম্ভব যে leftChild এবং/অথবা rightChild শিশুরা শূন্য হবে)। আপনি সম্ভবত বুঝতে পেরেছেন যে এই ক্ষেত্রে সংখ্যা ডেটা হল নোডে সংরক্ষিত ডেটা; কী - নোড কী।

আমরা গিঁটটি বের করেছি, এখন গাছের চাপের সমস্যা সম্পর্কে কথা বলা যাক। এখানে এবং নীচে, "বৃক্ষ" শব্দের অর্থ হবে একটি বাইনারি অনুসন্ধান গাছের ধারণা। বাইনারি গাছের গঠন:

public class BinaryTree<T> {
     private Node<T> root;

    //методы дерева
}

ক্লাস ফিল্ড হিসাবে, আমাদের শুধুমাত্র গাছের মূল প্রয়োজন, কারণ রুট থেকে, getLeftChild() এবং getRightChild() পদ্ধতি ব্যবহার করে, আপনি গাছের যেকোনো নোডে যেতে পারেন।

ট্রি অ্যালগরিদম

Поиск

ধরা যাক আপনার একটি নির্মিত গাছ আছে। কীভাবে কী কী দিয়ে উপাদান খুঁজে পাবেন? আপনাকে ক্রমানুসারে রুট থেকে গাছের নিচে নামতে হবে এবং পরবর্তী নোডের কী-এর সাথে কী-এর মান তুলনা করতে হবে: যদি কী পরবর্তী নোডের কী-এর চেয়ে কম হয়, তাহলে নোডের বাম বংশধরে যান, যদি বেশি হয় - ডানদিকে, যদি কীগুলি সমান হয় - পছন্দসই নোড পাওয়া যায়! প্রাসঙ্গিক কোড:

public Node<T> find(int key) {
    Node<T> current = root;
    while (current.getKey() != key) {
        if (key < current.getKey())
            current = current.getLeftChild();
        else
            current = current.getRightChild();
        if (current == null)
            return null;
    }
    return current;
}

যদি কারেন্ট শূন্য হয়ে যায়, তবে পুনরাবৃত্তি গাছের শেষ প্রান্তে পৌঁছেছে (একটি ধারণাগত স্তরে, আপনি গাছের একটি অস্তিত্বহীন জায়গায় আছেন - একটি পাতার সন্তান)।

একটি সুষম গাছে অনুসন্ধান অ্যালগরিদমের দক্ষতা বিবেচনা করুন (একটি গাছ যেখানে নোডগুলি কম বা বেশি সমানভাবে বিতরণ করা হয়)। তারপরে অনুসন্ধানের দক্ষতা হবে O(log(n)), এবং বেস 2 লগারিদম। দেখুন: যদি একটি ভারসাম্যপূর্ণ গাছে n উপাদান থাকে, তাহলে এর অর্থ হল গাছের log(n) বেস 2 স্তর থাকবে। এবং অনুসন্ধানে, চক্রের এক ধাপের জন্য, আপনি এক স্তর নিচে যান।

ঢোকান

আপনি যদি অনুসন্ধানের সারাংশটি উপলব্ধি করেন তবে সন্নিবেশটি বুঝতে আপনার পক্ষে অসুবিধা হবে না। আপনাকে কেবল গাছের পাতায় যেতে হবে (অনুসন্ধানে বর্ণিত বংশধরের নিয়ম অনুসারে) এবং এর বংশধর হতে হবে - বাম বা ডানে, কীটির উপর নির্ভর করে। বাস্তবায়ন:

   public void insert(T insertData, int key) {
        Node<T> current = root;
        Node<T> parent;
        Node<T> newNode = new Node<>(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

এই ক্ষেত্রে, বর্তমান নোড ছাড়াও, বর্তমান নোডের প্যারেন্ট সম্পর্কে তথ্য সংরক্ষণ করা প্রয়োজন। কারেন্ট নাল হয়ে গেলে, প্যারেন্ট ভেরিয়েবলে আমাদের প্রয়োজনীয় শীট থাকবে।
সন্নিবেশ কার্যকারিতা স্পষ্টতই অনুসন্ধানের মতোই হবে - O(log(n))৷

অপসারণ

মুছে ফেলা হল সবচেয়ে জটিল অপারেশন যা একটি গাছ দিয়ে করতে হবে। এটা স্পষ্ট যে প্রথমে আমরা যে উপাদানটি সরাতে যাচ্ছি তা খুঁজে বের করতে হবে। কিন্তু তারপর কি? যদি আমরা এর রেফারেন্সটি null এ সেট করি, তাহলে আমরা যে সাবট্রির মূল এই নোডটি সে সম্পর্কে তথ্য হারাবো। গাছ অপসারণ পদ্ধতি তিনটি ক্ষেত্রে বিভক্ত করা হয়.

প্রথম মামলা। যে নোডটি সরানো হবে তার কোন সন্তান নেই।

যদি মুছে ফেলা নোডের কোন সন্তান না থাকে, তাহলে এর মানে হল এটি একটি পাতা। অতএব, আপনি কেবলমাত্র এর পিতামাতার leftChild বা rightChild ক্ষেত্রগুলিকে নাল সেট করতে পারেন।

দ্বিতীয় মামলা। যে নোডটি অপসারণ করতে হবে তার একটি সন্তান আছে

এই মামলাটিও খুব কঠিন নয়। আসুন আমাদের উদাহরণে ফিরে যাই। ধরুন আমাদের কী 14 দিয়ে একটি উপাদান মুছে ফেলতে হবে। সম্মত হন যে যেহেতু এটি কী 10-এর সাথে একটি নোডের সঠিক চাইল্ড, তাহলে এর যেকোনো উত্তরসূরির (এই ক্ষেত্রে, ডানটির) 10-এর চেয়ে বড় একটি কী থাকবে, তাই আপনি এটিকে সহজেই গাছ থেকে "কাট" করতে পারে এবং নোডের সন্তানের সাথে সরাসরি অভিভাবককে সংযোগ করতে পারে, যেমন নোডকে 10 কী দিয়ে নোড 13-এর সাথে সংযুক্ত করুন। পরিস্থিতি একই রকম হবে যদি আমাদের একটি নোড মুছে ফেলতে হয় যা তার পিতামাতার বাম সন্তান। নিজের জন্য এটি সম্পর্কে চিন্তা করুন - একটি সঠিক উপমা।

তৃতীয় মামলা। নোডের দুটি সন্তান রয়েছে

সবচেয়ে কঠিন কেস। এর একটি নতুন উদাহরণ কটাক্ষপাত করা যাক.

একজন উত্তরসূরি খুঁজুন

ধরা যাক আমাদের কী দিয়ে নোডটি অপসারণ করতে হবে 25. আমরা এর জায়গায় কাকে রাখব? তার একজন অনুসারী (বংশের বংশধর বা বংশধর) হতে হবে উত্তরাধিকারী(যে মুছে ফেলা নোডের জায়গা নেবে)।

আপনি কিভাবে জানেন যে কে উত্তরাধিকারী হওয়া উচিত? স্বজ্ঞাতভাবে, এটি গাছের নোড যার কীটি নোড থেকে পরবর্তী বৃহত্তম সরানো হচ্ছে। অ্যালগরিদম নিম্নরূপ। আপনাকে তার ডান সন্তানের কাছে যেতে হবে (সর্বদা ডানদিকে, কারণ এটি ইতিমধ্যেই বলা হয়েছিল যে উত্তরাধিকারীর চাবিটি নোডের চাবি মুছে ফেলার চেয়ে বড়), এবং তারপরে এই ডানের বাম শিশুদের চেইনটি দিয়ে যেতে হবে। শিশু উদাহরণে, আমাদের অবশ্যই 35 কী সহ নোডে যেতে হবে এবং তারপরে তার বাম বাচ্চাদের চেইনটি পাতায় যেতে হবে - এই ক্ষেত্রে, এই চেইনটি কেবল 30 কী সহ নোড নিয়ে গঠিত। কঠোরভাবে বলতে গেলে, আমরা খুঁজছি কাঙ্খিত নোডের চেয়ে বড় নোডের সেটে সবচেয়ে ছোট নোড।

উত্তরসূরি অনুসন্ধান পদ্ধতি কোড:

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode;//родитель преемника
        Node<T> successor = deleteNode;//преемник
        Node<T> current = successor.getRightChild();//просто "пробегающий" узел
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        //на выходе из цикла имеем преемника и родителя преемника
        if (successor != deleteNode.getRightChild()) {//если преемник не совпадает с правым потомком удаляемого узла
            parentSuccessor.setLeftChild(successor.getRightChild());//то его родитель забирает себе потомка преемника, чтобы не потерять его
            successor.setRightChild(deleteNode.getRightChild());//связываем преемника с правым потомком удаляемого узла
        }
        return successor;
    }

মুছে ফেলার পদ্ধতির সম্পূর্ণ কোড:

public boolean delete(int deleteKey) {
        Node<T> current = root;
        Node<T> parent = current;
        boolean isLeftChild = false;//В зависимости от того, является ли  удаляемый узел левым или правым потомком своего родителя, булевская переменная isLeftChild будет принимать значение true или false соответственно.
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {//первый случай
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {//второй случай
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {//третий случай
            Node<T> successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

জটিলতা আনুমানিক O(log(n)) হতে পারে।

একটি গাছে সর্বোচ্চ/সর্বনিম্ন খোঁজা

স্পষ্টতই, গাছের সর্বনিম্ন/সর্বোচ্চ মান কীভাবে খুঁজে পাওয়া যায় - আপনাকে ক্রমানুসারে গাছের বাম/ডান উপাদানগুলির শৃঙ্খলের মধ্য দিয়ে যেতে হবে, যথাক্রমে; আপনি যখন পাতায় পৌঁছাবেন, এটি হবে সর্বনিম্ন/সর্বোচ্চ উপাদান।

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

জটিলতা - O(log(n))

সিমেট্রিক বাইপাস

ট্রাভার্সাল হল গাছের প্রতিটি নোডের সাথে কিছু করার জন্য একটি পরিদর্শন।

রিকার্সিভ সিমেট্রিক ট্রাভার্সাল অ্যালগরিদম:

1. বাম সন্তানের উপর একটি কর্ম করুন
2. নিজের সাথে একটি কাজ করুন
3. সঠিক সন্তানের উপর একটি পদক্ষেপ করুন

কোড:

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Здесь может быть все, что угодно
            inOrder(current.getRightChild());
        }
    }

উপসংহার

অবশেষে ! যদি আমি কিছু ব্যাখ্যা না করি বা কোনো মন্তব্য না করি, তাহলে আমি মন্তব্যের জন্য অপেক্ষা করছি। প্রতিশ্রুতি অনুযায়ী, এখানে সম্পূর্ণ কোড আছে।

Node.java:

public class Node<T> {
    private T data;
    private int key;
    private Node<T> leftChild;
    private Node<T> rightChild;

    public Node(T data, int key) {
        this.data = data;
        this.key = key;
    }

    public void setLeftChild(Node<T> newNode) {
        leftChild = newNode;
    }

    public void setRightChild(Node<T> newNode) {
        rightChild = newNode;
    }

    public Node<T> getLeftChild() {
        return leftChild;
    }

    public Node<T> getRightChild() {
        return rightChild;
    }

    public T getData() {
        return data;
    }

    public int getKey() {
        return key;
    }
}

BinaryTree.java:

public class BinaryTree<T> {
    private Node<T> root;

    public Node<T> find(int key) {
        Node<T> current = root;
        while (current.getKey() != key) {
            if (key < current.getKey())
                current = current.getLeftChild();
            else
                current = current.getRightChild();
            if (current == null)
                return null;
        }
        return current;
    }

    public void insert(T insertData, int key) {
        Node<T> current = root;
        Node<T> parent;
        Node<T> newNode = new Node<>(insertData, key);
        if (root == null)
            root = newNode;
        else {
            while (true) {
                parent = current;
                if (key < current.getKey()) {
                    current = current.getLeftChild();
                    if (current == null) {
                         parent.setLeftChild(newNode);
                         return;
                    }
                }
                else {
                    current = current.getRightChild();
                    if (current == null) {
                        parent.setRightChild(newNode);
                        return;
                    }
                }
            }
        }
    }

    public Node<T> getMinimum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node<T> getMaximum(Node<T> startPoint) {
        Node<T> current = startPoint;
        Node<T> parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode;
        Node<T> successor = deleteNode;
        Node<T> current = successor.getRightChild();
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }

        if (successor != deleteNode.getRightChild()) {
            parentSuccessor.setLeftChild(successor.getRightChild());
            successor.setRightChild(deleteNode.getRightChild());
        }
        return successor;
    }

    public boolean delete(int deleteKey) {
        Node<T> current = root;
        Node<T> parent = current;
        boolean isLeftChild = false;
        while (current.getKey() != deleteKey) {
            parent = current;
            if (deleteKey < current.getKey()) {
                current = current.getLeftChild();
                isLeftChild = true;
            } else {
                isLeftChild = false;
                current = current.getRightChild();
            }
            if (current == null)
                return false;
        }

        if (current.getLeftChild() == null && current.getRightChild() == null) {
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) {
            if (current == root)
                root = current.getLeftChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getLeftChild());
            else
                current.setRightChild(current.getLeftChild());
        } else if (current.getLeftChild() == null) {
            if (current == root)
                root = current.getRightChild();
            else if (isLeftChild)
                parent.setLeftChild(current.getRightChild());
            else
                parent.setRightChild(current.getRightChild());
        } 
        else {
            Node<T> successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");
            inOrder(current.getRightChild());
        }
    }
}

দ্রষ্টব্য

O(n) এর অবক্ষয়

আপনারা অনেকেই হয়তো লক্ষ্য করেছেন: গাছকে ভারসাম্যহীন করে দিলে কী হবে? উদাহরণস্বরূপ, ক্রমবর্ধমান কীগুলির সাথে গাছে নোডগুলি রাখুন: 1,2,3,4,5,6... তারপর গাছটি কিছুটা লিঙ্কযুক্ত তালিকার স্মরণ করিয়ে দেবে। এবং হ্যাঁ, গাছটি তার গাছের গঠন হারাবে, এবং তাই ডেটা অ্যাক্সেসের দক্ষতা। অনুসন্ধান, সন্নিবেশ, এবং মুছে ফেলার ক্রিয়াকলাপগুলির জটিলতা একটি লিঙ্কযুক্ত তালিকার মতোই হয়ে যাবে: O(n)। এটি সবচেয়ে গুরুত্বপূর্ণ এক, আমার মতে, বাইনারি গাছের অসুবিধা।

শুধুমাত্র নিবন্ধিত ব্যবহারকারীরা জরিপে অংশগ্রহণ করতে পারবেন। সাইন ইন করুনকরুন।

আমি অনেক দিন ধরে হ্যাব্রে ছিলাম না, এবং আমি জানতে চাই যে আপনি কোন বিষয়ে আরও দেখতে চান?

• উপাত্ত কাঠামো

• অ্যালগরিদম (DP, recursion, data কম্প্রেশন, ইত্যাদি)

• বাস্তব জীবনে ডেটা স্ট্রাকচার এবং অ্যালগরিদমের প্রয়োগ

• জাভাতে অ্যান্ড্রয়েড অ্যাপ্লিকেশন প্রোগ্রামিং

• জাভা ওয়েব অ্যাপ্লিকেশন প্রোগ্রামিং

2 ব্যবহারকারী ভোট দিয়েছেন। ১ জন ব্যবহারকারী বিরত ছিলেন।

সূত্র: www.habr.com