🥇 Umthi weBinary okanye indlela yokulungisa umthi wokukhangela wokubini

Umboniso

Eli nqaku limalunga nemithi yokukhangela yokubini. Kutshanje ndiyenzile inqaku malunga Uxinzelelo lwedatha usebenzisa indlela yeHuffman. Apho andizange ndihlawule kakhulu kwimithi yebhinari, kuba ukukhangela, ukufakwa, kunye neendlela zokucima zazingafanelekanga. Ngoku ndagqiba ekubeni ndibhale inqaku malunga nemithi. Masiqalise.

Umthi sisakhiwo sedatha esiquka iindawo ezidityaniswe ngamaphethelo. Sinokuthi umthi yimeko ekhethekileyo yegrafu. Nanku umzekelo womthi:

Lo ayingomthi wophendlo wokubini! Yonke into isikiwe!

I sigama

Umsuka

Ingcambu yomthi - le yeyona node yayo ephezulu. Kumzekelo, le node A. Emthini, indlela enye kuphela inokukhokelela ukusuka kwingcambu ukuya kuyo nayiphi na enye indawo! Enyanisweni, nayiphi na i-node inokuthathwa njengengcambu ye-subtree ehambelana nale node.

Abazali/inzala

Onke amaqhuqhuva ngaphandle kwengcambu anomphetho omnye kanye okhokelela kwenye indawo. Indawo ebekwe ngaphezulu kwale yangoku ibizwa ngokuba umzali le nodi. Indawo ebekwe ngaphantsi kwale yangoku kwaye iqhagamshelwe kuyo ibizwa ngokuba inzala le nodi. Makhe sisebenzise umzekelo. Masithathe i-node B, umzali wayo uya kuba ngu-A, kwaye abantwana bayo baya kuba ngu-D, u-E kunye no-F.

Leaf

I-node engenabantwana iya kubizwa ngokuba ligqabi lomthi. Kumzekelo, amagqabi aya kuba ngamaqhuqhuva D, E, F, G, I, J, K.

Esi sisigama esisisiseko. Ezinye iikhonsepthi ziya kuxoxwa ngokubhekele phaya. Ngoko ke, umthi wokubini ngumthi apho i-node nganye ayiyi kuba nabantwana abangaphezu kwesibini. Njengoko uqikelele, umthi ovela kumzekelo awuyi kuba bini, kuba i-nodes B kunye ne-H inabantwana abangaphezu kwesibini. Nanku umzekelo womthi wokubini:

Amaqhuqhuva emithi angaqulatha naluphi na ulwazi. Umthi wophendlo wokubini ngumthi wokubini oneempawu ezilandelayo:

Yomibini imithi esezantsi ekhohlo nasekunene yimithi yokukhangela yokubini.
Zonke iinodi zomthi ongaphantsi wasekhohlo we-node engenamkhethe X zinexabiso elibalulekileyo ledatha engaphantsi kwexabiso leqhosha ledatha le-node X ngokwayo.
Zonke iinodi kumthi ongezantsi osezantsi we-arbitrary node X zinamaxabiso angundoqo edatha amakhulu okanye alingana nexabiso lesitshixo sedatha yenodi X ngokwayo.

Ngundoqo — naluphi na uphawu lwenode (umzekelo, inani). Isitshixo siyafuneka ukuze ufumane into yomthi apho eli qhosha lihambelana khona. Umzekelo womthi wophendlo wokubini:

Umbono womthi

Njengoko siqhubela phambili, ndiza kubonelela ngamacandelo athile ekhowudi (ekunokwenzeka ukuba angaphelelanga) ukuphucula ukuqonda kwakho. Ikhowudi epheleleyo iya kuba ekupheleni kwenqaku.

Umthi unamaqhuqhuva. Ulwakhiwo lweNode:

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 nganye inabantwana ababini (kusenokwenzeka ukuba uMntwana wasekhohlo kunye/okanye umntwana wasekunene uya kuqulatha ixabiso elingento). Mhlawumbi uqaphele ukuba kule meko idatha yenombolo yidatha egcinwe kwi-node; iqhosha - iqhosha le-node.

Siye salungisa iqhina, ngoku makhe sithethe ngeengxaki ezicinezelayo ngemithi. Emva koku, ngegama elithi "umthi" ndiya kuthetha ingcamango yomthi wokukhangela ibhinari. Ubume bomthi kanambambili:

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

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

Sifuna kuphela ingcambu yomthi njengentsimi yeklasi, kuba ukusuka kwingcambu, usebenzisa i-getLeftChild () kunye ne-getRightChild () iindlela, unako ukufikelela kuyo nayiphi na i-node emthini.

Ii-algorithms emthini

search

Masithi unomthi owakhiweyo. Indlela yokufumana into eneqhosha elingundoqo? Udinga ukuhamba ngokulandelelanayo ukusuka kwingcambu phantsi komthi kwaye uthelekise ixabiso lesitshixo kunye nesitshixo se-node elandelayo: ukuba isitshixo singaphantsi kwesitshixo se-node elandelayo, emva koko uye kwisizukulwana sasekhohlo se-node, ukuba sinjalo. enkulu, ukuya ekunene, ukuba izitshixo ziyalingana, i-node efunwayo ifunyenwe! Ikhowudi efanelekileyo:

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

Ukuba i-current iba yinto engekhoyo, ngoko ukukhangela kuye kwafikelela ekupheleni komthi (kwinqanaba lengqiqo, ukwindawo engekho emthini - umntwana weqabunga).

Makhe siqwalasele ukusebenza kwe-algorithm yokukhangela kumthi olinganiselayo (umthi apho ii-nodes zisasazwa ngaphezulu okanye ngaphantsi ngokulinganayo). Emva koko umsebenzi wokukhangela uya kuba ngu-O(log(n)), kwaye i-logarithm yisiseko sesi-2. Jonga: ukuba kukho izakhi ze-n kumthi olungelelanisiweyo, oku kuthetha ukuba kuya kubakho ilog(n) ukusekela amanqanaba ama-2 umthi. Kwaye ekukhangeleni, kwinqanaba elinye lomjikelo, uyehla kwinqanaba elinye.

Faka

Ukuba ubamba undoqo wokukhangela, ngoko ukuqonda ukufakwa akuyi kuba nzima kuwe. Udinga nje ukuhla kwiqabunga lomthi (ngokwemigaqo yokwehla echazwe kwi-search) kwaye ube yinzala yayo - ekhohlo okanye ekunene, kuxhomekeke kwisitshixo. Ukuphunyezwa:

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

Kule meko, ukongeza kwi-node yangoku, kuyimfuneko ukugcina ulwazi malunga nomzali we-node yangoku. Xa yangoku ilingana no-null, umahluko womzali uya kuqulatha iphepha esilidingayo.
Ukusebenza kakuhle kokufaka ngokuqinisekileyo kuya kufana nokukhangela - O(log(n)).

Ukususwa

Ukususwa ngowona msebenzi unzima kakhulu kuya kufuneka ukuba wenziwe emthini. Kucacile ukuba okokuqala kuya kufuneka sifumane into esiza kuyicima. Kodwa kuthekani? Ukuba sibeka ngokulula ireferensi yayo kwi-null, siya kuphulukana nolwazi malunga nomthi ongaphantsi apho le node iyingcambu. Iindlela zokususa imithi zohlulwe zibe ziimeko ezintathu.

Imeko yokuqala. Indawo ecinyiweyo ayinabantwana

Ukuba i-node iyacinywa ayinabantwana, ke oku kuthetha ukuba ligqabi. Ke ngoko, unokuseta ngokulula Umntwana wasekhohlo okanye ekunene amabala omzali wakhe ukuba angasebenzi.

Ityala lesibini. Indawo ezakucinywa inomntwana omnye

Eli tyala nalo alikho nzima kakhulu. Masibuyele kumzekelo wethu. Masithi kufuneka sicime isitshixo ngesitshixo esingu-14. Vuma ukuba njengoko iyinzalo elungileyo yenodi eneqhosha u-10, ngoko nayiphi na inzala yayo (kule meko ekunene) izakuba nesitshixo esikhulu kuno-10, ngoko ke ngokulula "ukusika" ngaphandle komthi, kwaye udibanise umzali ngokuthe ngqo kumntwana we-node ecinyiweyo, i.e. qhagamshela i-node kunye nesitshixo se-10 kwi-node ye-13. Imeko iya kufana ukuba bekufuneka ukucima i-node engumntwana osekhohlo womzali wayo. Cinga ngayo ngokwakho - isifaniso esichanekileyo.

Ityala lesithathu. I-node inabantwana ababini

Elona tyala linzima. Makhe sijonge umzekelo omtsha.

Khangela umntu oza kungena ezihlangwini zakhe

Masithi kufuneka sicime i-node ngesitshixo esingu-25. Ngubani esifanele simbeke endaweni yayo? Umele abe ngomnye wabalandeli bakhe (inzala okanye inzala). ilandela(lowo uya kuthatha indawo yokususwa kwe node).

Indlela yokuqonda ukuba ngubani omele abe yindlalifa? Intuitively, le node emthini osisitshixo silandelayo sikhulu ukusuka kwindawo ecinyiweyo. I-algorithm ilandelayo. Kufuneka uye kwinzala yayo yasekunene (usoloko uye ekunene, kuba sele kuthiwe isitshixo somlandeli sikhulu kunesitshixo se-node esicinyiweyo), kwaye emva koko uhambe ngekhonkco lenzala yasekhohlo yale nzala yasekunene. . Kumzekelo, besiya kwi node ngesitshixo 35, size siye ezantsi egqabeni ngokusebenzisa umxokelelwane wabantwana basekhohlo - kulo mzekelo, eli khonkco iqulathe kuphela node isitshixo 30. Ukuthetha ngokuthe ngqo, sijonge. kweyona nodi incinci kwiseti yeendawo ezinkulu kunezo sijonga i node.

Ikhowudi yendlela yokukhangela yokulandela:

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

Ikhowudi epheleleyo yendlela yokucima:

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

Ukuntsokotha kunokuqikelelwa ku-O(log(n)).

Ukufumana ubuninzi/ubuncinane emthini

Kucacile ukuba ungalifumana njani elona xabiso liphantsi/elona liphezulu emthini - kufuneka uhambe ngokulandelelanayo ecaleni kwekhonkco lezinto ezisekhohlo/ekunene zomthi, ngokulandelelanayo; xa ufika kwiphepha, iyakuba yeyona nto incinci/eyona nto iphezulu.

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

Ukuntsokotha-O(log(n))

I-Symmetrical bypass

I-Traversal indwendwela indawo nganye yomthi ukuze yenze intshukumo ngayo.

I-algorithm ye-recursive symmetric traversal:

Yenza isenzo kumntwana osekhohlo
Yenza intshukumo nawe
Yenza isenzo kumntwana ofanelekileyo

Ikhowudi:

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

isiphelo

Ekugqibeleni! Ukuba andizange ndichaze nantoni na okanye ndinezimvo, nceda ushiye kwizimvo. Njengoko ndithembisile, ndinikezela ngekhowudi epheleleyo.

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

Ukuncipha ukuya ku-O(n)

Abaninzi benu basenokuba baye baqaphela: kuthekani ukuba wenza umthi ungalingani? Umzekelo, faka ii-nodes kunye nezitshixo ezikhulayo emthini: 1,2,3,4,5,6... Emva koko umthi uya kufana noluhlu oludityanisiweyo. Kwaye ewe, umthi uya kulahlekelwa isakhiwo sawo somthi, kwaye ngoko ke ukusebenza kakuhle kokufikelela kwedatha. Ukuntsokotha kokukhangela, ukufakela, kunye nokusebenza kocimo kuya kufana noluhlu oludityanisiweyo: O(n). Le ngenye yezona zinto zibalulekileyo, ngokombono wam, ukungahambi kakuhle kwemithi yokubini.

Ngabasebenzisi ababhalisiweyo kuphela abanokuthatha inxaxheba kuphando. Ngena, ndiyacela.

Andizange ndibe kwi-hub ixesha elide, kwaye ndingathanda ukwazi ukuba ngawaphi amanqaku malunga nezihloko ongathanda ukuzibona ngakumbi?

Ulwakhiwo lwedatha
Ii-algorithms (i-DP, i-recursion, uxinzelelo lwedatha, njl.)
Ukusetyenziswa kolwakhiwo lwedatha kunye ne-algorithms ebomini bokwenyani
Ukucwangcisa iiNkqubo ze-Android kwiJava
Ukucwangcisa usetyenziso lwewebhu kwiJava

Bayi-2 abasebenzisi abavotileyo. Abasebenzisi abangama-1 abakhange.

Umthombo: www.habr.com

Umthi weBhinary okanye indlela yokulungisa umthi wokukhangela ibhinary