Binary Tree ehk kuidas koostada binaarset otsingupuud

Eelajak

See artikkel on pühendatud binaarsetele otsingupuidule. Hiljuti kirjutasin artikli Huffmani meetodiga andmete tihendamisest. Seal ma ei pööranud liiga palju tähelepanu binaarsetele puudele, kuna otsingu, sisestamise ja kustutamise meetodid ei olnud aktuaalsed. Nüüd otsustasin kirjutada artikli just puude kohta. Alustame.

Puu on andmestruktuur, mis koosneb sõlmedest, mis on ühendatud harudega. Võib öelda, et puu on graafi spetsiifiline juhtum. Siin on näide puust:

See ei ole binaarne otsingupuu! Kogu teave on peidetud!

Terminoloogia

Juurtipp

Puu juurtipp on selle kõige ülemine sõlm. Antud näites on see sõlm A. Puust juurelt igale teisele sõlmile võib viia ainult üks tee! Tegelikult võib iga sõlme käsitleda kui vastava sõlme alampuu juurt.

Vanem/alam

Kõigil sõlmedel, välja arvatud juurtipp, on täpselt üks haru, mis viib üles poole teise sõlme juurde. Sõlm, mis asub hetke kohal, nimetatakse vanemaks selle sõlme jaoks. Sõlm, mis asub hetke all ja on sellega ühendatud, nimetatakse alamaks selle sõlme jaoks. Vaatame näidet. Võtame sõlme B, siis on selle vanem sõlm A ja alamad on sõlmed D, E ja F.

Leht

Sõlm, millel ei ole alamad, nimetatakse puu leheks. Antud näites on lehed sõlmed D, E, F, G, I, J ja K.

See on põhiterminoloogia. Teisi mõisteid käsitletakse hiljem. Nii et binaarne puu on puu, millel igal sõlmel võib olla mitte rohkem kui kaks alamad. Nagu te juba arvata võisite, ei ole antud näide binaarne, kuna sõlmed B ja H on enam kui kahe alamaga. Siin on näide binaarsest puust:

Puu sõlmedes võib olla mistahes teavet. Binaarne otsingupuu on binaarne puu, millel on järgmised omadused:

1. Mõlemad alampuud — vasak ja parem — on binaarsed otsingupuud.
2. Kõigil vasaku alampuu sõlmedel, mis kuuluvad suvalisele sõlmele X, on andmete võtmete väärtused väiksemad kui sõlme X enda võtme väärtus.
3. Kõigil parema alampuu sõlmedel, mis kuuluvad suvalisele sõlmele X, on andmete võtmete väärtused suuremad või võrdsed sõlme X enda võtme väärtusega.

Võti on mis tahes sõlme omadus (nt number). Võti on vajalik selleks, et leida puust element, millele see võti vastab. Näide binaarsest otsingupuust:

Puu esitus

Edasi liikudes toon ma välja mõned (võimalikult mittetäielikud) koodilõigud, et parandada teie arusaamist. Täielik kood leiab aset artikli lõpus.

Puu koosneb sõlmedest. Sõlme struktuur:

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;
    }
//...teised sõlme meetodid
}

Igal sõlmel on kaks järeltulijat (võimalik, et järeltulijad leftChild ja / või rightChild võivad sisaldada väärtust null). Olete ilmselt aru saanud, et antud juhul number data — andmed, mis on sõlmes salvestatud; key — sõlme võti.

Sõlmega oleme kursis, nüüd räägime puude praegustest probleemidest. Edaspidi mõtlen sõna "puu" all binaarset otsingu puud. Binaarse puu struktuur:

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

    //puu meetodid
}

Klassi väljana vajame ainult puu juurt, sest juure kaudu saab meetodite getLeftChild() ja getRightChild() abil jõuda igasugusele puu sõlmele.

Puu algoritmid

Vastuse otsimine peab olema keeruline — kui vastust on lihtne leida

Eeldame, et teil on üles ehitatud puu. Kuidas leida elementi, mille võti on key? Tuleb järjestikku liikuda juurelt alla puu kaudu ja võrrelda välist key sõlme võtmega: kui key on väiksem kui järgmise sõlme võti, siis liikuda sõlme vasakule järeltulijale, 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 saab nulliks, tähendab, et otsing jõudis puu lõpuni (kontseptsiooniliselt asute te mitteeksisteerivas puu kohas — lehe järeltulijas).

Vaadakem otsingu algoritmi efektiivsust tasakaalus puus (puus, kus sõlmed on jaotatud üksjagu ühtlaselt). Sel juhul on otsingu efektiivsus O(log(n)), kusjuures logaritm on põhjal 2. Vaadake: kui tasakaalus puus on n elementi, siis see tähendab, et puul on log(n) taset. Otsingu käigus langete ühe sammuga tsüklis ühe taseme võrra alla.

Sisestamine

Kui olete otsingu olemuse tabanud, siis ei ole lisamise mõistmine teile raske. Tuleb lihtsalt liikuda puu lehe juurde (langemisreeglite kohaselt, nagu otsingus kirjeldatud) ja saada selle järeltulijaks — vasakuks või paremaks, sõltuvalt võtme väärtusest. Rakendamine:

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

Antud juhul tuleb lisaks hetkelisele sõlmele hoida teavet käesoleva sõlme vanemast. Kui current muutub nulliks, siis on muutujas parent vajalik leht.
Selgelt on sisestamise tõhusus sama, mis otsingul — O(log(n)).

Kustutamine

Kustutamine on kõige keerulisem operatsioon, mille tuleb puu peal teostada. On selge, et kõigepealt tuleb leida element, mida me kavandame kustutada. Aga mis siis? Kui lihtsalt omistada selle lingile väärtus null, kaotame teabe selle sõlme juures oleva alampuu kohta. Puu kustutamise meetodid jagunevad kolmeks juhtumiks.

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

Kui kustutataval sõlmel ei ole järeltulijaid, tähendab see, et see on leht. Seetõttu saab lihtsalt vanema leftChild või rightChild väljadele määrata nulli.

Teine juhtum. Kustutataval sõlmel on üks järeltulija

See juhtum ei ole samuti väga keeruline. Naaseme tagasi meie näite juurde. Oletame, et tuleb kustutada element võtmega 14. Olgu see nii, et kuna see on sõlm, millel on võtmega 10 õigus järeltulija, on selle järeltulija (antud juhul parem) võtme väärtus alati suurem kui 10, seega saab selle lihtsalt puust 'välja lõigata' ja vanema otse järeltulijaga ühendada, s.t. sõle võtmega 10 ühendatakse sõlmiga 13. Sarnane oleks olukord, kui peaksime kustutama sõlme, mis on oma vanema vasak järeltulija. Mõelge selle üle ise — täpne analoogia.

Kolmas juhtum. Sõlmel on kaks järeltulijat

See on kõige keerulisem juhtum. Analüüsime uut näidet.

Eelkäija otsimine

Oletame, et peame kustutama sõlme, mille võti on 25. Keda paneme selle asemele? Keegi tema järglastest (järeltulijatest või järeltulijate järeltulijatest) peab saama järglaseks(see, kes võtab eemaldatava sõlme koha).

Kuidas mõista, kes peaks saama järglaseks? Intuitiivselt on selge, et see on puu sõlm, mille võti on eemaldatava sõlme omast suurem. Algoritm on järgmine. Tuleb liikuda tema paremale järeltulijale (alati paremale, kuna on juba öeldud, et järglase võti on suurem kui eemaldatava sõlme oma) ning seejärel minna vasakute järeltulijate ahelas selle parema järeltulija juurde. Näites peame liikuma sõlme, mille võti on 35, ja seejärel järgnema allapoole tema vasakute järeltulijate ahelas — antud juhul koosneb see ahel vaid sõlmest, mille võti on 30. Rikkalikult öeldes otsime toetava sõlme seas kõige väiksemat sõlme, mis on suurem kui otsitav sõlm.

Järglase otsimise meetodi kood:

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode; // järglase vanem
        Node<T> successor = deleteNode; // järglane
        Node<T> current = successor.getRightChild(); // lihtsalt 'läbivate' sõlm
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        // tsüklist väljudes saame järglase ja järglase vanema
        if (successor != deleteNode.getRightChild()) { // kui järglane ei lange kokku eemaldatava sõlme parema järeltulijaga
            parentSuccessor.setLeftChild(successor.getRightChild()); // siis tema vanem võtab järglase järeltulija endale, et mitte seda kaotada
            successor.setRightChild(deleteNode.getRightChild()); // seome järglase eemaldatava sõlme parema järeltulijaga
        }
        return successor;
    }

Kustutamise meetodi täielik kood:

public boolean delete(int deleteKey) {
        Node current = root;
        Node parent = current;
        boolean isLeftChild = false; // Olene lähetamine vastavalt, kas kustutatav sõlm on oma vanema vasak või parem laps, boolean muutuja isLeftChild omandab vastavalt true või 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) { // esimene juhus
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        } else if (current.getRightChild() == null) { // teine juhus
            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 juhus
            Node successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

Aja keerukus võib olla ligikaudu O(log(n)).

Puu maksimaalse/minimaalse väärtuse otsimine

Selgelt, kuidas leida puu minimaalne/maximaalne väärtus - tuleb järjestikku liikuda vasakute/paremate puu elementide ahelas; kui jõuate lehtedeni, siis see on minimaalne/maximaalne element.

    public Node getMinimum(Node startPoint) {
        Node current = startPoint;
        Node parent = current;
        while (current != null) {
            parent = current;
            current = current.getLeftChild();
        }
        return parent;
    }

    public Node getMaximum(Node startPoint) {
        Node current = startPoint;
        Node parent = current;
        while (current != null) {
            parent = current;
            current = current.getRightChild();
        }
        return parent;
    }

Keerukus - O(log(n))

Sümmeetriline läbimine

Läbimine - iga puu sõlme külastamine, et teha selle kohta mingisugune toiming.

Rekursiivse sümmeetrilise läbimise algoritm:

1. Teha toiming vasaku lapsega
2. Teha toiming iseendaga
3. Teha toiming parema lapsega

Kood:

    public void inOrder(Node current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Siin võib olla kõik, mis tahes
            inOrder(current.getRightChild());
        }
    }

Kokkuvõte

Lõpuks! Kui ma midagi piisavalt ei selgitanud või kui on mingeid märkusi, ootan kommentaarides. Nagu lubatud, jagan täismahus 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) tasemele

Paljud teist on ehk märganud: mis oleks, kui teha puust tasakaalustamata? Näiteks paigutada puusse sõlmed, millel on kasvavad võtmed: 1, 2, 3, 4, 5, 6... Siis hakkab puu meenutama seotud loendit. Jah, puu kaotab oma puulaadse struktuuri ja seega ka andmete juurdepääsu efektiivsuse. Otsingu, sisestamise, kustutamise operatsioonide keerukus muutub sarnaseks seotud loendi omaga: O(n). See on üks peamine puudus, mida ma arvan, et binaarsetel puudel on.

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

Ma olen hiljuti Habr's ja tahaksin teada, milliseid teemasid sooviksite rohkem näha?

• Andmestruktuurid

• Algoritmid (Dünaamiline Programmeerimine, rekursioon, andmete kokkusurumine jne)

• Andmestruktuuride ja algoritmide rakendamine reaalses elus

• Androidi rakenduste programmeerimine Java's

• Veebirakenduste programmeerimine Java's

Hääletas 2 kasutajat. 1 kasutaja hoidus.

Allikas: habr.com