🥇Binary Tree alebo ako pripraviť binárny strom vyhľadávania

Prelude

Tento článok sa zaoberá binárnymi stromami vyhľadávania. Nedávno som robil článok o kompresii dát metódou Huffmana. Tam som sa veľmi nezameriaval na binárne stromy, pretože metódy vyhľadávania, vkladania a odstraňovania neboli aktuálne. Teraz som sa rozhodol napísať článok presne o stromoch. Asi začneme.

Strom je dátová štruktúra pozostávajúca z uzlov, spojených hranami. Môžeme povedať, že strom je osobitný prípad grafu. Tu je príklad stromu:

Toto nie je binárne vyhľadávacie strom! Všetko pod kat!

Terminológia

Korene

Koreň stromu je najvyšší uzol. V príklade je to uzol A. V strome od koreňa k akémukoľvek inému uzlu môže viesť len jedna cesta! V skutočnosti sa akýkoľvek uzol dá považovať za koreň príslušného podstromu.

Rodičia/potomkovia

Všetky uzly okrem koreňového majú presne jednu hranu, vedúcu nahor k inému uzlu. Uzol, nachádzajúci sa nad aktuálnym, sa nazýva rodičom tohto uzla. Uzol, nachádzajúci sa pod aktuálnym a spojený s ním, sa nazýva potomkom tohto uzla. Pozrime sa na príklad. Vezmeme uzol B, jeho rodičom bude uzol A a potomkami budú uzly D, E a F.

List

Uzol, ktorý nemá potomkov, sa nazýva listom stromu. V príklade sú listami uzly D, E, F, G, I, J, K.

Toto je základná terminológia. Ďalšie pojmy budú podrobne vysvetlené neskôr. Takže binárny strom je strom, v ktorom má každý uzol najviac dvoch potomkov. Ako ste sa asi už domysleli, strom z príkladu nebude binárny, pretože uzly B a H majú viac ako dvoch potomkov. Tu je príklad binárneho stromu:

V uzloch stromu môže byť akákoľvek informácia. Binárny vyhľadávací strom je binárny strom, ktorého charakteristické vlastnosti sú nasledujúce:

Oba podstromy — ľavý a pravý — sú binárnymi vyhľadávacími stromami.
Všetky uzly ľavého podstromu akéhokoľvek uzla X majú hodnoty kľúčových údajov menšie než hodnota kľúča samotného uzla X.
Všetky uzly pravého podstromu akéhokoľvek uzla X majú hodnoty kľúčových údajov väčšie alebo rovné než hodnota kľúča samotného uzla X.

Parameter nejaká charakteristika uzla (napríklad číslo). Kľúč je potrebný na to, aby bolo možné nájsť prvok stromu, ktorý zodpovedá tomuto kľúču. Príklad binárneho vyhľadávacieho stromu:

Zobrazenie stromu

Ako budete pokračovať, prinesiem niektoré (možno neúplné) útržky kódu, aby som zlepšil vaše porozumenie. Kompletný kód bude na konci článku.

Strom sa skladá z uzlov. Štruktúra uzla:

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;
    }
//...ostatné metódy uzla
}

Každý uzol má dvoch potomkov (je možné, že potomkovia leftChild a/alebo rightChild budú mať hodnotu null). Určite ste pochopili, že v tomto prípade číslo data — údaje uložené v uzle; key — kľúč uzla.

S uzlom máme jasno, teraz sa porozprávajme o aktuálnych problémoch stromov. Tu a ďalej pod pojmom "strom" budem rozumieť pojem binárneho vyhľadávacieho stromu. Štruktúra binárneho stromu:

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

    //metódy stromu
}

Ako pole triedy nám bude potrebný len koreň stromu, pretože od koreňa pomocou metód getLeftChild() a getRightChild() sa dá dostať ku akémukoľvek uzlu stromu.

Algoritmy v strome

Hľadanie

Predpokladajme, že máte postavený strom. Ako nájsť prvok s kľúčom key? Je potrebné postupne sa pohybovať od koreňa smerom dole po strome a porovnávať hodnotu key s kľúčom aktuálneho uzla: ak je key menší ako kľúč aktuálneho uzla, prejdite k ľavému potomkovi uzla, ak je väčší — k pravému, ak sú kľúče rovné — požadovaný uzol je nájdený! Prislúchajúci kód:

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

Ak current sa stáva rovný null, znamená to, že preverenie dosiahlo koniec stromu (na konceptuálnej úrovni sa nachádzate na neexistujúcom mieste stromu — potomkovi listu).

Zvážme efektivitu vyhľadávacieho algoritmu na vyváženom strome (strome, v ktorom sú uzly rozložené viac-menej rovnomerne). Potom efektivita vyhľadávania bude O(log(n)), pričom logaritmus je so základom 2. Pozrite: ak je v vyváženom strome n prvkov, znamená to, že bude log(n) so základom 2 úrovní stromu. A pri vyhľadávaní, za jeden krok cyklu, zostupujete na jednu úroveň.

Vloženie

Ak ste pochopili podstatu vyhľadávania, potom pre vás nebude problém pochopiť vkladanie. Stačí len zostúpiť na list stromu (podľa pravidiel zostupu popísaných vo vyhľadávaní) a stať sa jeho potomkom - ľavým alebo pravým, v závislosti od kľúča. Realizácia:

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

V tomto prípade je potrebné okrem aktuálneho uzla uchovávať informácie o rodičovi aktuálneho uzla. Keď current dosiahne hodnotu null, v premennej parent bude ležať potrebný list.
Účinnosť vkladania bude zjavne rovnaká ako pri vyhľadávaní — O(log(n)).

Odstránenie

Vymazanie je najzložitejšia operácia, ktorú bude potrebné vykonať so stromom. Je jasné, že najprv bude potrebné nájsť prvok, ktorý chceme odstrániť. Ale čo potom? Ak jednoducho pridelíme jeho odkazu hodnotu null, stratíme informácie o podstrome, ktorého koreňom je tento uzol. Metódy odstraňovania stromu rozdeľujeme na tri prípady.

Prvý prípad. Odstraňovaný uzol nemá potomkov.

Ak odstraňovaný uzol nemá potomkov, znamená to, že je to list. Preto je možné priradiť poliam leftChild alebo rightChild jeho rodiča hodnotu null.

Druhý prípad. Odstraňovaný uzol má jedného potomka.

Tento prípad nie je tiež veľmi zložitý. Vráťme sa k nášmu príkladu. Predpokladajme, že treba odstrániť prvok s kľúčom 14. Súhlasíte, že keďže je to pravý potomok uzla s kľúčom 10, akýkoľvek jeho potomok (v tomto prípade pravý) bude mať kľúč väčší ako 10, preto ho môžeme ľahko „vyradiť“ zo stromu a rodiča pripojiť priamo k potomkovi odstraňovaného uzla, t.j. uzol s kľúčom 10 pripojiť k uzlu 13. Podobná by bola situácia, keby sme mali odstrániť uzol, ktorý je ľavým potomkom svojho rodiča. Zamyslite sa nad tým sami — presná analógia.

Tretí prípad. Uzol má dvoch potomkov.

Najzložitejší prípad. Rozoberieme na novom príklade.

Hľadanie nástupcu.

Povedzme, že chceme odstrániť uzol s kľúčom 25. Kto zaberie jeho miesto? Niekto z jeho následníkov (potomkov alebo potomkov potomkov) by sa mal stať nástupcom(tým, kto zaujme miesto odstráneného uzla).

Ako zistiť, kto by mal byť nástupcom? Intuitívne je jasné, že ide o uzol v strome, ktorého kľúč je najbližší vyšší k odstránenému uzlu. Algoritmus spočíva v nasledujúcom. Musíme prejsť k jeho pravému potomkovi (vždy k pravému, pretože už bolo povedané, že kľúč nástupcu je väčší ako kľúč odstráneného uzla) a potom prejsť reťazcom ľavých potomkov tohto pravého potomka. V príklade musíme prejsť k uzlu s kľúčom 35 a potom postupovať nadol po reťazci jeho ľavých potomkov — v tomto prípade sa reťazec skladá len z uzla s kľúčom 30. Stricto sensu, hľadáme najmenej uzol v množine uzlov, ktoré sú väčšie ako hľadaný uzol.

Kód metódy vyhľadávania nástupcu:

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode; // rodič nástupcu
        Node<T> successor = deleteNode; // nástupca
        Node<T> current = successor.getRightChild(); // prostý "bežiaci" uzol
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        // na výstupe z cyklu máme nástupcu a rodiča nástupcu
        if (successor != deleteNode.getRightChild()) { // ak sa nástupca nezhoduje s pravým potomkom odstraňovaného uzla
            parentSuccessor.setLeftChild(successor.getRightChild()); // potom jeho rodič vezme potomka nástupcu, aby ho nestratil
            successor.setRightChild(deleteNode.getRightChild()); // spojíme nástupcu s pravým potomkom odstraňovaného uzla
        }
        return successor;
    }

Úplný kód metódy delete:

public boolean delete(int deleteKey) {
        Node current = root;
        Node parent = current;
        boolean isLeftChild = false; // V závislosti od toho, či je mazaný uzol ľavým alebo pravým potomkom svojho rodiča, boolean premenna isLeftChild bude mať hodnotu true alebo 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) { // prvý prípad
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) { // druhý prípad
            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 { // tretí prípad
            Node successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

Zložitost môže byť aproximovaná na O(log(n)).

Hľadanie maxima/minima v strome

Je zrejmé, ako nájsť minimálnu/maximálnu hodnotu v strome — treba postupne prechádzať po reťazci ľavých/pravých prvkov stromu; keď sa dostanete k listu, ten bude minimálnym/maximálnym prvkom.

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

Zložitost — O(log(n))

Symetrický prechod

Prechod — návšteva každého uzla stromu s cieľom vykonať s ním nejakú akciu.

Algoritmus rekurzívneho symetrického prechodu:

Urobiť akciu s ľavým potomkom
Urobiť akciu so sebou
Urobiť akciu s pravým potomkom

Kód:

    public void inOrder(Node current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Tu môže byť čokoľvek
            inOrder(current.getRightChild());
        }
    }

Záver

Konečne! Ak som niečo nedostatočne vysvetlil alebo máte nejaké pripomienky, čakám na komentároch. Ako som sľúbil, prinášam kompletný kód.

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.

Zrútenie na O(n)

Mnohí z vás si mohli všimnúť: a čo ak by sme urobili, aby sa strom stal nevyváženým? Napríklad, ak by sme do stromu vkladali uzly s rastúcimi kľúčmi: 1,2,3,4,5,6… Potom bude strom pripomínať prepojený zoznam. A áno, strom stratí svoju stromovú štruktúru, a tým aj efektívnosť prístupu k údajom. Zložitosti operácií vyhľadávania, vkladania a odstraňovania sa stanú rovnakými, ako pri prepojených zoznamoch: O(n). V tom sa prejavuje jeden z najdôležitejších nedostatkov binárnych stromov, podľa môjho názoru.

Len registrovaní používatelia sa môžu zúčastniť prieskumu. Prihláste sa, prosím.