🥇Binarno stablo ili kako pripremiti binarno stablo pretraživanja

Preludij

Ovaj članak posvećen je binarnim stablima pretraživanja. Nedavno sam pisao članak o kompresiji podataka metodom Huffman. Tamo nisam previše obraćao pažnju na binarna stabla, jer metode pretraživanja, umetanja i brisanja nisu bile relevantne. Sad sam odlučio napisati članak upravo o stablima. Pa, da počnemo.

Stablo je struktura podataka koja se sastoji od čvorova povezanih granama. Može se reći da je stablo posebni slučaj grafa. Evo primera stabla:

To nije binarno stablo pretraživanja! Sve pod kat.

Terminologija

Korijen

Korijen stabla je njegov najgornji čvor. U primeru, to je čvor A. U stablu može postojati samo jedan put od korijena do bilo kojeg drugog čvora! U stvarnosti, svaki čvor se može smatrati korijenom odgovarajućeg podstabla.

Roditelji/ potomci

Svi čvorovi, osim korijena, imaju tačno jednu granju koja vodi prema drugom čvoru. Čvor koji se nalazi iznad trenutnog naziva se roditeljem ovog čvora. Čvor koji se nalazi ispod trenutnog i povezan je s njim, naziva se potomkom ovog čvora. Pogledajmo primer. Uzmimo čvor B, tada će njegov roditelj biti čvor A, a potomci će biti čvorovi D, E i F.

List

Čvor koji nema potomaka naziva se listem stabla. U primeru, listovi će biti čvorovi D, E, F, G, I, J, K.

Ovo je osnovna terminologija. Ostali pojmovi će biti razrađeni kasnije. Tako, binarno stablo je stablo u kojem svaki čvor može imati najviše dva potomka. Kako ste pogodili, stablo iz primera neće biti binarno, jer čvorovi B i H imaju više od dva potomka. Evo primera binarnog stabla:

U čvorovima stabla može se nalaziti bilo koja informacija. Binarno stablo pretraživanja je binarno stablo koje ima sledeće osobine:

Oba podstabla — levo i desno — su binarna stabla pretraživanja.
Svi čvorovi levog podstabla proizvoljnog čvora X imaju vrednosti ključeva podataka manje od vrednosti ključa podataka samog čvora X.
Svi čvorovi desnog podstabla proizvoljnog čvora X imaju vrednosti ključeva podataka veće ili jednake od vrednosti ključa podataka samog čvora X.

Ključ — neka karakteristika čvora (na primer, broj). Ključ je potreban kako bi se mogla pronaći stavka stabla kojoj odgovara taj ključ. Primer binarnog stabla pretraživanja:

Predstavljanje stabla

Kako napredujem, navest ću neke (moguće nepotpune) dijelove koda kako bih poboljšao vaše razumijevanje. Cijeli kod bit će na kraju članka.

Stablo se sastoji od čvorova. Struktura čvora:

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;
    }
//...ostali metodi čvora
}

Svaki čvor ima dva potomka (moguće je da potomci leftChild i/ili rightChild sadrže vrijednost null). Vjerojatno ste shvatili da u ovom slučaju data predstavlja podatke pohranjene u čvoru; key je ključ čvora.

O čvorovima smo razgovarali, sada razgovarajmo o hitnim problemima stabala. Ovdje i dalje pod pojmom „stablo“ mislim na pojam binarnog stabla pretraživanja. Struktura binarnog stabla:

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

    //metode stabla
}

Kao polje klase trebat će nam samo korijen stabla, jer se od korijena pomoću metoda getLeftChild() i getRightChild() može doći do bilo kojeg čvora stabla.

Algoritmi u stablu

Pretraživanje

Pretpostavimo da imate izgrađeno stablo. Kako pronaći element s ključem key? Trebate se postupno kretati od korijena prema dolje po stablu i uspoređivati vrijednost key s ključem trenutnog čvora: ako je key manji od ključa trenutnog čvora, pređite na lijevog potomka čvora, ako je veći — na desnog, ako su ključevi jednaki — traženi čvor je pronađen! Odgovarajući kod:

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

Ako current postane jednak null, to znači da je pretraga dostigla kraj stabla (na konceptualnoj razini nalazite se na nepostojećem mjestu stabla — potomku lista).

Razmotrimo učinkovitost algoritma pretraživanja na uravnoteženom stablu (stablo u kojem su čvorovi raspoređeni više-manje ravnomjerno). Tada će učinkovitost pretraživanja biti O(log(n)), pri čemu je logaritam na osnovi 2. Pogledajte: ako u uravnoteženom stablu ima n elemenata, to znači da će biti log(n) na osnovi 2 razina stabla. A u pretraživanju, za jedan korak petlje, silazite na jedan nivo.

Umetanje

Ako ste shvatili suštinu pretraživanja, onda vam umetanje neće biti teško. Samo se treba spustiti do lista stabla (prema pravilima spuštanja opisanima u pretraživanju) i postati njegov potomak — levi ili desni, u zavisnosti od ključa. Implementacija:

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

U ovom slučaju je potrebno, osim trenutnog čvora, čuvati informacije o roditelju trenutnog čvora. Kada current postane null, u varijabli parent će biti potrebni list.
Efikasnost umetanja, očigledno, biće ista kao i kod pretraživanja — O(log(n)).

Brisanje

Brisanje je najteža operacija koju treba sprovesti sa stablom. Jasno je da prvo treba pronaći element koji nameravamo da obrišemo. Ali šta onda? Ako jednostavno dodelimo njegovom referencu vrednost null, izgubićemo informacije o podstablu čiji je ovaj čvor koren. Metode brisanja stabla delimo u tri slučaja.

Prvi slučaj. Brišemo čvor koji nema potomaka

Ako brišemo čvor koji nema potomaka, to znači da je list. Stoga se jednostavno može dodeliti poljima leftChild ili rightChild njegovog roditelja vrednost null.

Drugi slučaj. Brišemo čvor koji ima jednog potomka

Ovaj slučaj takođe nije previše složen. Vratimo se našem primeru. Recimo da treba da obrišemo element sa ključem 14. Slažete se da, pošto je on desni potomak čvora sa ključem 10, bilo koji njegov potomak (u ovom slučaju desni) će imati ključ veći od 10, stoga ga možemo lako „izrezati“ iz stabla, a roditelja direktno povezati sa potomkom brišućeg čvora, tj. čvor sa ključem 10 povezati sa čvorom 13. Slična bi situacija bila da smo trebali obrisati čvor koji je levi potomak svog roditelja. Razmislite o tome sami — tačna analogija.

Treći slučaj. Čvor ima dva potomka

Najkompleksniji slučaj. Razradićemo to na novom primeru.

Pretraga naslednika

Pretpostavimo da trebamo ukloniti čvor s ključem 25. Koga ćemo postaviti na njegovo mjesto? Netko od njegovih sljedbenika (potomaka ili potomaka potomaka) trebao bi postati nasljednik(onaj tko zauzima mjesto uklonjenog čvora).

Kako shvatiti tko bi trebao postati nasljednik? Intuitivno je jasno da je to čvor u stablu čiji je ključ sljedeći veći od uklonjenog čvora. Algoritam se svodi na sljedeće. Trebamo prijeći na njegovog desnog potomka (uvijek na desnog, jer je već rečeno da je ključ nasljednika veći od ključa uklonjenog čvora), a zatim proći kroz lanac lijevih potomaka tog desnog potomka. U primjeru trebamo prijeći na čvor s ključem 35, a zatim se spustiti do lista kroz lanac njegovih lijevih potomaka — u ovom slučaju, taj lanac se sastoji samo od čvora s ključem 30. Strogo govoreći, tražimo najmanji čvor u skupu čvorova, većih od traženog čvora.

Kod metode pretraživanja nasljednika:

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode; // roditelj nasljednika
        Node<T> successor = deleteNode; // nasljednik
        Node<T> current = successor.getRightChild(); // samo "prolazni" čvor
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        // na izlazu iz petlje imamo nasljednika i roditelja nasljednika
        if (successor != deleteNode.getRightChild()) { // ako nasljednik nije isti kao desni potomak uklonjenog čvora
            parentSuccessor.setLeftChild(successor.getRightChild()); // tada njegov roditelj preuzima potomka nasljednika, da ga ne izgubi
            successor.setRightChild(deleteNode.getRightChild()); // povezujemo nasljednika s desnim potomkom uklonjenog čvora
        }
        return successor;
    }

Puni kod metode delete:

public boolean delete(int deleteKey) {
        Node current = root;
        Node parent = current;
        boolean isLeftChild = false; // Ovisno o tome je li čvor koji se uklanja lijevi ili desni potomak svog roditelja, booleanska varijabla isLeftChild će imati vrijednost true ili 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) { // prvi slučaj
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) { // drugi slučaj
            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 { // treći slučaj
            Node successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

Vrijednost složenosti može se aproksimirati na O(log(n)).

Pronalaženje maksimuma/minimuma u stablu

Očigledno je da se minimalna/maksimalna vrijednost u stablu može pronaći slijednim prelaskom kroz lanac lijevih/desnih elemenata stabla; kada stignete do lista, on će biti minimalni/maksimalni 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;
    }

Složenost — O(log(n))

Simetrično obilazak

Obilazak — posjetiti svaki čvor stabla s ciljem izvršenja neke radnje nad njim.

Algoritam za rekurzivni simetrični obilazak:

Izvrši radnju nad lijevim potomkom
Izvrši radnju nad sobom
Izvrši radnju nad desnim potomkom

Kod:

    public void inOrder(Node current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");// Ovdje može biti sve, što god
            inOrder(current.getRightChild());
        }
    }

Zaključak

Nap finally! Ako sam nešto nedovoljno objasnio ili imate kakve komentare, čekam vas u komentarima. Kao što sam obećao, donosim puni kod.

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.

Degeneracija do O(n)

Mnogi od vas mogli su primijetiti: što ako napravimo da stablo postane nesmetano? Na primjer, stavljajući u stablo čvorove s rastućim ključevima: 1,2,3,4,5,6… Tada će stablo više ličiti na povezanu listu. I da, stablo će izgubiti svoju drvenastu strukturu, a samim time i učinkovitost pristupa podacima. Složenost operacija pretrage, umetanja i brisanja postat će kao kod povezane liste: O(n). U tome se očituje jedan od najvažnijih, po mom mišljenju, nedostataka binarnih stabala.

Samo registrirani korisnici mogu sudjelovati u anketi. Prijavite se, molimo.