🥇 Dara Binar an jî meriv çawa dara lêgerînê ya binary amade dike

Pêşgotin

Ev gotar li ser darên lêgerîna binary e. Min vê dawiyê gotarek li ser kir berhevkirina daneyan bi karanîna rêbaza Huffman. Li wir min zêde guh neda darên binary, ji ber ku rêbazên lêgerîn, danîn û jêbirin ne têkildar bûn. Niha min biryar da ku ez gotarek li ser daran binivîsim. Werin em dest pê bikin.

Darek avahiyek daneyê ye ku ji girêkên ku bi kevanan ve girêdayî ne pêk tê. Em dikarin bibêjin ku dar haleteke taybet a grafekê ye. Li vir dara nimûne ye:

Ev ne dara lêgerînê ya binary e! Her tişt birîn!

Terminolojiyê

Root

Koka darê - ev girêka wê ya herî jorîn e. Di nimûneyê de, ev girê A ye. Di darekê de, tenê rêyek dikare ji kokê berbi girêkek din ve bibe! Di rastiyê de, her girêk dikare wekî koka binê dara ku bi vê girêkê re têkildar were hesibandin.

Dê û bav / neviyên

Ji bilî kokê, hemî girêk tam xwedan hêlek e ku berbi girêkek din ve diçe. Ji girêka ku li jorê ya heyî ye tê gotin dê û bav vê nodê. Navê girêkek ku li binê ya heyî ye û pê ve girêdayî ye tê gotin nebî vê nodê. Werin em mînakek bikar bînin. Ka em girêka B bigirin, paşê dêûbavê wê bibe girêka A, û zarokên wê dê bibin girêka D, E û F.

Rûberê nivînê

Ji girêka ku zarokên wê tune be, pelê darê tê gotin. Di nimûneyê de, pel dê bibin girêkên D, E, F, G, I, J, K.

Ev termînolojiya bingehîn e. Têgehên din dê bêtir bêne nîqaş kirin. Ji ber vê yekê, dara binary darek e ku tê de her girêk dê ji du zarokan zêdetir nebe. Wekî ku we texmîn kir, dara ji nimûneyê dê ne binary be, ji ber ku girêkên B û H ji du zarokan zêdetir in. Li vir mînakek dara binary e:

Di girêkên darê de dikare her agahdarî hebe. Dara lêgerînê ya binary darek binary e ku xwediyê taybetmendiyên jêrîn e:

Herdu jêrdarên çep û rast darên lêgerînê yên binary in.
Hemî girêkên binê dara çepê ya girêkek keyfî X xwedî nirxên mifteya daneyê ji nirxa mifteya daneya girê X bixwe kêmtir in.
Hemî girêkên di binê dara rastê ya girêkek keyfî X de xwedî nirxên mifteya daneyê ji nirxa mifteya daneya girê X bixwe mezintir an wekhev in.

Ключ - her taybetmendiyek girêk (mînak, hejmarek). Miftek pêdivî ye ku hûn bikarin hêmana darê ya ku ev mift pê re têkildar e bibînin. Mînakek dara lêgerînê ya binary:

Dîtina darê

Her ku em pêşve diçin, ez ê hin perçeyên kodê (dibe ku ne temam) peyda bikim da ku têgihîştina we baştir bikim. Koda tevahî dê di dawiya gotarê de be.

Darek ji girêkan pêk tê. Struktura nodê:

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

Her girêk du zarokan hene (mimkûn e ku zarokên ÇepChild û/an RastChild nirxek betal hebe). Dibe ku we fêhm kir ku di vê rewşê de daneyên hejmarê daneyên ku di girêkê de hatine hilanîn e; kilît - nod key.

Me girêk ji hev vekir, naha em li ser pirsgirêkên zextê yên li ser daran biaxivin. Li vir, bi peyva "dar" ez ê wateya têgeha dara lêgerînê ya binary. Struktura dara binary:

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

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

Em tenê ji koka darê wekî qada polê hewce ne, ji ber ku ji kokê, bi karanîna rêbazên getLeftChild() û getRightChild() hûn dikarin bigihîjin her girêka darê.

Algorîtmayên di darekê de

Поиск

Em bêjin darek we ya çêkirî heye. Meriv çawa hêmanek bi mifteya sereke bibîne? Pêdivî ye ku hûn bi rêzê ji kokê berbi darê ve biçin û nirxa mifteyê bi mifteya girêka din re bidin ber hev: heke mifteyê ji mifteya girêka paşîn kêmtir be, wê hingê biçin nivşê çepê yê girêk, heke ew be. mezintir, ji yê rastê re, heke kilît wekhev bin, girêka xwestî tê dîtin! Koda têkildar:

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

Ger niha betal bibe, wê hingê lêgerîn gihîştiye dawiya darê (di astek têgehî de, hûn di darê de li cîhek tune ne - neviyek pelek).

Ka em bandora algorîtmaya lêgerînê li ser darek hevseng (darek ku tê de girêk kêm-zêde bi rengek wekhev têne belav kirin) bifikirin. Wê hingê karbidestiya lêgerînê dê bibe O(log(n)), û logarîtma bingehê 2 ye. Binêre: heke di darek hevseng de n hêman hebin, wê hingê ev tê wê wateyê ku dê li ser bingeha 2 astan log(n) hebe. dar. Û di lêgerînê de, di yek gavê çerxê de, hûn yek astê dadikevin.

lêzêdekirin

Ger hûn cewhera lêgerînê fam bikin, wê hingê têgihîştina têxê ji we re ne dijwar be. Hûn tenê hewce ne ku dakevin pelek darê (li gorî qaîdeyên daketinê yên ku di lêgerînê de hatine destnîşan kirin) û bibin dûndana wê - çep an rast, li gorî mifteyê. Pêkanîna:

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

Di vê rewşê de, ji bilî girêka heyî, pêdivî ye ku agahdariya li ser dêûbavê girêka heyî were hilanîn. Dema ku niha bibe nûl wekhev, guhêrbara dêûbav dê pelika ku em hewce ne vedihewîne.
Karbidestiya têketinê dê eşkere wekî ya lêgerînê be - O(log(n)).

Deletion

Rakirin operasyona herî dijwar e ku dê li ser darekê were kirin. Eşkere ye ku pêşî em ê hewce bikin ku hêmana ku em ê jêbirin bibînin. Lê paşê çi? Ger em bi tenê referansa wê wekî null destnîşan bikin, em ê agahdariya li ser bindara ku ev girêk jê re kok e winda bikin. Rêbazên rakirina darê di sê rewşan de têne dabeş kirin.

Doza yekem. Di girêka ku tê jêbirin de zarok nînin

Ger girêka ku tê jêbirin tune be, wê hingê ev tê vê wateyê ku ew pel e. Ji ber vê yekê, hûn dikarin bi tenê qadên çepêChild an rastChild yên dêûbavê wê wekî betal bikin.

Doza duyemîn. Di girêka ku were jêbirin de zarokek heye

Ev doz jî ne pir tevlîhev e. Em vegerin ser mînaka xwe. Em bibêjin ku pêdivî ye ku em hêmanek bi mifteya 14-an jêbikin. Bipejirînin ku ji ber ku ew nîjada rast a girêkek bi kilîta 10-ê ye, wê hingê yek ji dûndana wê (di vê rewşê de ya rast) dê kilîtek ji 10-an mezintir hebe, ji ber vê yekê hûn dikare bi hêsanî wê ji darê "bibire", û dêûbav rasterast bi zarokê girêka ku tê jêbirin ve girêde, yanî. girêkê bi kilîta 10-ê bi girê 13-ê ve girêdide. Ger hewce bû ku girêkek ku zaroka dêûbavê wê ya çepê ye jê bibe, rewş dê wiha be. Bi xwe li ser wê bifikirin - analojiyek rastîn.

Doza sêyemîn. Nodek du zarokên xwe hene

Doza herî dijwar. Ka em li mînakek nû binêrin.

Bigerin ji bo cîgir

Ka em bibêjin divê em girêkek bi mifteya 25 jêbirin. Divê em kê têxin şûna wê? Divê yek ji şagirtên wî (nevî an jî dûndana dûvdanan) bibe karkera li pêhat(Yê ku dê cihê girêk tê rakirin) bigire.

Meriv çawa têdigihîje kî divê bibe cîgirê? Bi têgihîştî, ev girêkek di darê de ye ku kilîta wê ya herî mezin e ji girêka ku tê jêbirin. Algorîtma wiha ye. Pêdivî ye ku hûn herin ser dûndana wê ya rastê (her gav li yê rastê, ji ber ku ji berê ve hatî gotin ku mifteya paşgir ji mifteya girêka ku tê jêbirin mezintir e), û dûv re derbasî zincîra neviyên çepê yên vê dûvê rastê bibin. . Di nimûneyê de, em ê bi mifteya 35-an ve biçin ser girêkê, û dûv re di nav zincîra zarokên wê yên çepê de biçin ser pelê - di vê rewşê de, ev zincîre tenê ji girêka bi kilîta 30-ê pêk tê. Bi hişkî, em lê digerin. ji bo girêka herî piçûk di komek girêkan de ji ya ku em lê digerin mezintir e.

Koda rêbaza lêgerînê ya serketî:

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

Koda tevahî ji bo rêbaza jêbirinê:

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

Tevlihevî dikare bi O(log(n)) ve were texmîn kirin.

Di darekê de herî zêde/kêmtirîn dîtin

Eşkere ye ku meriv çawa di darekê de nirxa herî kêm / herî zêde bibîne - hûn hewce ne ku bi rêzê ve li ser zincîra hêmanên çepê / rastê yê darê bi rêzê bigerin; gava ku hûn gihîştin pelê, ew ê elementa herî kêm / herî zêde be.

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

Tevlihevî - O(log(n))

Derbasbûna Symmetrical

Traversal serdana her girêka darê dike da ku bi wê re hin çalakiyan bike.

Algorîtmaya rêveçûna sîmetrîk a vegerî:

Li ser zarokê çepê çalakiyek bikin
Bi xwe re çalakiyek bikin
Li ser zarokê rast çalakiyek bikin

Code:

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

encamê

Paşan! Ger min tiştek rave nekiribe an şîroveyek hebe, ji kerema xwe wan di şîroveyan de bihêle. Wekî ku soz da, ez koda tevahî peyda dikim.

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

Dejenerasyon ji bo O(n)

Dibe ku gelek ji we ferq kiriye: heke hûn darê bêhevseng bikin çi? Mînakî, girêkên bi kilît zêde dibin li darekê bixin: 1,2,3,4,5,6... Wê hingê dar dê hinekî dişibihe navnîşek pêvekirî. Erê, dar dê strukturê xwe yê darê winda bike, û ji ber vê yekê jî karîgeriya gihîştina daneyê winda bike. Tevliheviya operasyonên lêgerîn, têxistin û jêbirinê dê bibe heman wekî ya navnîşek girêdayî: O(n). Ev yek ji herî girîng e, bi dîtina min, dezawantajên darên binary.

Tenê bikarhênerên qeydkirî dikarin beşdarî anketê bibin. Têketinji kerema xwe.