🥇Binary Tree na fomba fanomanana hazo fikarohana binary

fampidirana

Ity lahatsoratra ity dia momba ny hazo fikarohana binary. Vao haingana aho no nanao lahatsoratra momba ny famatrarana angona mampiasa ny fomba Huffman. Teo aho dia tsy niraharaha loatra ny hazo binary, satria ny fomba fikarohana, fampidirana ary famafana dia tsy misy dikany. Nanapa-kevitra ny hanoratra lahatsoratra momba ny hazo aho izao. Andeha isika hanomboka.

Ny hazo dia rafitra angon-drakitra misy node mifamatotra amin'ny sisiny. Afaka milaza isika fa ny hazo dia tranga manokana amin'ny grafika. Ity misy ohatra hazo iray:

Tsy hazo fikarohana binary io! Tapaka ny zava-drehetra!

voambolana

faka

Fakan-kazo - io no node ambony indrindra. Ao amin'ny ohatra, ity dia node A. Amin'ny hazo iray, lalana iray ihany no afaka mitondra avy amin'ny fakany mankany amin'ny node hafa! Raha ny marina, ny node rehetra dia azo raisina ho fototry ny zana-kazo mifanitsy amin'io node io.

Ray aman-dreny/taranaka

Ny node rehetra afa-tsy ny fakany dia manana sisiny iray mankany amin'ny node hafa. Ny node eo ambonin'ny ankehitriny dia antsoina hoe ray aman-dreny ity node. Antsoina ny node iray eo ambanin'ilay ankehitriny ary mifandray aminy taranaky ity node. Andeha isika hampiasa ohatra. Andeha horaisintsika ny node B, dia ho node A ny ray aman-dreniny, ary ho node D, E ary F ny zanany.

lamba

Ny node tsy manan-janaka dia hatao hoe ravin-kazo. Amin'ny ohatra, ny ravina dia ho nodes D, E, F, G, I, J, K.

Izany no voambolana fototra. Ny hevitra hafa dia hodinihina bebe kokoa. Noho izany, ny hazo mimari-droa dia hazo iray izay tsy hanana zanaka mihoatra ny roa ny node tsirairay. Araka ny noeritreretinao, ny hazo avy amin'ny ohatra dia tsy ho binary, satria ny node B sy H dia manana zanaka mihoatra ny roa. Ity misy ohatra amin'ny hazo binary:

Ny node hazo dia mety ahitana fampahalalana rehetra. Ny hazo fikarohana binary dia hazo mimari-droa izay manana ireto toetra manaraka ireto:

Ny zana-kazo havia sy havanana dia hazo fikarohana mimari-droa.
Ny node rehetra amin'ny zana-kazo ankavia amin'ny node X dia manana soatoavin'ny data key latsaky ny sandan'ny fanalahidin'ny node X.
Ny node rehetra amin'ny zana-kazo havanana amin'ny node X dia manana soatoavina manan-danja lehibe kokoa na mitovy amin'ny sandan'ny fanalahidin'ny node X.

manan-danja - izay toetra mampiavaka ny node (ohatra, isa). Ilaina ny lakile mba hahitanao ny singa hazo mifanaraka amin'io lakile io. Ohatra amin'ny hazo fikarohana binary:

Fijerena hazo

Rehefa mandroso isika dia hanome kaody vitsivitsy (mety tsy feno) aho mba hanatsarana ny fahatakaranao. Ny kaody feno dia ho any amin'ny faran'ny lahatsoratra.

Ny hazo dia misy nodes. Firafitry ny node:

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

Ny node tsirairay dia manan-janaka roa (azo inoana fa ny zaza leftChild sy/na rightChild dia misy sanda tsy misy dikany). Azo inoana fa nahatsapa ianao fa amin'ity tranga ity dia ny angon-drakitra voatahiry ao amin'ny node ny angon-drakitra isa; key — node key.

Nandamina ny fatotra izahay, andao hiresaka momba ny olana maika momba ny hazo. Aorian'izay, ny teny hoe "hazo" dia midika hoe foto-kevitra momba ny hazo fikarohana binary. Rafitra hazo binary:

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

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

Ny fakan'ny hazo ihany no ilaintsika ho toy ny sahan'ny kilasy, satria avy amin'ny fakany, mampiasa ny getLeftChild() sy getRightChild() fomba, dia afaka miditra amin'ny node rehetra ao amin'ny hazo ianao.

Algorithms amin'ny hazo

Поиск

Aoka hatao hoe manana hazo namboarina ianao. Ahoana ny fomba hahitana singa misy ny fanalahidy? Mila miala amin'ny fakany midina amin'ny hazo ianao ary mampitaha ny sandan'ny fanalahidy amin'ny fanalahidin'ny node manaraka: raha kely noho ny fanalahidin'ny node manaraka ny lakile, dia mankanesa any amin'ny zaza havia amin'ny node, raha toa ka bebe kokoa, mankany amin'ny havanana, raha mitovy ny fanalahidy, dia hita ny node tadiavina! Kaody mifandraika:

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

Raha lasa tsy misy dikany ny ankehitriny, dia tonga any amin'ny faran'ny hazo ny fikarohana (amin'ny ambaratonga ara-kevitra, eo amin'ny toerana tsy misy eo amin'ny hazo ianao - taranaky ny ravina).

Andeha hojerentsika ny fahombiazan'ny algorithm amin'ny fikarohana amin'ny hazo voalanjalanja (hazo iray izay zaraina mitovy na kely kokoa ny node). Avy eo ny fahombiazan'ny fikarohana dia O (log(n)), ary ny logaritma dia fototra 2. Jereo: raha misy singa n ao anaty hazo voalanjalanja, dia midika izany fa hisy log(n) mankany amin'ny ambaratonga 2 fototra amin'ny hazo. Ary amin'ny fikarohana, amin'ny dingana iray amin'ny tsingerina, dia midina ambaratonga iray ianao.

Mampidira

Raha azonao ny fototry ny fikarohana, dia tsy ho sarotra aminao ny hahatakatra ny fampidirana. Mila midina fotsiny amin'ny ravin'ny hazo ianao (araka ny fitsipiky ny fidinana voalaza ao amin'ny fikarohana) ary ho lasa taranany - havia na havanana, miankina amin'ny fanalahidy. Fampiharana:

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

Amin'ity tranga ity, ankoatra ny node amin'izao fotoana izao, dia ilaina ny mitahiry vaovao momba ny ray aman-drenin'ny node amin'izao fotoana izao. Rehefa mitovitovy amin'ny null ny current, dia ahitana ny takelaka ilaintsika ny fari-piainan'ny ray aman-dreny.
Ny fahombiazan'ny fampidirana dia mazava ho azy fa mitovy amin'ny fikarohana - O(log(n)).

fanesorana

Ny fanesorana no asa sarotra indrindra tokony hatao amin'ny hazo. Mazava fa mila mitady ny singa izay hofafantsika aloha isika. Fa ahoana ary? Raha apetraka fotsiny amin'ny null ny fanondroana azy dia ho very ny fampahalalana momba ny zana-kazo misy an'io node io. Mizara telo ny fomba fanalana hazo.

Raharaha voalohany. Tsy manan-janaka ny node voafafa

Raha tsy manan-janaka ny node voafafa dia midika izany fa ravin-kazo izy io. Noho izany, azonao atao ny mametraka fotsiny ny sahan'ny leftChild na rightChild an'ny ray aman-dreniny ho tsy misy dikany.

Raharaha faharoa. Manana zanaka iray ny node hofafana

Tsy dia sarotra ihany koa ity raharaha ity. Andeha isika hiverina amin’ny ohatra asehontsika. Andeha atao hoe mila mamafa singa iray misy fanalahidy 14 isika. Ekeo fa satria taranaka havanana amin'ny node misy fanalahidy 10 izy io, dia ny taranany (amin'ity tranga ity ny havanana) dia hanana fanalahidy lehibe kokoa noho ny 10, ka ianao dia afaka "manapaka" mora foana amin'ny hazo, ary mampifandray mivantana ny ray aman-dreny amin'ny zanaky ny node voafafa, i.e. mampifandray ny node amin'ny fanalahidy 10 amin'ny node 13. Mety ho toy izany koa ny toe-javatra raha ilaina ny mamafa ny node izay zanaka ankavian'ny ray aman-dreniny. Eritrereto ny tenanao - fanoharana marina.

Tranga fahatelo. Ny node dia manan-janaka roa

Ny tranga sarotra indrindra. Andeha isika hijery ohatra vaovao.

Mitadiava mpandimby

Andao atao hoe mila mamafa node misy fanalahidy 25. Iza no tokony hapetraka eo amin'ny toerany? Ny iray amin'ireo mpanara-dia azy (taranaka na taranaky ny taranany) dia tsy maintsy lasa mpandimby(ilay haka ny toeran'ny node esorina).

Ahoana no ahafantarana hoe iza no tokony ho mpandimby? Intuitively, ity dia node ao amin'ny hazo izay ny lakile no lehibe indrindra manaraka avy amin'ny node voafafa. Ny algorithm dia toy izao manaraka izao. Mila mankany amin'ny taranany havanana ianao (miankavanana foana, satria efa voalaza fa lehibe kokoa noho ny fanalahidin'ny node voafafa ny fanalahidin'ny mpandimby), ary avy eo dia mandehana amin'ny rojom-pirazanana ankavia amin'ity taranaka havanana ity. . Amin'ny ohatra, dia mandeha any amin'ny node miaraka amin'ny fanalahidy 35 isika, ary avy eo midina mankany amin'ny ravina amin'ny alàlan'ny rojo ny zanany havia - amin'ity tranga ity, ity rojo ity dia tsy misy afa-tsy ny node misy fanalahidy 30. Raha ny marina dia mitady isika. ho an'ny node kely indrindra amin'ny fitambaran'ny node lehibe kokoa noho ilay tadiavintsika node.

Kaody fomba fikarohana mpandimby:

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

Kaody feno ho an'ny fomba famafana:

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

Ny fahasarotana dia azo tombanana amin'ny O(log(n)).

Mitady faratampony/farany amin'ny hazo iray

Mazava ho azy ny fomba hahitana ny sanda kely indrindra / fara-tampony amin'ny hazo iray - mila mihetsika manaraka ny rojo misy singa havia / havanana amin'ny hazo ianao, tsirairay avy; rehefa tonga any amin'ny takelaka ianao dia ho singa kely / fara-tampony.

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

Sarotra - O(log(n))

Bypass symmetrical

Ny traversal dia mitsidika ny node tsirairay amin'ny hazo mba hanaovana hetsika miaraka aminy.

Algorithm traversal symmetric recursive:

Manaova hetsika eo amin'ny zaza ankavia
Manaova hetsika miaraka amin'ny tenanao
Manaova hetsika amin'ny zaza mety

code:

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

famaranana

Farany! Raha tsy nanazava na inona na inona aho na manana hevitra dia avelao izy ireo ao amin'ny fanehoan-kevitra. Araka ny nampanantenaina dia omeko ny kaody feno.

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

Sal

Fahasimbana ho O(n)

Maro aminareo angamba no nahatsikaritra hoe: ahoana raha ataonareo tsy voalanjalanja ilay hazo? Ohatra, asio node misy fanalahidy mitombo ao anaty hazo iray: 1,2,3,4,5,6... Avy eo ilay hazo dia hitovy amin'ny lisitra mifandray. Ary eny, ho very ny firafitry ny hazo ny hazo, ary noho izany ny fahombiazan'ny fidirana angona. Ny fahasarotan'ny fikarohana, fampidirana ary famafana dia hitovy amin'ny an'ny lisitra mifandray: O(n). Io no iray amin'ireo zava-dehibe indrindra, araka ny hevitro, ny tsy fahampian'ny hazo binary.

Ireo mpampiasa voasoratra anarana ihany no afaka mandray anjara amin'ny fanadihadiana. HiditraPlease.

Efa ela aho no tsy tao amin'ny ivon-toerana, ary tiako ho fantatra ny lahatsoratra momba ny lohahevitra tianao hojerena bebe kokoa?

Rafitra data
Algorithm (DP, recursion, famatrarana data, sns.)
Fampiharana rafitra angon-drakitra sy algorithm amin'ny tena fiainana
Fandaharana fampiharana Android amin'ny Java
Fampiharana tranonkala amin'ny Java

Mpampiasa 2 no nifidy. Mpampiasa 1 no nifady.

Loharano: www.habr.com

Binary Tree na ny fomba hanomanana hazo fikarohana binary