ProHoster > Блог > Nchịkwa > Osisi ọnụọgụ abụọ ma ọ bụ otu esi akwadebe osisi ọchụchọ ọnụọgụ abụọ

Osisi ọnụọgụ abụọ ma ọ bụ otu esi akwadebe osisi ọchụchọ ọnụọgụ abụọ

Egwuru egwu

Edemede a bụ maka osisi ọchụchọ ọnụọgụ abụọ. M dere na nso nso a isiokwu banyere mkpakọ data site na usoro Huffman. N'ebe ahụ, anaghị m ege ntị n'ezie na osisi ọnụọgụ abụọ, n'ihi na usoro nke ịchọ, ntinye, ihichapụ adịghị mkpa. Ugbu a, ekpebiri m ide otu isiokwu banyere osisi. Ikekwe anyị ga-amalite.

Osisi bụ nhazi data nwere ọnụ ọnụ jikọtara ọnụ. Anyị nwere ike ịsị na osisi bụ ihe pụrụ iche nke eserese. Nke a bụ osisi ọmụmaatụ:

Osisi ọnụọgụ abụọ ma ọ bụ otu esi akwadebe osisi ọchụchọ ọnụọgụ abụọ

Nke a abụghị osisi ọchụchọ ọnụọgụ abụọ! Ihe niile dị n'okpuru ịkpụ!

Usoro ihe omuma

Mgbọrọgwụ

mgbọrọgwụ osisi bụ ọnụ ọnụ kacha elu. N'ihe atụ, nke a bụ ọnụ A. N'ime osisi ahụ, ọ bụ naanị otu ụzọ nwere ike isi na mgbọrọgwụ gaa na ọnụ ụzọ ọ bụla ọzọ! N'ezie, ọnụ ụzọ ọ bụla nwere ike weere dị ka mgbọrọgwụ nke subtree kwekọrọ na ọnụ a.

Nne na nna/ụmụ

Ọnụ niile ma e wezụga mgbọrọgwụ nwere kpọmkwem otu ọnụ na-eduga n'ọnụ ọzọ. A na-akpọ ọnụ dị n'elu ọnụ ọnụ ugbu a nne na nna ọnụ a. A na-akpọ ọnụ nke dị n'okpuru nke dị ugbu a ma jikọọ na ya ụmụ ọnụ a. Ka anyị were ihe atụ. Were ọnụ B, mgbe ahụ nne na nna ya ga-abụ ọnụ A, ụmụ ya ga-abụ ọnụ D, E, na F.

Akwụkwọ

A na-akpọ ọnụ nke na-enweghị ụmụ akwụkwọ osisi. N'ihe atụ, ọnụ D, E, F, G, I, J, K ga-abụ akwụkwọ.

Nke a bụ isi okwu okwu. A ga-atụle echiche ndị ọzọ ma emechaa. Ya mere, osisi ọnụọgụ abụọ bụ osisi nke oghere ọ bụla ga-enwe ihe karịrị ụmụ abụọ. Dị ka ị chere, osisi site na ihe atụ agaghị abụ ọnụọgụ abụọ, n'ihi na ọnụ B na H nwere ihe karịrị ụmụ abụọ. Nke a bụ ọmụmaatụ nke osisi ọnụọgụ abụọ:

Osisi ọnụọgụ abụọ ma ọ bụ otu esi akwadebe osisi ọchụchọ ọnụọgụ abụọ

Ọnụ osisi ahụ nwere ike ịnwe ozi ọ bụla. Osisi ọchụchọ ọnụọgụ abụọ bụ osisi ọnụọgụ abụọ nwere ihe ndị a:

  1. Osisi abụọ aka ekpe na aka nri bụ osisi ọchụchọ ọnụọgụ abụọ.
  2. Ọnụ ụzọ niile nke akụkụ aka ekpe nke ọnụ X aka ike nwere ụkpụrụ igodo data erughị uru igodo data nke ọnụ X n'onwe ya.
  3. Ọnụ ụzọ niile nke akụkụ aka nri nke ọnụ X aka ike nwere ụkpụrụ isi data karịa ma ọ bụ ha nhata uru igodo data nke ọnụ X n'onwe ya.

Igodo - ụfọdụ njirimara ọnụ (dịka ọmụmaatụ, nọmba). A choro igodo iji nwee ike ichota mmewere nke osisi nke igodo a kwekọrọ. Ihe atụ osisi ọchụchọ ọnụọgụ abụọ:

Osisi ọnụọgụ abụọ ma ọ bụ otu esi akwadebe osisi ọchụchọ ọnụọgụ abụọ

osisi anya

Ka m na-aga, m ga-etinye koodu ụfọdụ (ikekwe ezughị ezu) iji meziwanye nghọta gị. Koodu zuru ezu ga-adị na njedebe nke akụkọ.

Osisi ahụ bụ ọnụ ọnụ. Ọdịdị ọnụ:

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

Ọnụ ọnụ nke ọ bụla nwere ụmụ abụọ (ọ ga-ekwe omume na nwata na/ma ọ bụ aka nri ụmụaka ga-abụ ihe efu). O nwere ike ịbụ na ị ghọtara na na nke a data ọnụọgụ bụ data echekwara na ọnụ; igodo - igodo ọnụ.

Anyị chepụtara eriri ahụ, ugbu a, ka anyị kwuo banyere nsogbu ndị na-egbu mgbu banyere osisi. Mgbe nke a gachara, okwu ahụ bụ "osisi" ga-apụta echiche nke osisi ọchụchọ ọnụọgụ abụọ. Nhazi osisi ọnụọgụ abụọ:

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

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

Dị ka ubi klas, anyị chọrọ naanị mgbọrọgwụ osisi ahụ, n'ihi na site na mgbọrọgwụ, na-eji usoro getLeftChild () na getRightChild (), ị nwere ike ịbanye n'akụkụ ọ bụla nke osisi ahụ.

Algorithms osisi

Поиск

Ka anyị kwuo na ị nwere osisi wuru. Kedu ka esi achọta mmewere na igodo igodo? Ịkwesịrị ịkwaga n'usoro site na mgbọrọgwụ n'ala osisi ahụ wee tụnyere uru igodo ya na igodo nke ọnụ ụzọ na-esote: ọ bụrụ na igodo erughị igodo nke ọnụ ụzọ na-esote, gaa na nwa aka ekpe nke ọnụ, ma ọ bụrụ na karịa - n'aka nri, ma ọ bụrụ na igodo ha nhata - a na-achọta oghere a chọrọ! Koodu dị mkpa:

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

Ọ bụrụ na ugbu a na-aghọ efu, mgbe ahụ iteration eruwo na njedebe nke osisi (na a echiche larịị, ị nọ na a na-adịghị adị ebe na osisi - nwa akwukwo).

Tụlee arụmọrụ nke algorithm ọchụchọ na osisi kwesịrị ekwesị (osisi nke ọnụ na-ekesa karịa ma ọ bụ obere). Mgbe ahụ, arụmọrụ ọchụchọ ga-abụ O (log(n)), na isi 2 logarithm. Lee: ọ bụrụ na e nwere n ọcha na osisi kwesịrị ekwesị, nke a pụtara na a ga-enwe log (n) base 2 ọkwa nke osisi. Na na nchọta, maka otu nzọụkwụ nke okirikiri, ị na-agbada otu ọkwa.

fanye

Ọ bụrụ na ị ghọtara isi ihe nke ọchụchọ ahụ, mgbe ahụ ọ gaghị esiri gị ike ịghọta ntinye. Naanị ị ga-agbada na akwukwo osisi (dị ka iwu nke usoro ọmụmụ nke akọwapụtara na ọchụchọ) wee bụrụ ụmụ ya - aka ekpe ma ọ bụ aka nri, dabere na igodo. Mmejuputa:

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

N'okwu a, na mgbakwunye na ọnụ ọnụ ugbu a, ọ dị mkpa ịchekwa ozi gbasara nne na nna nke ọnụ ọnụ ugbu a. Mgbe nke ugbu a ghọrọ ihe efu, mgbanwe nne na nna ga-enwe mpempe akwụkwọ anyị chọrọ.
O doro anya na ntinye ntinye ga-adị ka nke ọchụchọ - O(log(n)).

Hichapụ

Nhichapụ bụ ọrụ kachasị mgbagwoju anya nke a ga-achọ iji osisi mee ya. O doro anya na mbụ ọ ga-adị mkpa ịchọta mmewere nke anyị ga-ewepụ. Ma gịnịzi? Ọ bụrụ na anyị edobe ntụaka ya na efu, mgbe ahụ anyị ga-atụfu ozi gbasara subtree nke mgbọrọgwụ ya bụ ọnụ. A na-ekewa ụzọ iwepụ osisi ụzọ atọ.

Ikpe mbụ. Ọnụ a ga-ewepụ enweghị ụmụaka.

Ọ bụrụ na ọnụ a ga-ehichapụ enweghị ụmụaka, ọ pụtara na ọ bụ akwụkwọ. Ya mere, ị nwere ike ịtọ ntọala nwata aka ekpe ma ọ bụ aka nri nke nne na nna ya ka ọ bụrụ ihe efu.

Ikpe nke abụọ. Ọnụ a ga-ewepụ nwere otu nwa

Ikpe a esighịkwa ike nke ukwuu. Ka anyị laghachi azụ n'ihe atụ anyị. Were ya na anyị kwesịrị ihichapụ ihe mmewere na igodo 14. Kweta na ebe ọ bụ nwa ziri ezi nke ọnụ ọnụ na igodo 10, mgbe ahụ onye ọ bụla n'ime ụmụ ya (na nke a, nke ziri ezi) ga-enwe igodo karịrị 10, yabụ ị nwere ike "bee" ya n'ụzọ dị mfe site na osisi, ma jikọọ nne na nna ozugbo na nwa nke ọnụ ọnụ na-ehichapụ, i.e. jikọọ ọnụ na igodo 10 ruo ọnụ 13. Ọnọdụ ahụ ga-adị ka ọ bụrụ na anyị ga-ehichapụ ọnụ nke bụ nwa aka ekpe nke nne na nna ya. Chee echiche banyere ya n'onwe gị - ihe atụ ziri ezi.

Ikpe nke atọ. Node nwere ụmụ abụọ

Ikpe kacha sie ike. Ka anyị leba anya n'ihe atụ ọhụrụ.

Osisi ọnụọgụ abụọ ma ọ bụ otu esi akwadebe osisi ọchụchọ ọnụọgụ abụọ

Chọọ onye ga-anọchi ya

Ka anyị kwuo na anyị kwesịrị iji igodo wepụ ọnụ ọnụ 25. Ònye ka anyị ga-etinye n'ọnọdụ ya? Otu n'ime ụmụazụ ya (ụmụ ma ọ bụ ụmụ ụmụ) ga-abụrịrị onye nọchiri anya ya(onye ga-ewere ọnọdụ nke oghere ewepụrụ).

Olee otú ị ga-esi mara onye kwesịrị ịbụ onye ga-anọchi anya ya? N'uche, nke a bụ ọnụ dị n'osisi ahụ nke igodo ya bụ nke na-esote kachasị na ọnụ na-ewepụ. Algọridim dị ka ndị a. Ịkwesịrị ịga na nwa ya aka nri (mgbe niile gaa n'aka nri, n'ihi na e kwuworị na igodo nke onye ga-anọchi ya dị ukwuu karịa igodo nke ọnụ na-ehichapụ), wee gaa n'agbụ nke ụmụaka aka ekpe nke a. nwa. N'ihe atụ, anyị ga-aga ọnụ na igodo 35, wee gbadaa agbụ nke ụmụ ya ekpe na akwukwo - na nke a, a yinye mejupụtara naanị ọnụ ọnụ na igodo 30. N'ikwu ya n'ụzọ ziri ezi, anyị na-achọ. ọnụ ọnụ kacha nta na nhazi ọnụ ọnụ karịa ọnụ ọnụ achọrọ.

Osisi ọnụọgụ abụọ ma ọ bụ otu esi akwadebe osisi ọchụchọ ọnụọgụ abụọ

Koodu usoro ọchụchọ onye ga-anọchi anya:

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

Koodu zuru oke nke usoro ihichapụ:

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

Enwere ike itinye mgbagwoju anya na O(log(n)).

Ịchọta kacha / kacha nta na osisi

N'ụzọ doro anya, otu esi achọta uru kacha nta / kachasị na osisi - ịkwesịrị ịga n'usoro site na agbụ nke akụkụ aka ekpe / aka nri nke osisi ahụ, n'otu n'otu; mgbe ị rutere na akwukwo, ọ ga-abụ ihe kacha nta / kacha.

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

Mgbagwoju anya - O(log(n))

Nbanye Symmetric

Traversal bụ nleta na ọnụ osisi ọ bụla iji mee ihe na ya.

Algọridim traversal symmetrical ugboro ugboro:

  1. Mee ihe na nwa aka ekpe
  2. Mee ihe na onwe gị
  3. Mee ihe na nwa ziri ezi

Koodu:

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

nkwubi

N'ikpeazụ! Ọ bụrụ na akọwaghị m ihe ma ọ bụ nwee nkọwa ọ bụla, mgbe ahụ, m na-echere na nkwupụta. Dị ka e kwere ná nkwa, ebe a bụ koodu zuru ezu.

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

Mmebi gaa na O(n)

Ọtụtụ n'ime unu nwere ike chọpụtala: gịnị ma ọ bụrụ na ị na-eme ka osisi ahụ bụrụ ihe na-adịghị mma? Dịka ọmụmaatụ, tinye ọnụ n'ime osisi na igodo na-abawanye: 1,2,3,4,5,6... Mgbe ahụ, osisi ahụ ga-adịtụ icheta ndepụta ejikọtara. Ma ee, osisi ahụ ga-atụfu usoro osisi ya, ya mere arụmọrụ nke ịnweta data. Mgbagwoju anya nke ọchụchọ, ntinye, na ọrụ nhichapụ ga-adị ka nke ndepụta ejikọtara: O(n). Nke a bụ otu n'ime ihe kachasị mkpa, n'echiche m, adịghị ike nke osisi ọnụọgụ abụọ.

Naanị ndị ọrụ edebanyere aha nwere ike isonye na nyocha a. banye, Biko.

Anọbeghị m na Habré ogologo oge, ọ ga-amasị m ịmata isiokwu ndị gbasara isiokwu ndị ga-amasị gị ịhụkwu?

  • Ọdịdị data

  • Algorithms (DP, recursion, mkpakọ data, wdg)

  • Ngwa nke usoro data na algọridim na ndụ n'ezie

  • Ịmepụta ngwa android na Java

  • Mmemme Ngwa Weebụ Java

Ndị ọrụ 2 tụrụ vootu. 1 onye ọrụ anabataghị.

Isi mmalite: www.habr.com

Tinye a comment