ProHoster > Blog > uprava > Binarno stablo ili kako pripremiti binarno stablo pretraživanja

Binarno stablo ili kako pripremiti binarno stablo pretraživanja

uvod

Ovaj članak govori o stablima binarnog pretraživanja. Nedavno sam napisao članak o kompresija podataka Huffmanovom metodom. Tu nisam baš obraćao pozornost na binarna stabla, jer metode pretraživanja, umetanja, brisanja nisu bile relevantne. Sada sam odlučio napisati članak o drveću. Možda ćemo početi.

Stablo je podatkovna struktura 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 binarno stablo pretraživanja! Sve je pod rezom!

terminologija

korijen

Korijen stabla je najviši čvor. U primjeru je to čvor A. U stablu samo jedan put može voditi od korijena do bilo kojeg drugog čvora! Zapravo, bilo koji čvor se može smatrati korijenom podstabla koje odgovara tom čvoru.

Roditelji/potomci

Svi čvorovi osim korijena imaju točno jedan rub koji vodi do drugog čvora. Poziva se čvor iznad trenutnog čvora roditelj ovaj čvor. Poziva se čvor koji se nalazi ispod trenutnog i povezan je s njim potomak ovaj čvor. Uzmimo primjer. Uzmite čvor B, tada će njegov roditelj biti čvor A, a djeca će biti čvorovi D, E i F.

list

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

Ovo je osnovna terminologija. O ostalim konceptima bit će riječi kasnije. Dakle, binarno stablo je stablo u kojem svaki čvor neće imati više od dva djeteta. Kao što ste pogodili, 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 binarna stabla pretraživanja.
  2. Svi čvorovi lijevog podstabla proizvoljnog čvora X imaju vrijednosti podatkovnog ključa manje od vrijednosti podatkovnog ključa samog čvora X.
  3. Svi čvorovi desnog podstabla proizvoljnog čvora X imaju vrijednosti podatkovnog ključa veće ili jednake vrijednosti podatkovnog ključa samog čvora X.

ključ - neka karakteristika čvora (na primjer, broj). Ključ je potreban kako bi se mogao pronaći element stabla kojem taj ključ odgovara. Primjer stabla binarnog pretraživanja:

Binarno stablo ili kako pripremiti binarno stablo pretraživanja

prikaz stabla

Usput ću uključiti neke (možda 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;
    }
//...остальные методы узла
}

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

Shvatili smo čvor, sada razgovarajmo o gorućim problemima oko drveća. U nastavku će riječ "stablo" označavati 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, korištenjem metoda getLeftChild() i getRightChild(), možete doći do bilo kojeg čvora stabla.

Algoritmi stabla

Traženje

Recimo da imate izgrađeno stablo. Kako pronaći element s ključnim ključem? Morate se uzastopno kretati od korijena niz stablo i usporediti vrijednost ključa s ključem sljedećeg čvora: ako je ključ manji od ključa sljedećeg čvora, idite na lijevog potomka čvora, ako je više - desno, ako su ključevi jednaki - pronađen je željeni čvor! 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 nula, tada je iteracija dosegla kraj stabla (na konceptualnoj razini, nalazite se na nepostojećem mjestu u stablu - dijete lista).

Razmotrite učinkovitost algoritma pretraživanja na uravnoteženom stablu (stablo u kojem su čvorovi raspoređeni više ili manje ravnomjerno). Tada će učinkovitost pretraživanja biti O(log(n)), a logaritam s bazom 2. Vidite: ako postoji n elemenata u uravnoteženom stablu, to znači da će postojati log(n) razina stabla s bazom 2. A u potrazi, za jedan korak u ciklusu, spustite se jednu razinu niže.

umetnuti

Ako ste shvatili bit pretrage, onda vam neće biti teško razumjeti umetanje. Samo se trebate spustiti na list stabla (prema pravilima silaska opisanim u pretrazi) i postati 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 ovom slučaju, osim trenutnog čvora, potrebno je pohraniti i podatke o roditelju trenutnog čvora. Kada struja postane null, nadređena varijabla će sadržavati list koji nam je potreban.
Učinkovitost umetanja će očito biti ista kao i kod pretraživanja - O(log(n)).

Uklanjanje

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 što onda? Ako njegovu referencu jednostavno postavimo na null, tada ćemo izgubiti informacije o podstablu čiji je korijen ovaj čvor. Metode uklanjanja drveća 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 list. Stoga možete jednostavno postaviti polja leftChild ili rightChild njegovog roditelja na null.

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

Ovaj slučaj također nije jako težak. Vratimo se našem primjeru. Pretpostavimo da trebamo izbrisati element s ključem 14. Složite se da budući da je to pravo dijete čvora s ključem 10, tada će bilo koji od njegovih potomaka (u ovom slučaju, onaj desni) imati ključ veći od 10, tako da može ga lako "izrezati" iz stabla i povezati roditelja izravno s podređenim čvorom koji se briše, tj. spojite čvor s ključem 10 na čvor 13. Situacija bi bila slična kada bismo morali izbrisati čvor koji je lijevi dijete svog roditelja. Razmislite sami – toč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

Potraga za nasljednikom

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

Kako znate tko 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. Trebate otići do njegovog desnog djeteta (uvijek do desnog, 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 lijevih potomaka ovog desnog dijete. U primjeru, moramo ići do čvora s ključem 35, a zatim ići niz lanac njegovih lijevih potomaka do lista - u ovom slučaju, ovaj se lanac 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 traženja 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;
    }

Potpuni 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čito, kako pronaći minimalnu / maksimalnu vrijednost u stablu - morate sekvencijalno proći kroz lanac lijevo / desno elemenata 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))

Simetrična premosnica

Traversal je posjet svakom čvoru stabla kako bi se s njim nešto učinilo.

Rekurzivni simetrični algoritam obilaska:

  1. Izvršite akciju na lijevom djetetu
  2. Napravite nešto sami sa sobom
  3. Poduzmite akciju na pravo dijete

Šifra:

    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, onda čekam u komentarima. Kao što je obećano, ovdje je kompletan kod.

Čvor.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: što ako stablo učinite neuravnoteženim? Na primjer, stavite čvorove u stablo s rastućim ključevima: 1,2,3,4,5,6... Tada će stablo pomalo podsjećati na povezanu listu. I da, stablo će izgubiti svoju strukturu stabla, a time i učinkovitost pristupa podacima. Složenost operacija pretraživanja, umetanja i brisanja postat će ista kao kod povezanog popisa: O(n). Ovo je, po mom mišljenju, jedan od najvažnijih nedostataka binarnih stabala.

U anketi mogu sudjelovati samo registrirani korisnici. Prijaviti se, molim.

Dugo nisam bio na Habréu i volio bih znati koje članke o kojim temama želite vidjeti više?

  • Strukture podataka

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

  • Primjena podatkovnih struktura i algoritama u stvarnom životu

  • Programiranje android aplikacija u Javi

  • Programiranje Java web aplikacija

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

Izvor: www.habr.com

Dodajte komentar