बाइनरी ट्री या बाइनरी सर्च ट्री कैसे तैयार करें

प्रस्तावना

यह लेख बाइनरी सर्च ट्री के बारे में है। मैंने हाल ही में इसके बारे में एक लेख लिखा है हफ़मैन विधि द्वारा डेटा संपीड़न। वहां मैंने वास्तव में बाइनरी ट्री पर ध्यान नहीं दिया, क्योंकि खोजने, डालने, हटाने के तरीके प्रासंगिक नहीं थे। अब मैंने पेड़ों के बारे में एक लेख लिखने का फैसला किया। शायद हम शुरू करेंगे.

ट्री एक डेटा संरचना है जिसमें किनारों से जुड़े नोड्स होते हैं। हम कह सकते हैं कि पेड़ ग्राफ़ का एक विशेष मामला है। यहाँ एक उदाहरण वृक्ष है:

यह कोई बाइनरी सर्च ट्री नहीं है! सब कुछ कटौती के अधीन है!

शब्दावली

जड़

पेड़ की जड़ सबसे ऊपरी नोड है. उदाहरण में, यह नोड ए है। पेड़ में, केवल एक पथ जड़ से किसी अन्य नोड तक जा सकता है! वास्तव में, किसी भी नोड को इस नोड के अनुरूप उपट्री की जड़ के रूप में माना जा सकता है।

माता-पिता/संतान

रूट को छोड़कर सभी नोड्स में बिल्कुल एक किनारा होता है जो दूसरे नोड तक जाता है। वर्तमान नोड के ऊपर के नोड को कहा जाता है माता-पिता यह नोड. वर्तमान नोड के नीचे स्थित और उससे जुड़े नोड को कहा जाता है वंशज यह नोड. चलिए एक उदाहरण लेते हैं. नोड बी लें, तो उसके माता-पिता नोड ए होंगे, और उसके बच्चे नोड डी, ई और एफ होंगे।

चादर

जिस नोड की कोई संतान नहीं होती उसे पेड़ का पत्ता कहा जाता है। उदाहरण में, नोड D, E, F, G, I, J, K पत्तियां होंगी।

यह मूल शब्दावली है. अन्य अवधारणाओं पर बाद में चर्चा की जाएगी। तो, एक बाइनरी ट्री एक ऐसा पेड़ है जिसमें प्रत्येक नोड में दो से अधिक बच्चे नहीं होंगे। जैसा कि आपने अनुमान लगाया, उदाहरण से पेड़ बाइनरी नहीं होगा, क्योंकि नोड्स बी और एच में दो से अधिक बच्चे हैं। यहाँ एक बाइनरी ट्री का उदाहरण दिया गया है:

पेड़ के नोड्स में कोई भी जानकारी हो सकती है। बाइनरी सर्च ट्री एक बाइनरी ट्री है जिसमें निम्नलिखित गुण होते हैं:

1. बाएँ और दाएँ दोनों उपवृक्ष द्विआधारी खोज वृक्ष हैं।
2. एक मनमाने ढंग से नोड एक्स के बाएं उपट्री के सभी नोड्स में डेटा कुंजी मान नोड एक्स के डेटा कुंजी मान से कम है।
3. एक मनमाना नोड

कुंजी - नोड की कुछ विशेषता (उदाहरण के लिए, एक संख्या)। पेड़ के उस तत्व को ढूंढने में सक्षम होने के लिए कुंजी की आवश्यकता होती है जिससे यह कुंजी मेल खाती है। बाइनरी सर्च ट्री उदाहरण:

ट्री व्यू

जैसे-जैसे मैं आगे बढ़ूंगा, आपकी समझ को बेहतर बनाने के लिए मैं कोड के कुछ (शायद अधूरे) टुकड़े शामिल करूंगा। पूरा कोड लेख के अंत में होगा.

पेड़ गांठों से बना होता है। नोड संरचना:

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;
    }
//...остальные методы узла
}

प्रत्येक नोड में दो बच्चे हैं (यह बहुत संभव है कि बाएँ बच्चे और/या दाएँ बच्चे के बच्चे शून्य होंगे)। आप शायद समझ गए होंगे कि इस मामले में संख्या डेटा नोड में संग्रहीत डेटा है; कुंजी - नोड कुंजी.

हमने गुत्थी सुलझा ली, अब बात करते हैं पेड़ों से जुड़ी गंभीर समस्याओं की। यहां और नीचे, "ट्री" शब्द का अर्थ बाइनरी सर्च ट्री की अवधारणा से होगा। बाइनरी ट्री संरचना:

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 तत्व हैं, तो इसका मतलब है कि पेड़ के आधार 2 स्तर लॉग (n) होंगे। और खोज में, चक्र के एक कदम के लिए, आप एक स्तर नीचे चले जाते हैं।

सम्मिलित

यदि आपने खोज का सार समझ लिया है तो सम्मिलन को समझना आपके लिए कठिन नहीं होगा। आपको बस पेड़ के पत्ते के नीचे जाने की जरूरत है (खोज में वर्णित वंश के नियमों के अनुसार) और उसका वंशज बनना है - कुंजी के आधार पर बाएं या दाएं। कार्यान्वयन:

   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))।

निष्कासन

हटाना सबसे जटिल ऑपरेशन है जिसे किसी पेड़ के साथ करने की आवश्यकता होगी। यह स्पष्ट है कि सबसे पहले उस तत्व को ढूंढना आवश्यक होगा जिसे हम हटाने जा रहे हैं। लेकिन फिर क्या? यदि हम इसके संदर्भ को शून्य पर सेट करते हैं, तो हम उस उपवृक्ष के बारे में जानकारी खो देंगे जिसका मूल यह नोड है। पेड़ हटाने के तरीकों को तीन मामलों में विभाजित किया गया है।

पहला मामला. हटाए जाने वाले नोड की कोई संतान नहीं है.

यदि हटाए जाने वाले नोड में कोई संतान नहीं है, तो इसका मतलब है कि यह एक पत्ता है। इसलिए, आप बस इसके पैरेंट के बाएँ बच्चे या दाएँ बच्चे फ़ील्ड को शून्य पर सेट कर सकते हैं।

दूसरा मामला. हटाए जाने वाले नोड में एक बच्चा है

ये मामला भी बहुत मुश्किल नहीं है. आइए अपने उदाहरण पर वापस जाएँ। मान लीजिए कि हमें कुंजी 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(लॉग(n))

सममित बाईपास

ट्रैवर्सल पेड़ के साथ कुछ करने के लिए उसके प्रत्येक नोड का दौरा है।

पुनरावर्ती सममित ट्रैवर्सल एल्गोरिथ्म:

1. बाएं बच्चे पर एक क्रिया करें
2. अपने आप से एक कार्य करें
3. सही बच्चे पर कार्रवाई करें

कोड:

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

निष्कर्ष

अंत में! यदि मैंने कुछ समझाया नहीं है या कोई टिप्पणी नहीं है, तो मैं टिप्पणियों में प्रतीक्षा कर रहा हूं। जैसा कि वादा किया गया था, यहाँ पूरा कोड है।

नोड.जावा:

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;
    }
}

बाइनरीट्री.जावा:

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)। मेरी राय में, यह बाइनरी ट्री के सबसे महत्वपूर्ण नुकसानों में से एक है।

केवल पंजीकृत उपयोगकर्ता ही सर्वेक्षण में भाग ले सकते हैं। साइन इन करेंकृपया।

मैं काफी समय से हैबे पर नहीं हूं, और मैं जानना चाहूंगा कि आप किन विषयों पर कौन से लेख अधिक देखना चाहेंगे?

• डेटा संरचनाएं

• एल्गोरिदम (डीपी, रिकर्सन, डेटा संपीड़न, आदि)

• वास्तविक जीवन में डेटा संरचनाओं और एल्गोरिदम का अनुप्रयोग

• जावा में एंड्रॉइड एप्लिकेशन प्रोग्रामिंग

• जावा वेब एप्लिकेशन प्रोग्रामिंग

2 उपयोगकर्ताओं ने मतदान किया। 1 उपयोगकर्ता ने भाग लिया।

स्रोत: www.habr.com