ProHoster > blog > Utawala > Binary Tree au jinsi ya kuandaa mti wa utafutaji wa binary

Binary Tree au jinsi ya kuandaa mti wa utafutaji wa binary

Uonyesho

Makala hii ni kuhusu miti ya utafutaji ya binary. Hivi majuzi niliandika makala kuhusu ukandamizaji wa data kwa njia ya Huffman. Huko sikuzingatia sana miti ya binary, kwa sababu mbinu za kutafuta, kuingiza, kufuta hazikufaa. Sasa niliamua kuandika makala kuhusu miti. Labda tutaanza.

Mti ni muundo wa data unaojumuisha nodi zilizounganishwa na kingo. Tunaweza kusema kwamba mti ni kesi maalum ya grafu. Hapa kuna mfano wa mti:

Binary Tree au jinsi ya kuandaa mti wa utafutaji wa binary

Huu sio mti wa utaftaji wa binary! Kila kitu ni chini ya kukata!

Terminology

Mizizi

Mzizi wa mti ni nodi ya juu zaidi. Kwa mfano, hii ni node A. Katika mti, njia moja tu inaweza kuongoza kutoka mizizi hadi node nyingine yoyote! Kwa kweli, nodi yoyote inaweza kuzingatiwa kama mzizi wa mti mdogo unaolingana na nodi hii.

Wazazi/watoto

Nodi zote isipokuwa mzizi zina kingo moja inayoelekea kwenye nodi nyingine. Node juu ya node ya sasa inaitwa mzazi nodi hii. Node iko chini ya sasa na kushikamana nayo inaitwa mjukuu nodi hii. Hebu tuchukue mfano. Chukua nodi B, kisha mzazi wake atakuwa nodi A, na watoto wake watakuwa nodi D, E, na F.

Leaf

Node ambayo haina watoto inaitwa jani la mti. Kwa mfano, nodes D, E, F, G, I, J, K zitakuwa majani.

Hii ndiyo istilahi ya msingi. Dhana zingine zitajadiliwa baadaye. Kwa hivyo, mti wa binary ni mti ambao kila nodi haitakuwa na watoto zaidi ya wawili. Kama ulivyodhani, mti kutoka kwa mfano hautakuwa wa binary, kwa sababu nodi B na H zina watoto zaidi ya wawili. Hapa kuna mfano wa mti wa binary:

Binary Tree au jinsi ya kuandaa mti wa utafutaji wa binary

Nodi za mti zinaweza kuwa na habari yoyote. Mti wa utaftaji wa binary ni mti wa binary ambao una sifa zifuatazo:

  1. Miti ndogo ya kushoto na kulia ni miti ya utafutaji ya binary.
  2. Nodi zote za mti mdogo wa kushoto wa nodi ya kiholela X zina thamani za vitufe vya data chini ya thamani ya ufunguo wa data ya nodi X yenyewe.
  3. Nodi zote za mti mdogo wa kulia wa nodi X zina thamani za vitufe vya data kubwa kuliko au sawa na thamani ya ufunguo wa data wa nodi X yenyewe.

Muhimu - tabia fulani ya node (kwa mfano, nambari). Ufunguo unahitajika ili kuweza kupata kipengele cha mti ambacho ufunguo huu unalingana. Mfano wa mti wa utaftaji wa binary:

Binary Tree au jinsi ya kuandaa mti wa utafutaji wa binary

mtazamo wa mti

Ninapoendelea, nitajumuisha vipande (labda visivyo kamili) vya msimbo ili kuboresha uelewa wako. Nambari kamili itakuwa mwishoni mwa kifungu.

Mti huu umeundwa na nodi. Muundo wa nodi:

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;
    }
//...ΠΎΡΡ‚Π°Π»ΡŒΠ½Ρ‹Π΅ ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ ΡƒΠ·Π»Π°
}

Kila nodi ina watoto wawili (inawezekana kabisa kwamba mtoto wa kushoto na/au mtoto wa kulia atakuwa batili). Labda ulielewa kuwa katika kesi hii data ya nambari ni data iliyohifadhiwa kwenye nodi; ufunguo - ufunguo wa nodi.

Tuligundua fundo, sasa hebu tuzungumze juu ya shida kubwa juu ya miti. Baadaye, neno "mti" litamaanisha wazo la mti wa utaftaji wa binary. Muundo wa mti wa binary:

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

    //ΠΌΠ΅Ρ‚ΠΎΠ΄Ρ‹ Π΄Π΅Ρ€Π΅Π²Π°
}

Kama uwanja wa darasa, tunahitaji tu mzizi wa mti, kwa sababu kutoka kwa mzizi, kwa kutumia getLeftChild() na getRightChild() mbinu, unaweza kupata nodi yoyote ya mti.

Algorithms ya miti

Tafuta

Wacha tuseme una mti uliojengwa. Jinsi ya kupata kipengee na ufunguo muhimu? Unahitaji kuhama kutoka kwa mzizi chini ya mti na kulinganisha thamani ya ufunguo na ufunguo wa nodi inayofuata: ikiwa ufunguo ni chini ya ufunguo wa nodi inayofuata, kisha nenda kwa kizazi cha kushoto cha nodi, ikiwa zaidi - kwa kulia, ikiwa funguo ni sawa - node inayotaka inapatikana! Msimbo husika:

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

Ikiwa sasa inakuwa null, basi iteration imefikia mwisho wa mti (katika ngazi ya dhana, wewe ni mahali ambapo haipo kwenye mti - mtoto wa jani).

Fikiria ufanisi wa algorithm ya utafutaji kwenye mti wa usawa (mti ambao nodes zinasambazwa zaidi au chini sawasawa). Kisha ufanisi wa utafutaji utakuwa O (logi (n)), na msingi wa logarithm 2. Angalia: ikiwa kuna vipengele vya n katika mti wa usawa, basi hii ina maana kwamba kutakuwa na logi (n) msingi ngazi 2 za mti. Na katika utafutaji, kwa hatua moja ya mzunguko, unashuka ngazi moja.

kuingiza

Ikiwa umefahamu kiini cha utafutaji, basi haitakuwa vigumu kwako kuelewa kuingizwa. Unahitaji tu kwenda chini kwenye jani la mti (kulingana na sheria za asili zilizoelezwa katika utafutaji) na kuwa mzao wake - kushoto au kulia, kulingana na ufunguo. Utekelezaji:

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

Katika kesi hii, pamoja na node ya sasa, ni muhimu kuhifadhi habari kuhusu mzazi wa node ya sasa. Wakati sasa inakuwa batili, utofauti wa mzazi utakuwa na laha tunayohitaji.
Ufanisi wa kuingizwa bila shaka utakuwa sawa na ule wa utafutaji - O(logi(n)).

Kuondolewa

Kufuta ni operesheni ngumu zaidi ambayo itahitajika kufanywa na mti. Ni wazi kwamba kwanza itakuwa muhimu kupata kipengele ambacho tutaondoa. Lakini basi nini? Ikiwa tutaweka tu rejeleo lake kwa null, basi tutapoteza habari kuhusu mti mdogo ambao mzizi wake ni nodi hii. Njia za kuondolewa kwa miti zimegawanywa katika kesi tatu.

Kesi ya kwanza. Node ya kuondolewa haina watoto.

Ikiwa node ya kufutwa haina watoto, inamaanisha kuwa ni jani. Kwa hivyo, unaweza kuweka tu sehemu za leftChild au rightChild za mzazi wake kubatilisha.

Kesi ya pili. Node ya kuondolewa ina mtoto mmoja

Kesi hii pia sio ngumu sana. Hebu turudi kwenye mfano wetu. Tuseme tunahitaji kufuta kipengele na ufunguo 14. Kubali kwamba kwa kuwa ni mtoto sahihi wa nodi na ufunguo 10, basi kizazi chake chochote (katika kesi hii, haki) kitakuwa na ufunguo zaidi ya 10, kwa hivyo wewe. inaweza "kukata" kwa urahisi kutoka kwa mti, na kuunganisha mzazi moja kwa moja kwa mtoto wa node inayofutwa, i.e. unganisha node na ufunguo 10 hadi node 13. Hali itakuwa sawa ikiwa tunapaswa kufuta node ambayo ni mtoto wa kushoto wa mzazi wake. Fikiria juu yako mwenyewe - mlinganisho halisi.

Kesi ya tatu. Node ina watoto wawili

Kesi ngumu zaidi. Hebu tuangalie mfano mpya.

Binary Tree au jinsi ya kuandaa mti wa utafutaji wa binary

Tafuta mrithi

Hebu tuseme tunahitaji kuondoa nodi kwa ufunguo 25. Tutaweka nani mahali pake? Mmoja wa wafuasi wake (wazao au wazao) lazima awe mrithi(yule ambaye atachukua nafasi ya node iliyoondolewa).

Unajuaje nani anafaa kuwa mrithi? Intuitively, hii ni nodi katika mti ambao ufunguo ni mkubwa zaidi kutoka kwa nodi inayoondolewa. Algorithm ni kama ifuatavyo. Unahitaji kwenda kwa mtoto wake wa kulia (daima kwa yule wa kulia, kwa sababu tayari ilisemwa kuwa ufunguo wa mrithi ni mkubwa kuliko ufunguo wa nodi inayofutwa), na kisha pitia mlolongo wa watoto wa kushoto wa haki hii. mtoto. Katika mfano, lazima tuende kwenye nodi na ufunguo 35, na kisha uende chini ya mlolongo wa watoto wake wa kushoto kwenye jani - katika kesi hii, mnyororo huu unajumuisha tu nodi na ufunguo 30. Kwa kusema, tunatafuta. nodi ndogo zaidi katika seti ya nodi kubwa kuliko nodi inayotaka.

Binary Tree au jinsi ya kuandaa mti wa utafutaji wa binary

Msimbo wa njia ya utafutaji wa mrithi:

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

Nambari kamili ya njia ya kufuta:

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

Utata unaweza kukadiriwa kuwa O(logi(n)).

Kupata kiwango cha juu/cha chini kwenye mti

Kwa wazi, jinsi ya kupata thamani ya chini / ya juu kwenye mti - unahitaji kupitia mlolongo wa vipengele vya kushoto / kulia vya mti, kwa mtiririko huo; unapofika kwenye jani, itakuwa kipengele cha chini/kiwango cha juu zaidi.

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

Utata - O(logi(n))

Njia ya ulinganifu

Traversal ni kutembelea kila nodi ya mti ili kufanya kitu nayo.

Algorithm ya kurudia ya ulinganifu wa ulinganifu:

  1. Fanya kitendo kwa mtoto wa kushoto
  2. Fanya hatua na wewe mwenyewe
  3. Fanya hatua kwa mtoto sahihi

Code:

    public void inOrder(Node<T> current) {
        if (current != null) {
            inOrder(current.getLeftChild());
            System.out.println(current.getData() + " ");//Π—Π΄Π΅ΡΡŒ ΠΌΠΎΠΆΠ΅Ρ‚ Π±Ρ‹Ρ‚ΡŒ всС, Ρ‡Ρ‚ΠΎ ΡƒΠ³ΠΎΠ΄Π½ΠΎ
            inOrder(current.getRightChild());
        }
    }

Hitimisho

Hatimaye! Ikiwa sikuelezea kitu au kuwa na maoni yoyote, basi ninasubiri kwenye maoni. Kama ilivyoahidiwa, hapa kuna nambari kamili.

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

Kupungua kwa O(n)

Wengi wenu wanaweza kuwa wameona: ni nini ikiwa unafanya mti kuwa usio na usawa? Kwa mfano, weka nodes kwenye mti na funguo zinazoongezeka: 1,2,3,4,5,6 ... Kisha mti utakuwa kukumbusha kwa kiasi fulani orodha iliyounganishwa. Na ndiyo, mti utapoteza muundo wake wa mti, na hivyo ufanisi wa upatikanaji wa data. Utata wa shughuli za utafutaji, uwekaji na ufutaji utakuwa sawa na ule wa orodha iliyounganishwa: O(n). Hii ni moja ya muhimu zaidi, kwa maoni yangu, hasara za miti ya binary.

Watumiaji waliojiandikisha pekee ndio wanaweza kushiriki katika utafiti. Weka sahihitafadhali.

Sijamtumia Habre kwa muda mrefu, na ningependa kujua ni makala gani kuhusu mada gani ungependa kuona zaidi?

  • Miundo ya data

  • Algorithms (DP, recursion, compression data, nk)

  • Utumiaji wa miundo ya data na algoriti katika maisha halisi

  • Kupanga programu za android katika Java

  • Utayarishaji wa Programu ya Wavuti ya Java

Watumiaji 2 walipiga kura. Mtumiaji 1 alijizuia.

Chanzo: www.habr.com

Kuongeza maoni