Binaarne puu ehk kuidas valmistada binaarset otsingupuud

Prelüüd

See artikkel käsitleb binaarseid otsingupuusid. Hiljuti kirjutasin artikli Huffman'i meetodil andmete tihendamisest. Seal ei pööranud ma palju tähelepanu binaarsetele puudele, kuna otsimise, lisamise ja kustutamise meetodid polnud aktuaalsed. Nüüd otsustasin kirjutada artikli just puude kohta. Alustame siis.

Puud on andmestruktuurid, mis koosnevad sõlmedest, mis on ühendatud servadega. Võib öelda, et puu on graafi erijuht. Siin on puu näide:

See ei ole binaarne otsingupuu! Kõik allpool!

Terminoloogia

Juurepunkt

Puulehe juurepunkt on selle kõige ülemine sõlm. Näites on see sõlm A. Puust juurepunktist võib iga teise sõlmeni viia ainult üks tee! Tegelikult saab ühtegi sõlme käsitleda vastava alampuu juurepunktina.

Vanemad/ajalugu

Kõik sõlmed, välja arvatud juurepunkt, omavad täpselt ühte serva, mis viib ülespoole teise sõlmeni. Sõlm, mis asub praegusest kõrgemal, nimetatakse vanemaks selle sõlme jaoks. Sõlm, mis asub praegusest allpool ja on sellega ühendatud, nimetatakse järeltulijaks selle sõlme jaoks. Võtame näiteks sõlme B, siis tema vanem on sõlm A ja järeltulijad on sõlmed D, E ja F.

Leht

Puu sõlmed, millel ei ole järgnenud sõlmi, nimetatakse puu lehtedeks. Antud näites on lehtedeks sõlmed D, E, F, G, I, J, K.

See on põhiterminoloogia. Teised mõisted käsitletakse hiljem. Nii on binaarne puu puu, millel igal sõlmel on mitte rohkem kui kaks järglast. Nagu arvatavasti teate, ei ole antud puu binaarne, kuna sõlmed B ja H omavad rohkem kui kahte järglast. Siin on näide binaarsest puust:

Puu sõlmedes võib paikneda mis tahes teave. Binaarne otsingu puu on binaarne puu, millel on järgmised omadused:

1. Mõlemad alampuud — vasak ja parem — on binaarsed otsingu puud.
2. Kõik vasakpoolse alampuu sõlmed mistahes sõlme X puhul on andmekohtade võtmete väärtused väiksemad kui sõlme X enda võtme väärtus.
3. Kõik parempoolse alampuu sõlmed mistahes sõlme X puhul on andmekohtade võtmete väärtused suuremad või võrdsed kui sõlme X enda võtme väärtus.

Ala — mõni sõlme omadus (näiteks number). Võti on vajalik, et leida puu element, millele see võti vastab. Näide binaarsest otsingu puust:

Puu esitus

Etenemisprotsessis toon ma välja mõned (võimalikult mitte täielikud) koodilõigud, et aidata teil paremini mõista. Täielik kood on artikli lõpus.

Puu koosneb sõlmedest. Sõlme struktuur:

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

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

    public Node getRightChild() {
        return rightChild;
    }
//...muud sõlme meetodid
}

Igal sõlmel on kaks last (tõenäoliselt võivad leftChild ja/või rightChild sisaldada väärtust null). Olete ilmselt aru saanud, et antud juhul number data on sõlmes hoitavad andmed; key on sõlme võti.

Nüüd, kui oleme sõlmega tutvunud, räägime puude päevakajalistest probleemidest. Siin ja edaspidi mõistan sõna "puu" all binaarse otsingu puu mõistet. Binaarse puu struktuur:

public class BinaryTree {
     private Node root;

    //puu meetodid
}

Klassi väljana vajame ainult puu juuri, kuna juuri kaudu on võimalik meetodite getLeftChild() ja getRightChild() abil pääseda iga puu sõlmeni.

Algoritmid puus

Otsi

Oletame, et teil on loodud puu. Kuidas leida elementi, millel on võti key? Tuleb järk-järgult liikuda juurest allapoole puu ja võrrelda väärtust key järgmise sõlme võtmega: kui key on väiksem kui järgmise sõlme võti, siis liikuda sõlme vasakule alampuudule, kui suurem — paremale, kui võtmed on võrdsed — otsitav sõlm on leitud! Vastav kood:

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

Kui current muutub nulliks, tähendab see, et läbimine on jõudnud puu lõppu (kontseptuaalses mõttes viibite te puudulikkuse koha — lehes oleva järglase juures).

Vaadakem otsingu algoritmi efektiivsust tasakaalustatud puus (puus, kus sõlmed on jaotatud enam-vähem ühtlaselt). Seega on otsingu efektiivsus O(log(n)), kusjuures logaritm on alus 2. Näiteks: kui tasakaalustatud puus on n elementi, tähendab see, et puu taset on log(n) alusel 2. Ja otsingus, ühe tsükli sammu jooksul, laskute ühe taseme võrra.

Sisestamine

Kui olete otsimise mõtte tabanud, siis ei tohiks lisamine teile raskusi valmistada. Tuleb lihtsalt laskuda puu lehte (langemise reeglite kohaselt, nagu on kirjas otsingus) ja saada selle järeltulijaks — vasakuks või paremaks, sõltuvalt võtmest. Teostus:

   public void insert(T insertData, int key) {
        Node current = root;
        Node parent;
        Node 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;
                    }
                }
            }
        }
    }

Sellisel juhul tuleb lisaks praegusele sõlmele hoida teavet ka praeguse sõlme vanema kohta. Kui current saab nulliks, sisaldab muutuja parent vajalikku lehte.
Sisestamise efektiivsus on kindlasti sama mis otsimise puhul — O(log(n)).

Kustuta

Kustutamine on kõige keerulisem toiming, mida puu juures teha tuleb. Esiteks tuleb leida element, mille me kavatseme eemaldada. Aga mis siis edasi? Kui lihtsalt määrata selle viide väärtusele null, kaotame me teabe selle alampuu kohta, mille juureks on see sõlm. Puu eemaldamise meetodid jagunevad kolme juhtumi vahel.

Esimene juhtum. Eemaldatav sõlm ei oma järeltulijaid.

Kui eemaldatav sõlm ei oma järeltulijaid, siis tähendab see, et ta on leht. Seega võib lihtsalt määrata tema vanema leftChild või rightChild väljadele väärtuse null.

Teine juhtum. Eemaldatav sõlm omab ühte järeltulijat.

See juht ei ole ka eriti keeruline. Naaseme meie näite juurde. Oletame, et peame eemaldama elemendi, mille võtme number on 14. Nõustute, et kuna see on parempoolne järeltulija sõlme, mille võtme number on 10, siis igal tema järeltulijal (antud juhul parempoolsel) on kindlasti võtme number, mis on suurem kui 10. Seega saab selle lihtsasti „välja lõigata“ puust, ning vanemate sõlme saab otse ühendada eemaldatava sõlme järeltulijaga, st sõlm, mille võtme number on 10, saab ühendatud sõlmega 13. Sarnane olukord oleks ka siis, kui peaksime eemaldama sõlme, mis on tema vanema vasak järeltulija. Mõelge sellele ise — täpselt analoogne.

Kolmas juhtum. Sõlm omab kahte järeltulijat.

Õige keerulisem juhtum. Lahkame selle uue näite põhjal.

Järeltulija otsimine.

Oletame, et peame eemaldama sõlme, mille võtme number on 25. Keda paneme tema asemele? Keegi tema järgmistest (järeltulijatest või järeltulijate järeltulijatest) peaks saama järeltulijaks.(see, kes asendab eemaldatavat sõlme).

Kuidas mõista, kes peab olema järglane? Intuitiivselt on selge, et see on puu sõlm, mille võti on eemaldatava sõlme järgmiseks suuruseks. Algoritm on järgmine. Tuleb minna selle paremale järeltulijale (aina paremale, sest on juba öeldud, et järglase võti on suurem eemaldatava sõlme võtmel), ja siis liikuda selle parema järeltulija vasakute järeltulijate ahelas. Näites peame liikuma sõlme juurde, mille võti on 35, ja seejärel liikuma alla lehe kaudu tema vasakute järeltulijate ahelas — antud juhul koosneb see ahel vaid sõlmest, mille võti on 30. Rangelt öeldes otsime me väikseimat sõlme nende sõlmede kogumis, mis on otsitavast sõlmest suuremad.

Järglase otsimise meetodi kood:

    public Node getSuccessor(Node deleteNode) {
        Node parentSuccessor = deleteNode; // vanema järglane
        Node successor = deleteNode; // järglane
        Node current = successor.getRightChild(); // lihtsalt "läbiv" sõlm
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        // tsüklist väljudes on meil järglane ja vanema järglane
        if (successor != deleteNode.getRightChild()) { // kui järglane ei ühti kustutatava sõlme parema lapsega
            parentSuccessor.setLeftChild(successor.getRightChild()); // siis tema vanem võtab järglase järeltulija, et seda mitte kaotada
            successor.setRightChild(deleteNode.getRightChild()); // seome järglase kustutatava sõlme parema lapsega
        }
        return successor;
    }

Kogu delete meetodi kood:

public boolean delete(int deleteKey) {
        Node current = root;
        Node parent = current;
        boolean isLeftChild = false; // Sõltuvalt sellest, kas kustutatav sõlm on oma vanemast vasak või parem järeltulija, omandab loogiline muutuja isLeftChild väärtuse true või false vastavalt.
        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) { // esimene juhtum
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) { // teine juhtum
            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 { // kolmas juhtum
            Node successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

Aja võib hinnata O(log(n))-ks.

Maksimaalse/minimaalse otsimine puus

Ilmselgelt, kuidas leida puus minimaalne/maximaalne väärtus — tuleb järjestikku liikuda puu vasakute/paretute elementide kaudu; kui jõuad lehtedeni, on see minimaalne/maximaalne element.

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

Aja keerukus — O(log(n))

Sümbiootiline läbimine

Läbimine — iga puu sõlme külastamine tegevuse sooritamiseks.

Rekursiivse sümbiootilise läbimise algoritm:

1. Teha tegevus vasakul lapsel
2. Teha tegevus endaga
3. Teha tegevus paremal lapsel

Kood:

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Siin võib olla mis iganes
            inOrder(current.getRightChild());
        }
    }

Kokkuvõte

Lõpuks! Kui ma midagi ei selgitanud või on mingeid märkusi, ootan neid kommentaarides. Nagu lubatud, esitan täis koodi.

Node.java:

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

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

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

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

    public Node getLeftChild() {
        return leftChild;
    }

    public Node 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());
        }
    }
}

P.S.

Langenemine O(n) tasemeni

Paljud teist on võib-olla märganud, et mis juhtub, kui puud pole tasakaalus? Näiteks, kui panna puusse järjestikuseid sõlmi: 1, 2, 3, 4, 5, 6… Siis meenutab puu pigem ühendatud loendit. Ja jah, puu kaotab oma puulise struktuuri, seega ka andmete juurdepääsu efektiivsuse. Otsingu, sisestamise ja kustutamise keerukus muutub sarnaseks ühendatud loendi omadega: O(n). See on üks olulisemaid, minu arvates, kahjusid, mis tulenevad binaarsetest puudest.

Ainult registreeritud kasutajad saavad küsitluses osaleda. Logige sisse, palun.

Ma olen hubastes hiljuti ning sooviksin teada, milliseid teemasid sooviksite rohkem näha?

• Andmestruktuurid

• Algoritmid (Dünaamiline programmeerimine, rekurssioon, andmete tihendamine jne.)

• Andmestruktuuride ja algoritmide rakendamine reaalses elus

• Android-rakenduste programmeerimine Java-s

• Veebirakenduste programmeerimine Java-s

Hääletas 2 kasutajat. 1 kasutaja hoidub.

Allikas: habr.com