🥇Isihlahla Kanambambili noma indlela yokulungisa isihlahla sosesho olunambambili

Yethula

Lesi sihloko sikhuluma ngezihlahla zokusesha kanambambili. Ngisanda kwenza isihloko mayelana ukucindezela idatha usebenzisa indlela ye-Huffman. Lapho angizange nginake kakhulu izihlahla kanambambili, ngoba ukusesha, ukufakwa, nezindlela zokususa zazingafaneleki. Manje nginqume ukubhala isihloko mayelana nezihlahla. Ake siqale.

Isihlahla isakhiwo sedatha esihlanganisa ama-node axhunywe imiphetho. Singasho ukuthi isihlahla siyicala elikhethekile legrafu. Nasi isibonelo sesihlahla:

Lesi akusona isihlahla sokucinga kanambambili! Konke kusikiwe!

I-terminology

Umsuka

Impande yesihlahla - lena i-node yayo ephezulu kakhulu. Esibonelweni, lena i-node A. Esihlahleni, indlela eyodwa kuphela engaholela ukusuka empandeni iye kunoma iyiphi enye i-node! Eqinisweni, noma iyiphi i-node ingabhekwa njengempande ye-subtree ehambisana nale nodi.

Abazali/inzalo

Wonke ama-node ngaphandle kwempande anomkhawulo owodwa oholela kwenye i-node. I-node etholakala ngenhla kwalena yamanje ibizwa umzali le node. I-node etholakala ngaphansi kwalena yamanje futhi exhunywe kuyo ibizwa inzalo le node. Ake sisebenzise isibonelo. Ake sithathe inodi B, khona-ke umzali wayo uzoba inodi A, futhi izingane zayo zizoba amanodi D, E kanye no-F.

Leaf

I-node engenabantwana izobizwa ngokuthi iqabunga lesihlahla. Esibonelweni, amaqabunga azoba amanodi D, E, F, G, I, J, K.

Leli igama eliyisisekelo. Eminye imiqondo kuzoxoxwa ngayo ngokuqhubekayo. Ngakho-ke, isihlahla kanambambili isihlahla lapho i-node ngayinye ingeke ibe nezingane ezingaphezu kwezimbili. Njengoba uqagele, isihlahla esivela esibonelweni ngeke sibe kanambambili, ngoba ama-node B no-H anezingane ezingaphezu kwezimbili. Nasi isibonelo sesihlahla kanambambili:

Amanodi esihlahla angaqukatha noma yiluphi ulwazi. Umuthi wokusesha kanambambili isihlahla kanambambili esinezici ezilandelayo:

Zombili izihlahla ezingaphansi kwesokunxele nesokudla ziyizihlahla zokusesha ezimbaxambili.
Wonke ama-node we-subtree engakwesokunxele ye-node engu-X anamanani wokhiye wedatha angaphansi kwenani lokhiye wedatha we-node X ngokwayo.
Wonke ama-node esihlahleni esingezansi esingakwesokudla se-node engu-X anamanani okhiye wedatha amakhulu noma alingana nenani lokhiye wedatha wenodi X ngokwayo.

Ukhiye - noma yisiphi isici se-node (isibonelo, inombolo). Kudingeka ukhiye ukuze ukwazi ukuthola isici somuthi lapho lesi sihluthulelo sihambisana khona. Isibonelo somuthi wokusesha onambambili:

Ukubuka kwesihlahla

Njengoba sithuthuka, ngizokunikeza ezinye izingcezu zekhodi (okungenzeka ezingaphelele) ukuze ngithuthukise ukuqonda kwakho. Ikhodi ephelele izoba sekupheleni kwesihloko.

Isihlahla siqukethe amaqhuqhuva. Ukwakheka kwenodi:

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

Indawo ngayinye inezingane ezimbili (kungenzeka ukuthi ingane yakwesokunxele kanye/noma yesokudla izoqukatha inani elingenalutho). Cishe uqaphele ukuthi kulokhu idatha yenombolo yidatha egcinwe ku-node; key - ukhiye we-node.

Silungise ifindo, manje ake sikhulume ngezinkinga ezicindezelayo ngezihlahla. Ngemva kwalokhu, ngegama elithi “isihlahla” ngizosho umqondo womuthi wokusesha kanambambili. Isakhiwo sesihlahla kanambambili:

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

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

Sidinga kuphela impande yesihlahla njengenkambu yekilasi, ngoba kusuka empandeni, usebenzisa izindlela ze-getLeftChild() kanye ne-getRightChild(), ungathola kunoma iyiphi i-node esihlahleni.

Ama-algorithms esihlahleni

Поиск

Ake sithi unesihlahla esakhiwe. Ungayithola kanjani into enokhiye wokhiye? Udinga ukuhamba ngokulandelana ukusuka empandeni wehle esihlahleni bese uqhathanisa inani lokhiye nokhiye we-node elandelayo: uma ukhiye ungaphansi kwesihluthulelo se-node elandelayo, bese uya enzalweni yesokunxele ye-node, uma okukhulu, kwesokudla, uma okhiye belingana, i-node oyifunayo iyatholakala! Ikhodi ehambisanayo:

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

Uma okwamanje kuba yize, khona-ke ukusesha sekufinyelele ekupheleni kwesihlahla (ezingeni lomqondo, usendaweni engekho esihlahleni - inzalo yeqabunga).

Ake sicabangele ukusebenza kahle kwe-algorithm yokusesha esihlahleni esilinganiselayo (isihlahla lapho amanodi asatshalaliswa ngokulinganayo noma ngokulinganayo). Khona-ke ukusebenza kahle kosesho kuzoba ngu-O(log(n)), bese i-logarithm iyisisekelo esingu-2. Bheka: uma kukhona ama-elementi angu-n esihlahleni esilinganisiwe, kusho ukuthi kuzoba nelogi(n) ukuze kusekelwe amazinga angu-2 we umuthi. Futhi ekusesheni, esinyathelweni esisodwa somjikelezo, wehla izinga elilodwa.

Faka

Uma ubamba ingqikithi yosesho, ukuqonda okufakiwe ngeke kube nzima kuwe. Udinga nje ukwehla eqabungeni lomuthi (ngokwemithetho yokwehla echazwe ekusesheni) futhi ube yinzalo yayo - kwesokunxele noma kwesokudla, kuye ngokhiye. Ukuqaliswa:

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

Kulesi simo, ngaphezu kwe-node yamanje, kuyadingeka ukugcina ulwazi mayelana nomzali we-node yamanje. Uma okwamanje kufana nokungabi nalutho, okuguquguqukayo komzali kuzoqukatha ishidi esilidingayo.
Ukusebenza kahle kokufakwayo kuzofana nokusesho - O(log(n)).

Susa

Ukususwa kuwumsebenzi onzima kakhulu ozodinga ukwenziwa esihlahleni. Kuyacaca ukuthi okokuqala sizodinga ukuthola i-elementi esizoyisusa. Kodwa-ke kuthiwani? Uma simane sibeka ireferensi yayo ku-null, sizolahlekelwa ulwazi mayelana nesihlahla esingaphansi lapho le nodi iyimpande. Izindlela zokususa izihlahla zihlukaniswe ngamacala amathathu.

Icala lokuqala. Indawo esuswayo ayinazo izingane

Uma i-node isuswa ingenazo izingane, lokhu kusho ukuthi iqabunga. Ngakho-ke, ungamane usethe izinkambu zeLeftChild noma rightChild zomzali wayo ukuthi zingasebenzi.

Icala lesibili. Inodi ezosuswa inengane eyodwa

Leli cala nalo aliyinkimbinkimbi kakhulu. Ake sibuyele esibonelweni sethu. Ake sithi sidinga ukususa i-elementi ngokhiye 14. Vuma ukuthi njengoba iyinzalo efanele yenodi enokhiye 10, noma iyiphi inzalo yayo (kulokhu okulungile) izoba nokhiye omkhulu kuno-10, ingakwazi "ukusika" kalula esihlahleni, futhi ixhume umzali ngqo enganeni ye-node esuswayo, i.e. xhuma i-node nokhiye 10 ku-node 13. Isimo besiyofana uma kudingekile ukususa i-node eyingane yesokunxele yomzali wayo. Cabanga ngakho ngokwakho - isifaniso esiqondile.

Icala lesithathu. I-node inezingane ezimbili

Icala elinzima kakhulu. Ake sibheke isibonelo esisha.

Sesha ozongena esikhundleni

Ake sithi sidinga ukususa i-node ngokhiye 25. Kufanele sibeke bani endaweni yayo? Omunye wabalandeli bakhe (inzalo noma inzalo yenzalo) kumelwe abe owalandela(ozothatha indawo yokukhishwa kwenodi).

Indlela yokuqonda ukuthi ubani okufanele abe yindlalifa? Ngokuqondayo, lena i-node esihlahleni ukhiye wayo ungomkhulu olandelayo ku-node esuswayo. I-algorithm imi kanje. Udinga ukuya enzalweni yayo yesokudla (njalo uye kwekwesokudla, ngoba sekuvele kushiwo ukuthi ukhiye womlandeli mkhulu kunokhiye we-node esuswayo), bese udlula ochungechungeni lwenzalo yesokunxele yale nzalo yesokudla. . Esibonelweni, sizoya endaweni enokhiye ongu-35, bese sehlela eqabungeni ngeketanga lezingane ezingakwesokunxele - kulokhu, leli ketanga liqukethe kuphela i-node enokhiye ongu-30. Ngokuqondile, sibheka. endaweni encane kunazo zonke kusethi yamanodi amakhulu kunalena esiyifunayo.

Ikhodi yendlela yosesho yomlandeli:

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

Ikhodi egcwele yendlela yokususa:

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

Ubunkimbinkimbi bungalinganiselwa kokuthi O(log(n)).

Ukuthola ubuningi/ubuncane esihlahleni

Kusobala ukuthi ungathola kanjani inani eliphansi/eliphezulu esihlahleni - udinga ukuhamba ngokulandelana ochungechungeni lwezakhi zesokudla/kwesokudla zesihlahla, ngokulandelana; uma ufika eshidini, kuzoba yisici esincane/esiphezulu.

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

Ubunkimbinkimbi - O(log(n))

I-bypass ye-Symmetrical

I-Traversal ivakashela indawo ngayinye yesihlahla ukuze yenze isenzo esithile ngaso.

I-algorithm ye-recursive symmetric traversal:

Yenza isenzo enganeni yangakwesobunxele
Yenza isenzo nawe
Yenza isenzo enganeni efanele

Ikhodi:

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

isiphetho

Ekugcineni! Uma ngingakachazi lutho noma nginakho ukuphawula, ngicela uwashiye kumazwana. Njengoba ngithembisile, nginikeza ikhodi ephelele.

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

I-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

Ukwehla ku-O(n)

Abaningi benu kungenzeka ukuthi baye baqaphela: kuthiwani uma wenza umuthi ungalingani? Isibonelo, faka ama-node anokhiye abakhulayo esihlahleni: 1,2,3,4,5,6... Khona-ke isihlahla sizofana nohlu oluxhunyiwe. Futhi yebo, isihlahla sizolahlekelwa isakhiwo saso somuthi, ngakho-ke ukusebenza kahle kokufinyelela kwedatha. Ubunkimbinkimbi bokusesha, ukufakwa, kanye nemisebenzi yokususa buzofana nobohlu oluxhunyiwe: O(n). Lokhu kungenye yezinto ezibaluleke kakhulu, ngokubona kwami, ukungalungi kwezihlahla kanambambili.

Abasebenzisi ababhalisiwe kuphela abangabamba iqhaza kuhlolovo. Ngena ngemvume, wamukelekile.

Angikaze ngibe kuhabhu isikhathi eside, futhi ngingathanda ukwazi ukuthi yiziphi izihloko mayelana nokuthi yiziphi izihloko ongathanda ukubona okwengeziwe ngazo?

Izakhiwo zedatha
Ama-algorithms (i-DP, i-recursion, ukucindezelwa kwedatha, njll.)
Ukusetshenziswa kwezakhiwo zedatha nama-algorithms empilweni yangempela
Ukuhlela izinhlelo zokusebenza ze-Android ku-Java
Ukuhlela izinhlelo zokusebenza zewebhu ku-Java

2 abasebenzisi abavotile. Umsebenzisi ongu-1 uyekile.

Umthombo: www.habr.com

Binary Tree noma indlela yokulungisa isihlahla sokusesha kanambambili