Binary Tree edo nola prestatu bitar bilaketa zuhaitz bat

Aurreskua

Artikulu hau bilaketa-zuhaitz bitarrei buruzkoa da. Duela gutxi artikulu bat idatzi dut Datuen konpresioa Huffman metodoaren bidez. Han ez nien benetan zuhaitz bitarrei erreparatu, bilatzeko, txertatzeko, ezabatzeko metodoak ez zirelako garrantzitsuak. Orain zuhaitzei buruzko artikulu bat idaztea erabaki nuen. Agian hasiko gara.

Zuhaitz bat ertz bidez konektatutako nodoz osatutako datu-egitura da. Zuhaitza grafiko baten kasu berezi bat dela esan dezakegu. Hona hemen zuhaitz adibide bat:

Hau ez da bilaketa-zuhaitz bitar bat! Dena mozketa azpian dago!

terminologia

erro

Zuhaitz sustraia goiko nodoa da. Adibidean, hau A nodoa da. Zuhaitzean, bide bakarrak eraman dezake errotik beste edozein nodora! Izan ere, edozein nodo har daiteke nodo honi dagokion azpizuhaitzaren errotzat.

Gurasoak/seme-alabak

Nodo guztiek erroa izan ezik beste nodo batera doan ertz bat dute. Uneko nodoaren gaineko nodoari deitzen zaio gurasoa nodo hau. Unekoaren azpian dagoen eta hari konektatuta dagoen nodo bati deitzen zaio ondorengoa nodo hau. Har dezagun adibide bat. Hartu B nodoa, orduan bere gurasoa A nodoa izango da eta bere seme-alabak D, E eta F nodoak izango dira.

xafla

Seme-alabarik ez duen nodoari zuhaitzaren hosto deitzen zaio. Adibidean, D, E, F, G, I, J, K nodoak hostoak izango dira.

Hau da oinarrizko terminologia. Beste kontzeptu batzuk geroago eztabaidatuko dira. Beraz, zuhaitz bitarra nodo bakoitzak bi seme-alaba baino gehiago izango dituen zuhaitza da. Asmatu duzun bezala, adibideko zuhaitza ez da bitarra izango, B eta H nodoek bi seme baino gehiago dituztelako. Hona hemen zuhaitz bitar baten adibide bat:

Zuhaitzaren nodoek edozein informazio eduki dezakete. Bilaketa-zuhaitz bitarra propietate hauek dituen zuhaitz bitarra da:

1. Ezkerreko eta eskuineko azpizuhaitzak bilaketa-zuhaitz bitarrak dira.
2. X nodo arbitrario baten ezkerreko azpizuhaitzaren nodo guztiek X nodoaren datu-gakoaren balioak baino txikiagoak dituzte.
3. X nodo arbitrario baten eskuineko azpizuhaitzaren nodo guztiek X nodoaren datu-gakoaren balio handiagoak edo berdinak dituzte.

gakoa - nodoaren ezaugarri batzuk (adibidez, zenbaki bat). Gakoa beharrezkoa da gako horri dagokion zuhaitzaren elementua aurkitu ahal izateko. Bilaketa-zuhaitz bitar adibidea:

zuhaitz ikuspegia

Aurrera doan heinean, kode zati batzuk (baliteke osatu gabeak) sartuko ditut zure ulermena hobetzeko. Kode osoa artikuluaren amaieran egongo da.

Zuhaitza nodoz osatuta dago. Nodoen egitura:

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;
    }
//...остальные методы узла
}

Nodo bakoitzak bi seme-alaba ditu (oso posible da leftChild eta/edo rightChild seme-alabak nuluak izatea). Seguruenik ulertu zenuen kasu honetan zenbaki-datuak nodoan gordetako datuak direla; tekla - nodo-gakoa.

Korapiloa asmatu genuen, orain hitz egin dezagun zuhaitzen arazo larriei buruz. Hemen eta behean, "zuhaitza" hitzak bilaketa-zuhaitz bitar baten kontzeptua esan nahi du. Zuhaitz egitura bitarra:

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

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

Klase-eremu gisa, zuhaitzaren erroa besterik ez dugu behar, errotik, getLeftChild() eta getRightChild() metodoak erabiliz, zuhaitzaren edozein nodotara irits zaitezke.

Zuhaitz algoritmoak

bilaketa

Demagun zuhaitz eraikia duzula. Nola aurkitu elementua gako-gakoarekin? Errotik zuhaitzean behera sekuentzialki mugitu eta gakoaren balioa hurrengo nodoko gakoarekin alderatu behar duzu: gakoa hurrengo nodoaren gakoa baino txikiagoa bada, joan nodoaren ezkerreko ondorengora, gehiago bada - eskuinera, teklak berdinak badira - nahi den nodoa aurkitzen da! Kode garrantzitsua:

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

Korrontea nulu bihurtzen bada, orduan iterazioa zuhaitzaren amaierara iritsi da (kontzeptu mailan, zuhaitzean existitzen ez den leku batean zaude - hosto baten seme-alaba).

Demagun bilaketa-algoritmoaren eraginkortasuna zuhaitz orekatu batean (nodoak berdin-berdin banatuta dauden zuhaitza). Orduan bilaketa-eraginkortasuna O(log(n)) izango da, eta 2 oinarriko logaritmoa. Ikus: zuhaitz orekatu batean n elementu badaude, horrek esan nahi du zuhaitzaren log(n) oinarri 2 mailak egongo direla. Eta bilaketan, zikloko urrats bat, maila bat jaisten zara.

txertatzeko

Bilaketaren funtsa ulertu baduzu, ez zaizu zaila izango txertaketa ulertzea. Zuhaitzaren hostora jaitsi besterik ez duzu behar (bilaketan deskribatutako jaitsiera-arauen arabera) eta haren ondorengo bihurtu - ezkerrera edo eskuinera, gakoaren arabera. Ezarpena:

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

Kasu honetan, uneko nodoaz gain, beharrezkoa da uneko nodoaren gurasoari buruzko informazioa gordetzea. Korrontea nulu bihurtzen denean, aldagai nagusiak behar dugun orria izango du.
Txertatzeko eraginkortasuna bilaketaren berdina izango da, jakina - O(log(n)).

kentzea

Ezabatzea da zuhaitz batekin egin beharko den eragiketarik konplexuena. Argi dago lehenik eta behin kenduko dugun elementua bilatu beharko dela. Baina orduan zer? Bere erreferentzia nulu gisa ezartzen badugu, orduan nodo hau erroa duen azpizuhaitzari buruzko informazioa galduko dugu. Zuhaitzak kentzeko metodoak hiru kasutan banatzen dira.

Lehenengo kasua. Kendu beharreko nodoak ez du seme-alabarik.

Ezabatu beharreko nodoak seme-alabarik ez badu, hosto bat dela esan nahi du. Hori dela eta, bere gurasoaren leftChild edo rightChild eremuak nulu gisa ezar ditzakezu.

Bigarren kasua. Kendu beharreko nodoak seme-alaba bat du

Kasu hau ere ez da oso zaila. Itzul gaitezen gure adibidera. Demagun 14 gakoa duen elementu bat ezabatu behar dugula. Onartu 10 gakoa duen nodo baten seme-alaba egokia denez, bere ondorengo edozeinek (kasu honetan, eskuinekoa) 10 baino gako handiagoa izango duela, beraz erraz "moztu" daiteke zuhaitzetik, eta gurasoa zuzenean ezabatzen ari den nodoaren haurra konektatu, hau da. konektatu 10. gakoa duen nodoa 13. nodoarekin. Egoera antzekoa izango litzateke bere gurasoaren ezkerreko seme-alaba den nodo bat ezabatu beharko bagenu. Pentsa ezazu zeure burua - analogia zehatza.

Hirugarren kasua. Nodok bi seme ditu

Kasurik zailena. Ikus dezagun adibide berri bati.

Bilatu oinordeko bat

Demagun gakoarekin nodoa kendu behar dugula 25. Nor jarriko dugu haren lekuan? Bere jarraitzaileetako batek (ondorengoak edo ondorengoen ondorengoak) bihurtu behar du ondorengoa(kendutako nodoaren lekua hartuko duena).

Nola dakizu nor izan behar duen ondorengoa? Intuitiboki, zuhaitzeko nodoa da, zeinaren gakoa kentzen ari den nodotik hurrengo handiena den. Algoritmoa honakoa da. Bere eskuineko haurra joan behar duzu (beti eskuinera, lehendik ere esana baitzen ondorengoaren gakoa ezabatzen ari den nodoaren gakoa baino handiagoa dela), eta ondoren eskuin honen ezkerreko seme-alaben katetik pasa. ume. Adibidean, 35 gakoa duen nodora joan behar dugu, eta, ondoren, bere ezkerreko seme-alaben katetik behera jaitsi hostora - kasu honetan, kate hau 30 gakoa duen nodoaz osatuta dago soilik. Zorrotz esanda, bilatzen ari gara. nahi den nodoa baino handiagoa den nodo multzoko nodo txikiena.

Ondorengo bilaketa metodoaren kodea:

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

Ezabatzeko metodoaren kode osoa:

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

Konplexutasuna O(log(n))ra hurbildu daiteke.

Zuhaitz batean maximoa/minimoa aurkitzea

Jakina, nola aurkitu zuhaitzean gutxieneko/gehieneko balioa - sekuentzialki zuhaitzaren ezkerreko/eskuineko elementuen katetik joan behar duzu, hurrenez hurren; hostora iristen zarenean, gutxieneko/gehieneko elementua izango da.

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

Konplexutasuna - O(log(n))

Saihesbide simetrikoa

Traversal zuhaitzaren nodo bakoitza bisitatzea da, horrekin zerbait egiteko.

Gurutze-algoritmo simetriko errekurtsiboa:

1. Egin ekintza bat ezkerreko haurraren gainean
2. Egin ekintza zure buruarekin
3. Egin ekintza bat ume egokiaren gainean

kodea:

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

Ondorioa

Azkenean! Ez badut zerbait azaldu edo iruzkinik badut, iruzkinetan zain nago. Agindu bezala, hona hemen kode osoa.

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

Endekapena O(n)

Askok ohartuko zineten: zer gertatzen da zuhaitza desorekatu egiten baduzu? Adibidez, jarri nodoak zuhaitzean gero eta gako handiagoak dituztenak: 1,2,3,4,5,6... Ondoren, zuhaitzak zertxobait gogoraraziko du estekatutako zerrenda bat. Eta bai, zuhaitzak bere zuhaitz-egitura galduko du, eta, hortaz, datuen sarbidearen eraginkortasuna. Bilaketa, txertatze eta ezabatze eragiketen konplexutasuna estekatutako zerrenda baten berdina izango da: O(n). Hau da, nire ustez, zuhaitz bitarren desabantaila garrantzitsuenetako bat.

Erregistratutako erabiltzaileek soilik parte hartu dezakete inkestan. Hasi saioa, mesedez.

Aspaldi ez naiz Habré-n egon, eta jakin nahiko nuke zein gairi buruzko zer artikulu gehiago ikustea gustatuko litzaizuke?

• Datuen Egiturak

• Algoritmoak (DP, errekurtsioa, datuen konpresioa, etab.)

• Datu-egiturak eta algoritmoak bizitza errealean aplikatzea

• Android aplikazioak Javan programatzea

• Java Web Aplikazioen Programazioa

2 erabiltzailek eman dute botoa. Erabiltzaile 1 abstenitu egin zen.

Iturria: www.habr.com