बायनरी ट्री किंवा बायनरी सर्च ट्री कसे तयार करावे

प्रस्तावना

हा लेख बायनरी शोध झाडांबद्दल आहे. मी अलीकडे एक लेख केला आहे Huffman पद्धत वापरून डेटा कॉम्प्रेशन. तेथे मी बायनरी झाडांकडे जास्त लक्ष दिले नाही, कारण शोध, समाविष्ट करणे आणि हटविण्याच्या पद्धती संबंधित नाहीत. आता मी झाडांबद्दल एक लेख लिहायचे ठरवले. चला सुरू करुया.

ट्री ही डेटा स्ट्रक्चर आहे ज्यामध्ये कडांनी जोडलेले नोड्स असतात. आपण असे म्हणू शकतो की एक वृक्ष ग्राफचा एक विशेष केस आहे. येथे एक उदाहरण झाड आहे:

हे बायनरी शोध वृक्ष नाही! सर्व काही कापले आहे!

टर्मिनोलॉजी

रूट

झाडाचे मूळ - हा त्याचा सर्वात वरचा नोड आहे. उदाहरणामध्ये, हे नोड A आहे. झाडामध्ये, फक्त एक मार्ग रूटपासून इतर कोणत्याही नोडकडे नेऊ शकतो! खरं तर, कोणत्याही नोडला या नोडशी संबंधित सबट्रीचे मूळ मानले जाऊ शकते.

पालक/वंशज

रूट वगळता सर्व नोड्समध्ये अगदी एक धार असते जी दुसऱ्या नोडपर्यंत जाते. वर्तमान एक वर स्थित नोड म्हणतात पालक हा नोड. वर्तमानाच्या खाली स्थित आणि त्यास जोडलेला नोड म्हणतात वंशज हा नोड. चला एक उदाहरण वापरू. चला नोड बी घेऊ, नंतर त्याचे पालक नोड 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;
    }
//...остальные методы узла
}

प्रत्येक नोडमध्ये दोन मुले असतात (हे शक्य आहे की लेफ्ट चाइल्ड आणि/किंवा राईट चाइल्ड मुलांमध्ये शून्य मूल्य असेल). तुम्हाला कदाचित लक्षात आले असेल की या प्रकरणात संख्या डेटा नोडमध्ये संग्रहित डेटा आहे; की - नोड की.

आम्ही गाठ सोडवली आहे, आता झाडांबद्दलच्या समस्यांबद्दल बोलूया. यापुढे, "वृक्ष" या शब्दाचा अर्थ मी बायनरी शोध वृक्षाची संकल्पना घेईन. बायनरी वृक्ष रचना:

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 घटक असतील, तर याचा अर्थ असा की लॉग(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)) सारखीच असेल.

हटवा

काढणे हे सर्वात कठीण ऑपरेशन आहे जे झाडावर करणे आवश्यक आहे. हे स्पष्ट आहे की प्रथम आपण हटवणार आहोत तो घटक शोधणे आवश्यक आहे. पण मग काय? जर आपण त्याचा संदर्भ नल वर सेट केला तर आपण ज्या सबट्रीचे हे नोड मूळ आहे त्याबद्दलची माहिती गमावू. झाडे काढण्याच्या पद्धती तीन प्रकरणांमध्ये विभागल्या आहेत.

पहिली केस. हटवल्या जात असलेल्या नोडला मुले नाहीत

जर हटविल्या जाणार्‍या नोडला मुले नसतील तर याचा अर्थ असा आहे की ते एक पान आहे. म्हणून, तुम्ही फक्त त्याच्या पालकांचे 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());
        }
    }
}

PS

O(n) कडे अध:पतन

तुमच्यापैकी अनेकांनी लक्षात घेतले असेल: जर तुम्ही झाड असंतुलित केले तर? उदाहरणार्थ, झाडामध्ये वाढत्या कळांसह नोड्स ठेवा: 1,2,3,4,5,6... मग झाड काही प्रमाणात लिंक केलेल्या सूचीसारखे दिसेल. आणि होय, वृक्ष त्याच्या झाडाची रचना गमावेल आणि म्हणून डेटा ऍक्सेसची कार्यक्षमता. शोध, समाविष्ट करणे आणि हटवणे ऑपरेशन्सची जटिलता लिंक केलेल्या सूचीप्रमाणेच होईल: O(n). माझ्या मते, बायनरी झाडांचे तोटे हे सर्वात महत्वाचे आहे.

केवळ नोंदणीकृत वापरकर्तेच सर्वेक्षणात भाग घेऊ शकतात. साइन इन करा, आपले स्वागत आहे.

मी खूप दिवसांपासून हबवर नाही आणि मला जाणून घ्यायचे आहे की तुम्हाला कोणत्या विषयावरील लेख अधिक पहायचे आहेत?

• डेटा संरचना

• अल्गोरिदम (डीपी, पुनरावृत्ती, डेटा कॉम्प्रेशन इ.)

• वास्तविक जीवनात डेटा संरचना आणि अल्गोरिदमचा वापर

• Java मध्ये अँड्रॉइड ऍप्लिकेशन्स प्रोग्रामिंग

• Java मध्ये प्रोग्रामिंग वेब अनुप्रयोग

2 वापरकर्त्यांनी मतदान केले. 1 वापरकर्ता दूर राहिला.

स्रोत: www.habr.com