ProHoster > Блог > Administracija > Binarno stablo ili kako pripremiti binarno stablo pretraživanja

Binarno stablo ili kako pripremiti binarno stablo pretraživanja

Preludij

Ovaj članak je o stablima binarnog pretraživanja. Nedavno sam napisao članak o kompresiju podataka po Huffman metodi. Tu nisam baš obraćao pažnju na binarna stabla, jer metode traženja, umetanja, brisanja nisu bile relevantne. Sada sam odlučio napisati članak o drveću. Možda ćemo početi.

Stablo je struktura podataka koja se sastoji od čvorova povezanih rubovima. Možemo reći da je stablo poseban slučaj grafa. Evo primjera stabla:

Binarno stablo ili kako pripremiti binarno stablo pretraživanja

Ovo nije stablo binarnog pretraživanja! Sve je ispod reza!

Terminologija

Root

Koren drveta je najviši čvor. U primjeru, ovo je čvor A. U stablu, samo jedna staza može voditi od korijena do bilo kojeg drugog čvora! U stvari, bilo koji čvor se može smatrati korijenom podstabla koje odgovara ovom čvoru.

Roditelji/potomci

Svi čvorovi osim korijena imaju tačno jednu ivicu koja vodi do drugog čvora. Poziva se čvor iznad trenutnog čvora roditelj ovaj čvor. Poziva se čvor koji se nalazi ispod trenutnog i povezan s njim potomak ovaj čvor. Uzmimo primjer. Uzmimo čvor B, tada će mu roditelj biti čvor A, a potomci će biti čvorovi D, E i F.

List

Čvor koji nema djece naziva se list drveta. U primjeru, čvorovi D, E, F, G, I, J, K će biti listovi.

Ovo je osnovna terminologija. O ostalim konceptima će se govoriti kasnije. Dakle, binarno stablo je stablo u kojem svaki čvor neće imati više od dva djeteta. Kao što ste pretpostavili, stablo iz primjera neće biti binarno, jer čvorovi B i H imaju više od dva djeteta. Evo primjera binarnog stabla:

Binarno stablo ili kako pripremiti binarno stablo pretraživanja

Čvorovi stabla mogu sadržavati bilo koju informaciju. Binarno stablo pretraživanja je binarno stablo koje ima sljedeća svojstva:

  1. I lijevo i desno podstablo su binarno stablo pretraživanja.
  2. Svi čvorovi lijevog podstabla proizvoljnog čvora X imaju vrijednosti ključa podataka manje od vrijednosti ključa podataka samog čvora X.
  3. Svi čvorovi desnog podstabla proizvoljnog čvora X imaju vrijednosti ključa podataka veće ili jednake vrijednosti ključa podataka samog čvora X.

Ključ - neke karakteristike čvora (na primjer, broj). Ključ je potreban da bi se mogao pronaći element stabla kojem ovaj ključ odgovara. Primjer stabla binarnog pretraživanja:

Binarno stablo ili kako pripremiti binarno stablo pretraživanja

pogled na drvo

U nastavku ću uključiti neke (možda nepotpune) dijelove koda kako bih poboljšao vaše razumijevanje. Cijeli kod će biti 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;
    }
//...остальные методы узла
}

Svaki čvor ima dva djeteta (sasvim je moguće da će djeca leftChild i/ili rightChild biti null). Vjerovatno ste shvatili da su u ovom slučaju podaci o broju podaci pohranjeni u čvoru; ključ - ključ čvora.

Shvatili smo čvor, a sada razgovarajmo o gorućim problemima drveća. Ovdje i ispod, riječ "stablo" će značiti koncept binarnog stabla pretraživanja. Struktura binarnog stabla:

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

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

Kao polje klase, potreban nam je samo korijen stabla, jer iz korijena, koristeći metode getLeftChild() i getRightChild(), možete doći do bilo kojeg čvora stabla.

Algoritmi stabla

Поиск

Recimo da imate izgrađeno drvo. Kako pronaći element sa ključem? Morate se uzastopno pomicati od korijena niz stablo i usporediti vrijednost ključa sa ključem sljedećeg čvora: ako je ključ manji od ključa sljedećeg čvora, onda idite na lijevog potomka čvora, ako je više - desno, ako su ključevi jednaki - željeni čvor je pronađen! Relevantni 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 struja postane null, onda je iteracija stigla do kraja stabla (na konceptualnom nivou, vi ste na nepostojećem mjestu u stablu - dijete lista).

Razmotrite efikasnost algoritma pretraživanja na uravnoteženom stablu (stablo u kojem su čvorovi raspoređeni manje-više ravnomjerno). Tada će efikasnost pretraživanja biti O(log(n)), a logaritam baze 2. Vidite: ako postoji n elemenata u balansiranom stablu, onda to znači da će postojati log(n) baza 2 nivoa stabla. I u potrazi, za jedan korak ciklusa, spuštate se za jedan nivo.

umetnuti

Ako ste shvatili suštinu pretrage, onda vam neće biti teško razumjeti umetanje. Samo treba da se spustite do lista drveta (prema pravilima spuštanja opisanim u pretrazi) i postanete njegov potomak - lijevo ili desno, ovisno o ključu. Implementacija:

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

U tom slučaju, pored trenutnog čvora, potrebno je pohraniti i podatke o roditelju trenutnog čvora. Kada current postane null, roditeljska varijabla će sadržavati list koji nam je potreban.
Efikasnost umetanja će očigledno biti ista kao i kod pretrage - O(log(n)).

Brisanje

Brisanje je najsloženija operacija koja će se morati obaviti sa stablom. Jasno je da će prvo biti potrebno pronaći element koji ćemo ukloniti. Ali šta onda? Ako jednostavno postavimo njegovu referencu na null, tada ćemo izgubiti informacije o podstablu čiji je korijen ovaj čvor. Metode uklanjanja stabala podijeljene su u tri slučaja.

Prvi slučaj. Čvor koji treba ukloniti nema djece.

Ako čvor koji se briše nema djece, to znači da je to list. Stoga, možete jednostavno postaviti leftChild ili rightChild polja njegovog roditelja na null.

Drugi slučaj. Čvor koji treba ukloniti ima jedno dijete

Ovaj slučaj takođe nije mnogo težak. Vratimo se na naš primjer. Pretpostavimo da treba da izbrišemo element sa ključem 14. Slažete se da, pošto je to pravo dete čvora sa ključem 10, onda će bilo koji od njegovih potomaka (u ovom slučaju, desni) imati ključ veći od 10, tako da može ga lako „isjeći“ iz stabla, i povezati roditelja direktno na dijete čvora koji se briše, tj. povežite čvor sa ključem 10 sa čvorom 13. Situacija bi bila slična kada bismo morali da izbrišemo čvor koji je levo dete njegovog roditelja. Razmislite o tome sami - tačna analogija.

Treći slučaj. Node ima dvoje djece

Najteži slučaj. Pogledajmo novi primjer.

Binarno stablo ili kako pripremiti binarno stablo pretraživanja

Potražite nasljednika

Recimo da moramo ukloniti čvor sa ključem 25. Koga ćemo staviti na njegovo mjesto? Jedan od njegovih sljedbenika (potomci ili potomci potomaka) mora postati naslednik(onaj koji će zauzeti mjesto uklonjenog čvora).

Kako znate ko bi trebao biti nasljednik? Intuitivno, ovo je čvor u stablu čiji je ključ sljedeći najveći od čvora koji se uklanja. Algoritam je sljedeći. Treba ići na njegovo desno dijete (uvijek na desno, jer je već rečeno da je ključ nasljednika veći od ključa čvora koji se briše), a zatim proći kroz lanac lijeve djece ovog desnog dijete. U primjeru, moramo ići do čvora s ključem 35, a zatim se spustiti niz lanac njegovih lijeve djece do lista - u ovom slučaju, ovaj lanac se sastoji samo od čvora s ključem 30. Strogo govoreći, tražimo najmanji čvor u skupu čvorova veći od željenog čvora.

Binarno stablo ili kako pripremiti binarno stablo pretraživanja

Kod metode pretraživanja nasljednika:

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

Kompletan kod metode brisanja:

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

Složenost se može aproksimirati na O(log(n)).

Pronalaženje maksimuma/minimuma u stablu

Očigledno, kako pronaći minimalnu / maksimalnu vrijednost u stablu - morate uzastopno proći kroz lanac lijevog / desnog elementa stabla; kada dođete do lista, to će biti minimalni/maksimalni 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;
    }

Složenost - O(log(n))

Symmetric Bypass

Prelazak je posjeta svakom čvoru stabla kako bi se nešto uradilo s njim.

Rekurzivni simetrični algoritam obilaska:

  1. Napravite akciju na lijevom djetetu
  2. Napravite akciju sa sobom
  3. Napravite akciju na pravo dijete

Kod:

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

zaključak

Konačno! Ako nešto nisam objasnio ili imam komentare, čekam u komentarima. Kao što je obećano, evo kompletnog koda.

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

Degeneracija u O(n)

Mnogi od vas su možda primijetili: šta ako učinite da drvo postane neuravnoteženo? Na primjer, stavite čvorove u stablo sa povećavajućim ključevima: 1,2,3,4,5,6... Tada će stablo pomalo podsjećati na povezanu listu. I da, stablo će izgubiti strukturu stabla, a time i efikasnost pristupa podacima. Složenost operacija pretraživanja, umetanja i brisanja postat će ista kao kod povezane liste: O(n). Ovo je jedan od najvažnijih, po mom mišljenju, nedostataka binarnih stabala.

Samo registrovani korisnici mogu učestvovati u anketi. Prijavite semolim.

Nisam bio na Habré-u dosta dugo, a voleo bih da znam koje članke o kojim temama biste voleli da vidite više?

  • Strukture podataka

  • Algoritmi (DP, rekurzija, kompresija podataka, itd.)

  • Primjena struktura podataka i algoritama u stvarnom životu

  • Programiranje android aplikacija u Javi

  • Java programiranje web aplikacija

2 korisnika je glasalo. 1 korisnik je bio uzdržan.

Izvor: www.habr.com

Dodajte komentar