Binary Tree jeb kā pagatavot bināro mežu meklēšanai

Priekšvārds

Šis raksts ir veltīts binārajiem mežiem meklēšanai. Nesen veicu rakstu par datu saspiešanu, izmantojot Huffmaņa metodi. Tur es īpaši nepievēršu uzmanību binārajiem mežiem, jo meklēšanas, ievietošanas un dzēšanas metodes nebija aktuālas. Tagad esmu nolēmis uzrakstīt rakstu tieši par kokiem. Sāksim.

Koks — datu struktūra, kas sastāv no mezgliem, kas savienoti ar malām. Var teikt, ka koks ir grafētiskas struktūras īpašs gadījums. Lūk, koka piemērs:

Tas nav binārais mežs! Visi zem katras sadaļas!

Terminoloģija

Sakne

Koka sakne ir augstākais mezgls. Šajā piemērā tas ir mezgls A. Koks no saknes uz jebkuru citu mezglu var novest tikai pa vienu ceļu! Patiesībā jebkuru mezglu var uzskatīt par sakni atbilstošajam tā mezglam apakškokam.

Vecāki/pēcnācēji

Visiem mezgliem, izņemot sakni, ir tieši viena mala, kas ved uz citu mezglu. Mezgla, kas atrodas virs pašreizējā, nosaukums ir vecāks šī mezgla. Mezgla, kas atrodas zem pašreizējā un savienots ar to, nosaukums ir pēcnācējs šī mezgla. Apskatīsim piemēru. Ja ņemam mezglu B, tad tā vecāks būs mezgls A, bet pēcnācēji — mezgli D, E un F.

Lapa

Mezgla, kuram nav pēcnācēju, nosaukums būs koka lapa. Šajā piemērā lapas būs mezgli D, E, F, G, I, J, K.

Tā ir pamatterminoloģija. Citi jēdzieni tiks apskatīti vēlāk. Tātad, binārais koks ir koks, kurā katram mezglam ir ne vairāk kā divi pēcnācēji. Kā jūs varējāt uzminēt, piemērā esošais koks nebūs binārs, jo mezgliem B un H ir vairāk nekā divi pēcnācēji. Lūk, binārā koka piemērs:

Kokos var būt jebkāda informācija. Binārais mežs meklēšanai ir binārais koks, kuram raksturīgas šādas īpašības:

1. Abi apakškoki — kreisais un labais — ir binārie meži meklēšanai.
2. Visiem mezgliem kreisajā apakškokā noteiktajam mezglam X datu atslēgu vērtības ir mazākas nekā datu atslēgas vērtība pašam mezglam X.
3. Visiem mezgliem labajā apakškokā noteiktajam mezglam X datu atslēgu vērtības ir lielākas vai vienādas ar datu atslēgas vērtību pašam mezglam X.

Atslēga — kāda mezgla īpašība (piemēram, skaitlis). Atslēga ir nepieciešama, lai varētu atrast koka elementu, kuram atbilst šī atslēga. Binārā meža meklēšanas piemērs:

Koka attēlojums

Iesākot ceļu, es sniegšu dažus (iespējams, nepilnīgus) koda fragmentus, lai uzlabotu jūsu izpratni. Pilnais kods būs raksta beigās.

Koks sastāv no mezgliem. Mezgla struktūra:

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;
    }
//...pārējās mezgla metodes
}

Katram mezglam ir divi pēcnācēji (ļoti iespējams, ka ļaudis leftChild un vai rightChild saturēs vērtību null). Jūs, iespējams, sapratāt, ka šajā gadījumā data — ir dati, kas glabājas mezglā; key — ir mezgla atslēga.

Mezglu esam apskatījuši, tagad runāsim par aktuālām problēmām saistībā ar kokiem. Šeit un turpmāk ar vārdu „koks” es sapratīšu binārā meža koncepciju. Binārā meža struktūra:

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

    //koka metodes
}

Kā kādas klases lauku mēs izmantosim tikai koka sakni, jo no saknes ar metožu getLeftChild() un getRightChild() palīdzību var nokļūt pie jebkura koka mezgla.

Algoritmi kokā

Meklēšanai

Pieņemsim, ka jums ir izveidots koks. Kā atrast elementu ar atslēgu key? Jāvirzās no saknes uz leju pa koku un jāsalīdzina key vērtība ar attiecīgā mezgla atslēgu: ja key ir mazāks par attiecīgā mezgla atslēgu, jāpāriet uz kreiso pēcnācēju, ja lielāks — uz labo, ja atslēgas ir vienādas — meklētais mezgls ir atrasts! Atbilstošais kods:

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

Ja current kļūst vienāds ar null, tas nozīmē, ka pārlūkošana ir sasniegusi koka galu (konceptuālā līmenī jūs atrodaties neesošā koka vietā — lapu pēcnācējā).

Apskatīsim meklēšanas algoritma efektivitāti sabalansētā kokā (kokā, kur mezgli ir sadalīti apmēram vienmērīgi). Tādā gadījumā meklēšanas efektivitāte būs O(log(n)), ņemot vērā logaritmu ar pamatu 2. Skatieties: ja sabalansētā kokā ir n elementi, tas nozīmē, ka būs log(n) ar pamatu 2 līmeņu koka. Un meklēšanā, viens cikla solis ir vienas līmeņa nokāpums.

Ievietošana

Ja, ja varat saprast meklēšanas būtību, ievietošana neradīs lielas grūtības. Jums vienkārši jānokāpj līdz koka lapai (saskaņā ar meklēšanā aprakstītajiem nolaišanās noteikumiem) un jāstājas tās pēcnācēju vietā – kreisajā vai labajā, atkarībā no atslēgas. Realizācija:

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

Šajā gadījumā ir jāuztur informācija ne tikai par pašreizējo mezglu, bet arī par pašreizējā mezgla vecāku. Kad current kļūs par null, mainīgajā parent būs nepieciešamā lapa.
Ievietošanas efektivitāte, acīmredzot, būs tāda pati kā meklēšanai – O(log(n)).

Dzēst

Dzēšana ir visgrūtākā operācija, kas jāveic ar koku. Ir skaidrs, ka vispirms jāatrod elements, kuru mēs grasāmies dzēst. Bet kas pēc tam? Ja vienkārši piešķiram tā atsaucē vērtību null, mēs zaudējam informāciju par apakškoku, kura sakne ir šis mezgls. Koku dzēšanas metodes dalās trīs gadījumos.

Pirmais gadījums. Dzēšamais mezgls nav pēcnācēju.

Ja dzēšamais mezgls nav pēcnācēju, tas nozīmē, ka tas ir lapa. Tātad, vienkārši varam piešķirt saviem vecākiem poliem leftChild vai rightChild vērtību null.

Otrais gadījums. Dzēšamais mezgls ir viens pēcnācējs.

Šis gadījums arī nav ļoti sarežģīts. Atgriezīsimies pie mūsu piemēra. Pieņemsim, ka jādzen dzēšams elements ar atslēgu 14. Piekrītiet, ka tā kā tas ir labais pēcnācējs mezglam ar atslēgu 10, jebkuram tā pēcnācējam (šajā gadījumā labajam) būs atslēga, kas ir lielāka par 10, tāpēc to var viegli "izgriezt" no koka, un vecāku tieši savienot ar dzēstā mezgla pēcnācēju, t.i., mezglu ar atslēgu 10 savienot ar mezglu 13. Līdzīga situācija būtu, ja jums vajadzētu dzēst mezglu, kas ir sava vecāka kreisais pēcnācējs. Pārdomājiet to paši – precīza analoģija.

Trešais gadījums. Mezgls ir divi pēcnācēji.

Visnopietnākais gadījums. Apskatīsim uz jauna piemēra.

Mantojuma meklēšana

Pieņemsim, ka jāizdzēš mezgls ar atslēgu 25. Kadu liksim tā vietā? Kāds no tā sekotājiem (pēcnācējiem vai tā pēcnācēju pēcnācējiem) jābūt pēctecim(tas, kurš aizņems izdzēstā mezgla vietu).

Kā saprast, kuram jābūt pēctecim? Intuitīvi ir skaidrs, ka tas ir mezgls kokā, kura atslēga ir nākamā lielākā pēc izdzēstā mezgla. Algoritms ir šāds. Jāiet uz tā labā pēcnācēja (vienmēr uz labā, jo jau tika teikts, ka pēcteča atslēga ir lielāka par izdzēstā mezgla atslēgu), un pēc tam jāiet pa kreiso pēcnācēju ķēdi šim labajam pēcnācējam. Piemērā mums jāpāriet uz mezglu ar atslēgu 35, un tad jāiet uz leju pa kreiso pēcnācēju ķēdi – šajā gadījumā šī ķēde sastāv tikai no mezgla ar atslēgu 30. Strikti runājot, mēs meklējam mazāko mezglu kopā mezglu, kas ir lielāki par meklēto mezglu.

Pēcteča meklēšanas metodes kods:

    public Node<T> getSuccessor(Node<T> deleteNode) {
        Node<T> parentSuccessor = deleteNode; //pēcteča vecāks
        Node<T> successor = deleteNode; //pēctecis
        Node<T> current = successor.getRightChild(); //vienkārši "pārvietojamais" mezgls
        while (current != null) {
            parentSuccessor = successor;
            successor = current;
            current = current.getLeftChild();
        }
        //iznākot no cikla, iegūstam pēcteča un pēcteča vecāku
        if (successor != deleteNode.getRightChild()) { //ja pēctecis nesakrīt ar izdzēstā mezgla labajā pēcnācējā
            parentSuccessor.setLeftChild(successor.getRightChild()); //tad tā vecāks paņem sev pēcteča pēcnācēju, lai to nezaudētu
            successor.setRightChild(deleteNode.getRightChild()); //saistām pēcteča ar izdzēstā mezgla labajiem pēcnācējiem
        }
        return successor;
    }

Pilnīgais dzēšanas metodes kods:

public boolean delete(int deleteKey) {
        Node current = root;
        Node parent = current;
        boolean isLeftChild = false; // Atkarībā no tā, vai dzēšamais mezgls ir kreisais vai labais bērns, loģiskā mainīgā isLeftChild vērtība būs true vai false attiecīgi.
        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) { // pirmais gadījums
            if (current == root)
                current = null;
            else if (isLeftChild)
                parent.setLeftChild(null);
            else
                parent.setRightChild(null);
        }
        else if (current.getRightChild() == null) { // otrais gadījums
            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šais gadījums
            Node successor = getSuccessor(current);
            if (current == root)
                root = successor;
            else if (isLeftChild)
                parent.setLeftChild(successor);
            else
                parent.setRightChild(successor);
        }
        return true;
    }

Sarežģītību var aproksimēt līdz O(log(n)).

Maksimālās/minimālās vērtības meklēšana kokā

Acīmredzami, kā atrast minimālo/maksimālo vērtību kokā — ir jādodas secīgi pa kreisajiem/labajiem koka elementiem attiecīgi; kad sasniegsiet lapu, tā būs minimālā/maksimālā vērtība.

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

Sarežģītība — O(log(n))

Simetriska pārvietošanās

Pārvietošanās — katra koka mezgla apmeklēšana ar mērķi veikt kādu darbību ar to.

Rekurīvās simetriskās pārvietošanās algoritms:

1. Veikt darbību ar kreiso bērnu
2. Veikt darbību ar sevi
3. Veikt darbību ar labo bērnu

Kods:

    public void inOrder(Node current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Šeit var būt viss, kas vien vēlas
            inOrder(current.getRightChild());
        }
    }

Secinājums

Beidzot! Ja es kaut ko neizskaidroju vai ja ir kādi komentāri, gaidu tos komentāros. Kā solīts, šeit ir pilnais kods.

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.

Izsistēšana līdz O(n)

Daudzi no jums, iespējams, ir pamanījuši: ko darīt, lai koks kļūtu nesabalansēts? Piemēram, ievietojot kokā mezglus ar pieaugošām atslēgām: 1,2,3,4,5,6… Šādā gadījumā koks nedaudz atgādinās saistīto sarakstu. Un jā, koks zaudēs savu koka struktūru, tāpēc arī datu piekļuves efektivitāti. Meklēšanas, ievietošanas un dzēšanas operāciju sarežģītība kļūs tāda pati kā saistītajā sarakstā: O(n). Tas ir viens no svarīgākajiem, manuprāt, bināro koku trūkumiem.

Tikai reģistrētie lietotāji var piedalīties aptaujā. Pieteikties, lūdzu.

Es pavisam nesen esmu uz Habr, un vēlos uzzināt, par kādām tēmām jūs vēlētos redzēt vairāk rakstu?

• Datu struktūras

• Algoritmi (DP, rekursija, datu saspiestšana utt.)

• Datu struktūru un algoritmu pielietojums reālajā dzīvē

• Android lietotņu programmēšana Java valodā

• Web lietotņu programmēšana Java valodā

Balsu nodeva 2 lietotāji. Atturējās 1 lietotājs.

Avots: habr.com