बाइनरी ट्री वा बाइनरी खोज रूख कसरी तयार गर्ने

Prelude

यो लेख बाइनरी खोज रूखहरूको बारेमा हो। मैले भर्खरै बारेमा एउटा लेख गरें Huffman विधि प्रयोग गरेर डाटा सङ्कुचन। त्यहाँ मैले बाइनरी रूखहरूमा धेरै ध्यान दिएन, किनभने खोज, सम्मिलन, र मेटाउने विधिहरू सान्दर्भिक थिएनन्। अब मैले रूखहरूको बारेमा लेख लेख्ने निर्णय गरें। सुरु गरौं।

एक रूख एक डेटा संरचना हो जसमा किनारहरू द्वारा जोडिएका नोडहरू समावेश हुन्छन्। हामी भन्न सक्छौं कि रूख ग्राफको एक विशेष केस हो। यहाँ एउटा उदाहरण रूख छ:

यो बाइनरी खोज रूख होइन! सबै काटिएको छ!

टर्मिनलजी

रूट

रुखको जरा - यो यसको शीर्ष नोड हो। उदाहरणमा, यो नोड ए हो। रूखमा, एउटा मात्र बाटोले रूटबाट अर्को नोडमा लैजान सक्छ! वास्तवमा, कुनै पनि नोडलाई यस नोडसँग सम्बन्धित सबट्रीको मूलको रूपमा मान्न सकिन्छ।

आमाबाबु / सन्तान

रूट बाहेक सबै नोडहरूमा अर्को नोडमा पुग्ने एउटा किनारा हुन्छ। हालको माथि रहेको नोडलाई भनिन्छ अभिभावक यो नोड। हालको एक मुनि स्थित नोड र यसलाई जडान भनिन्छ वंशज यो नोड। एउटा उदाहरण प्रयोग गरौं। नोड 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)) हुनेछ, र logarithm आधार 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))।

मेटाउनुहोस्

हटाउने सबैभन्दा कठिन कार्य हो जुन रूखमा प्रदर्शन गर्न आवश्यक पर्दछ। यो स्पष्ट छ कि पहिले हामीले तत्व फेला पार्न आवश्यक छ जुन हामी मेटाउन जाँदैछौं। तर त्यसपछि के? यदि हामीले यसको सन्दर्भलाई शून्यमा सेट गर्यौं भने, हामीले यो नोड रूट भएको सबट्रीको बारेमा जानकारी गुमाउनेछौं। रूख हटाउने विधिहरू तीन अवस्थामा विभाजित छन्।

पहिलो केस। मेटाइएको नोडको कुनै बच्चा छैन

यदि नोड मेटाइएको छ भने कुनै बच्चा छैन, यसको मतलब यो पात हो। तसर्थ, तपाईले यसको अभिभावकको 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 मा प्रोग्रामिङ वेब अनुप्रयोगहरू

2 प्रयोगकर्ताहरूले मतदान गरे। १ प्रयोगकर्ता रोकिए।

स्रोत: www.habr.com