🥇Siġra Binarja jew kif tipprepara siġra tat-tfittxija binarja

Preludju

Dan l-artikolu huwa dwar siġar tat-tiftix binarju. Dan l-aħħar għamilt artiklu dwar kompressjoni tad-data bl-użu tal-metodu Huffman. Hemm ma tantx tajt attenzjoni lis-siġar binarji, minħabba li l-metodi ta 'tfittxija, inserzjoni u tħassir ma kinux rilevanti. Issa ddeċidejt li nikteb artiklu dwar is-siġar. Ejja nibdew.

Siġra hija struttura tad-dejta li tikkonsisti minn nodi konnessi bi truf. Nistgħu ngħidu li siġra hija każ speċjali ta 'graff. Hawn siġra eżempju:

Din mhix siġra tat-tfittxija binarja! Kollox huwa maqtugħ!

Terminoloġija

Għerq

Għerq tas-siġra - dan huwa l-ogħla node tiegħu. Fl-eżempju, dan huwa node A. F'siġra, mogħdija waħda biss tista 'twassal mill-għerq għal kwalunkwe nodu ieħor! Fil-fatt, kull node jista 'jitqies bħala l-għerq tas-subtree li jikkorrispondi għal dan in-node.

Ġenituri/dixxendenti

In-nodi kollha ħlief l-għerq għandhom eżattament tarf wieħed li jwassal għal nodu ieħor. In-nodu li jinsab fuq dak kurrenti jissejjaħ ġenitur dan in-node. Node li jinsab taħt dak kurrenti u konness miegħu jissejjaħ dixxendent dan in-node. Ejja nużaw eżempju. Ejja nieħdu n-node B, allura l-ġenitur tiegħu jkun in-node A, u t-tfal tiegħu jkunu n-nodi D, E u F.

Folja

Nodu li m'għandux tfal se jissejjaħ werqa tas-siġra. Fl-eżempju, il-weraq se jkunu nodi D, E, F, G, I, J, K.

Din hija t-terminoloġija bażika. Kunċetti oħra se jiġu diskussi aktar. Allura, siġra binarja hija siġra li fiha kull nodu se jkollu mhux aktar minn żewġt itfal. Kif qtajt, is-siġra mill-eżempju mhux se tkun binarja, minħabba li n-nodi B u H għandhom aktar minn żewġt itfal. Hawn eżempju ta 'siġra binarja:

In-nodi tas-siġar jista 'jkun fihom kwalunkwe informazzjoni. Siġra tat-tfittxija binarja hija siġra binarja li għandha l-proprjetajiet li ġejjin:

Kemm is-subsiġar tax-xellug kif ukoll tal-lemin huma siġar tat-tiftix binarji.
In-nodi kollha tas-subtree tax-xellug ta 'node X arbitrarju għandhom valuri taċ-ċavetta tad-dejta inqas mill-valur taċ-ċavetta tad-dejta tan-node X innifsu.
In-nodi kollha fis-subtree tal-lemin ta 'node X arbitrarju għandhom valuri taċ-ċavetta tad-dejta akbar minn jew ugwali għall-valur taċ-ċavetta tad-dejta tan-node X innifsu.

Ewlenin — kwalunkwe karatteristika tan-nodu (pereżempju, numru). Iċ-ċavetta hija meħtieġa sabiex tkun tista' ssib l-element tas-siġra li għalih tikkorrispondi din iċ-ċavetta. Eżempju ta' siġra ta' tfittxija binarja:

Veduta tas-siġra

Hekk kif nimxu 'l quddiem, ser nipprovdi xi biċċiet ta' kodiċi (possibilment mhux kompluti) biex ittejjeb il-fehim tiegħek. Il-kodiċi sħiħ se jkun fl-aħħar tal-artiklu.

Siġra tikkonsisti minn nodi. Struttura tan-nodi:

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

Kull node għandu żewġt itfal (huwa pjuttost possibbli li t-tfal leftChild u/jew rightChild ikun fihom valur null). Int probabilment induna li f'dan il-każ id-dejta tan-numru hija d-dejta maħżuna fin-node; ċavetta — ċavetta tan-node.

Irranġajna l-għoqda, issa ejja nitkellmu dwar problemi urġenti dwar is-siġar. Minn hawn 'il quddiem, bil-kelma "siġra" ser infisser il-kunċett ta' siġra ta 'tfittxija binarja. Struttura tas-siġra binarja:

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

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

Neħtieġu biss l-għerq tas-siġra bħala qasam tal-klassi, għax mill-għerq, billi tuża l-metodi getLeftChild() u getRightChild(), tista’ tasal għal kwalunkwe nodu fis-siġra.

Algoritmi f'siġra

Fittex

Ejja ngħidu li għandek siġra mibnija. Kif issib element biċ-ċavetta ewlenija? Ikollok bżonn timxi b'mod sekwenzjali mill-għerq 'l isfel mis-siġra u tqabbel il-valur taċ-ċavetta maċ-ċavetta tan-nodu li jmiss: jekk iċ-ċavetta hija inqas miċ-ċavetta tan-nodu li jmiss, imbagħad mur lejn id-dixxendent tax-xellug tan-nodu, jekk tkun akbar, lejn il-lemin, jekk iċ-ċwievet huma ugwali, jinstab in-nodu mixtieq! Kodiċi rilevanti:

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

Jekk il-kurrent isir null, allura t-tfittxija tkun waslet fit-tmiem tas-siġra (f'livell kunċettwali, inti qiegħed f'post ineżistenti fis-siġra - tifel ta 'werqa).

Ejja nikkunsidraw l-effettività tal-algoritmu tat-tfittxija fuq siġra bilanċjata (siġra li fiha n-nodi huma mqassma bejn wieħed u ieħor indaqs). Imbagħad l-effiċjenza tat-tfittxija tkun O(log(n)), u l-logaritmu huwa bażi 2. Ħares: jekk ikun hemm n elementi f'siġra bilanċjata, allura dan ifisser li se jkun hemm log(n) għal bażi 2 livelli tal- siġra. U fit-tfittxija, f'pass wieħed taċ-ċiklu, tinżel livell wieħed.

daħħal

Jekk taqbad l-essenza tat-tfittxija, allura tifhem l-inserzjoni mhux se tkun diffiċli għalik. Għandek bżonn biss li tinżel għal werqa tas-siġra (skond ir-regoli tad-dixxendenza deskritti fit-tfittxija) u ssir id-dixxendent tagħha - xellug jew lemin, skont iċ-ċavetta. Implimentazzjoni:

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

F'dan il-każ, minbarra n-nodu attwali, huwa meħtieġ li tinħażen informazzjoni dwar il-ġenitur tan-nodu attwali. Meta l-kurrent isir ugwali għal null, il-varjabbli ġenitur ikun fih il-folja li neħtieġu.
L-effiċjenza tal-inserzjoni ovvjament tkun l-istess bħal dik tat-tfittxija - O(log(n)).

Tħassir

It-tneħħija hija l-aktar operazzjoni diffiċli li trid titwettaq fuq siġra. Huwa ċar li l-ewwel se jkollna bżonn insibu l-element li se nħassru. Imma x'inhu mela? Jekk sempliċement nissettjaw ir-referenza tagħha għal null, aħna nitilfu informazzjoni dwar is-subtree li tagħha dan in-node huwa l-għerq. Il-metodi tat-tneħħija tas-siġar huma maqsuma fi tliet każijiet.

L-ewwel każ. In-nodu li qed jitħassar m'għandux tfal

Jekk in-nodu li qed jitħassar m'għandux tfal, allura dan ifisser li hija werqa. Għalhekk, tista 'sempliċement issettja l-oqsma leftChild jew rightChild tal-ġenitur tagħha għal null.

It-tieni każ. In-nodu li għandu jitħassar għandu tifel wieħed

Dan il-każ ukoll mhuwiex ikkumplikat ħafna. Ejja nerġgħu lura għall-eżempju tagħna. Ejja ngħidu li għandna bżonn inħassru element b'ċavetta 14. Naqbel li peress li huwa d-dixxendent it-tajjeb ta 'node b'ċavetta 10, allura kwalunkwe mid-dixxendenti tiegħu (f'dan il-każ dak it-tajjeb) ikollu ċavetta akbar minn 10, allura inti jista 'faċilment "taqta'" mis-siġra, u jgħaqqad il-ġenitur direttament mat-tifel tan-node li qed jitħassar, i.e. qabbad in-node biċ-ċavetta 10 man-node 13. Is-sitwazzjoni tkun simili kieku kien meħtieġ li jitħassar node li huwa t-tifel tax-xellug tal-ġenitur tiegħu. Aħseb dwarha lilek innifsek - analoġija eżatta.

It-tielet każ. Node għandu żewġt itfal

L-aktar każ diffiċli. Ejja nħarsu lejn eżempju ġdid.

Fittex għal suċċessur

Ejja ngħidu li għandna bżonn inħassru node b'ċavetta 25. Min għandna npoġġu minfloku? Wieħed mis-segwaċi tiegħu (dixxendenti jew dixxendenti tad-dixxendenti) irid isir suċċessur(dak li se jieħu l-post tan-node li qed jitneħħa).

Kif tifhem min għandu jsir is-suċċessur? Intuwittivament, dan huwa node fis-siġra li ċ-ċavetta tagħha hija l-akbar li jmiss min-nodu li qed jitħassar. L-algoritmu huwa kif ġej. Ikollok bżonn tmur lejn id-dixxendent tal-lemin tagħha (dejjem lejn il-lemin, għax diġà ntqal li ċ-ċavetta tas-suċċessur hija akbar miċ-ċavetta tan-node li qed titħassar), u mbagħad tgħaddi mill-katina tad-dixxendenti tax-xellug ta 'dan id-dixxendent tal-lemin. . Fl-eżempju, aħna mmorru għan-nodu biċ-ċavetta 35, u mbagħad ninżlu għall-werqa permezz tal-katina tat-tfal tax-xellug tagħha - f'dan il-każ, din il-katina tikkonsisti biss fin-nodu biċ-ċavetta 30. Strettament speaking, qed infittxu għall-iżgħar node fis-sett ta 'nodi akbar minn dak li qed infittxu node.

Kodiċi tal-metodu tat-tfittxija tas-suċċessur:

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

Kodiċi sħiħ għall-metodu tat-tħassir:

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

Il-kumplessità tista' tiġi approssimata għal O(log(n)).

Tfittxija massimu/minimu f'siġra

Huwa ovvju kif issib il-valur minimu/massimu f'siġra - għandek bżonn timxi b'mod sekwenzjali tul il-katina ta 'elementi tax-xellug/lemin tas-siġra, rispettivament; meta tasal għall-folja, ikun l-element minimu/massimu.

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

Kumplessità - O(log(n))

Bypass simetriku

Traversal qed iżżur kull node tas-siġra sabiex tagħmel xi azzjoni magħha.

Algoritmu trasversali simetriku rikursiv:

Agħmel azzjoni fuq it-tifel tax-xellug
Agħmel azzjoni miegħek innifsek
Agħmel azzjoni fuq it-tifel it-tajjeb

Kodiċi:

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

Konklużjoni

Fl-aħħarnett! Jekk ma spjegajt xejn jew għandi xi kummenti, jekk jogħġbok ħallihom fil-kummenti. Kif imwiegħed, nipprovdi l-kodiċi komplut.

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

Deġenerazzjoni għal O(n)

Ħafna minnkom forsi ndunajtu: x'jiġri jekk tagħmel is-siġra żbilanċjata? Pereżempju, poġġi nodi b'ċwievet li qed jiżdiedu f'siġra: 1,2,3,4,5,6... Imbagħad is-siġra tkun xi ftit tixbah lista konnessa. U iva, is-siġra titlef l-istruttura tas-siġra tagħha, u għalhekk l-effiċjenza tal-aċċess għad-dejta. Il-kumplessità tal-operazzjonijiet ta' tfittxija, inserzjoni u tħassir se ssir l-istess bħal dik ta' lista konnessa: O(n). Dan huwa wieħed mill-iktar żvantaġġi importanti, fl-opinjoni tiegħi, tas-siġar binarji.

Utenti reġistrati biss jistgħu jipparteċipaw fl-istħarriġ. Idħol, ta 'xejn.

Ilni ħafna fuq iċ-ċentru, u nixtieq inkun naf liema artikli dwar liema suġġetti tixtieq tara aktar?

Strutturi tad-data
Algoritmi (DP, rikorsi, kompressjoni tad-dejta, eċċ.)
Applikazzjoni ta 'strutturi ta' data u algoritmi fil-ħajja reali
Ipprogrammar Applikazzjonijiet Android f'Java
L-ipprogrammar ta' applikazzjonijiet tal-web f'Java

2 utenti vvutaw. utent 1 astjena.

Sors: www.habr.com

Siġra Binarja jew kif tipprepara siġra tat-tfittxija binarja