ProHoster > Π‘Π»ΠΎΠ³ > Administrasi > Binary Tree utawa carane nyiyapake wit telusuran binar

Binary Tree utawa carane nyiyapake wit telusuran binar

Pambuka

Artikel iki babagan wit telusuran binar. Aku bubar nggawe artikel babagan kompresi data nggunakake metode Huffman. Ing kana aku ora nggatekake wit binar, amarga metode telusuran, penyisipan, lan pambusakan ora cocog. Saiki aku mutusake kanggo nulis artikel babagan wit. Ayo dadi miwiti.

Wit minangka struktur data sing kasusun saka node sing disambungake kanthi pinggir. Kita bisa ngomong yen wit minangka kasus khusus saka grafik. Punika conto wit:

Binary Tree utawa carane nyiyapake wit telusuran binar

Iki dudu wit telusuran binar! Kabeh dipotong!

Istilah kasebut

Root

Oyod wit - iki simpul paling dhuwur. Ing conto, iki simpul A. Ing wit, mung siji path bisa mimpin saka ROOT menyang simpul liyane! Nyatane, simpul apa wae bisa dianggep minangka oyod saka subtree sing cocog karo simpul iki.

Wong tuwa/turune

Kabeh simpul kajaba oyod duwe persis siji pinggiran menyang simpul liyane. Simpul sing ana ing sadhuwure saiki diarani wong tuwa simpul iki. Node sing ana ing sangisore sing saiki lan disambungake diarani keturunan simpul iki. Ayo nganggo conto. Ayo njupuk simpul B, banjur wong tuwane bakal dadi simpul A, lan anak-anake bakal dadi simpul D, E lan F.

Rwaning

Simpul sing ora duwe anak bakal diarani godhong wit. Ing conto, godhong bakal dadi simpul D, E, F, G, I, J, K.

Iki minangka terminologi dhasar. Konsep liyane bakal dibahas luwih lanjut. Dadi, wit binar minangka wit sing saben simpul ora duwe anak luwih saka loro. Kaya sing sampeyan bayangake, wit saka conto kasebut ora bakal binar, amarga simpul B lan H duwe luwih saka rong anak. Punika conto wit binar:

Binary Tree utawa carane nyiyapake wit telusuran binar

Node wit bisa ngemot informasi apa wae. Wit telusuran binar yaiku wit binar sing nduweni sifat ing ngisor iki:

  1. Subtree kiwa lan tengen minangka wit telusuran binar.
  2. Kabeh simpul subtree kiwa saka simpul X sing sewenang-wenang nduweni nilai kunci data sing kurang saka nilai kunci data simpul X dhewe.
  3. Kabeh simpul ing subtree sisih tengen simpul X duwe nilai kunci data sing luwih gedhe tinimbang utawa padha karo nilai kunci data simpul X dhewe.

Kunci - sembarang karakteristik simpul (contone, nomer). Tombol dibutuhake supaya sampeyan bisa nemokake unsur wit sing cocog karo tombol iki. Conto wit telusuran binar:

Binary Tree utawa carane nyiyapake wit telusuran binar

Pemandangan wit

Nalika kita maju, aku bakal nyedhiyani sawetara (bisa uga ora lengkap) kode kanggo nambah pangerten. Kode lengkap bakal ana ing pungkasan artikel.

A wit kasusun saka node. Struktur node:

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

Saben simpul duwe anak loro (bisa uga anak leftChild lan / utawa rightChild bakal ngemot nilai null). Sampeyan mbokmenawa nyadari yen ing kasus iki data nomer yaiku data sing disimpen ing simpul; tombol - tombol simpul.

Kita wis ngrampungake simpul kasebut, saiki ayo ngomong babagan masalah penting babagan wit. Sabanjure, kanthi tembung "wit" aku bakal tegese konsep wit telusuran binar. Struktur wit binar:

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

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

Kita mung perlu ROOT wit minangka lapangan kelas, amarga saka ROOT, nggunakake getLeftChild () lan getRightChild () cara, sampeyan bisa njaluk menyang sembarang simpul ing wit.

Algoritma ing wit

Поиск

Ayo ngomong sampeyan duwe wit sing dibangun. Kepiye carane nemokake unsur kanthi tombol kunci? Sampeyan kudu pindhah saka oyod mudhun wit lan mbandhingake nilai kunci karo kunci simpul sabanjure: yen kunci kurang saka tombol simpul sabanjure, banjur pindhah menyang turunan kiwa simpul, yen ana. luwih gedhe, ing sisih tengen, yen tombol padha, simpul sing dikarepake ditemokake! Kode sing cocog:

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

Yen saiki dadi null, banjur telusuran wis tekan mburi wit (ing tingkat konseptual, sampeyan ana ing panggonan sing ora ana ing wit - anak saka rwaning).

Ayo dipikirake efektifitas algoritma telusuran ing wit sing seimbang (wit sing node disebarake luwih utawa kurang merata). Banjur efisiensi telusuran bakal dadi O(log(n)), lan logaritma dadi basis 2. Deleng: yen ana n unsur ing wit sing seimbang, mula iki tegese bakal ana log (n) menyang basis 2 tingkat saka wit. Lan ing panelusuran, ing siji langkah saka siklus, sampeyan mudhun siji tingkat.

masang

Yen sampeyan nangkep inti telusuran, mula ngerti sisipan ora bakal angel kanggo sampeyan. Sampeyan mung kudu mudhun menyang godhong wit (miturut aturan keturunan sing diterangake ing telusuran) lan dadi turunane - ngiwa utawa nengen, gumantung saka tombol kasebut. Implementasine:

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

Ing kasus iki, saliyane simpul saiki, perlu kanggo nyimpen informasi babagan wong tuwa saka simpul saiki. Nalika saiki dadi padha karo null, variabel induk bakal ngemot sheet sing kita butuhake.
Efisiensi penyisipan bakal temenan padha karo panelusuran - O(log(n)).

Pambusakan

Ngilangi minangka operasi sing paling angel sing kudu ditindakake ing wit. Cetha yen pisanan kita kudu nemokake unsur sing bakal dibusak. Nanging apa banjur? Yen kita mung nyetel referensi kanggo null, kita bakal kelangan informasi bab subtree kang simpul iki ROOT. Cara ngilangi wit dipΓ©rang dadi telung kasus.

Kasus pisanan. Node sing dibusak ora duwe anak

Yen simpul sing dibusak ora duwe anak, mula iki tegese godhong. Mulane, sampeyan mung bisa nyetel kolom leftChild utawa rightChild saka wong tuwane dadi null.

Kasus kapindho. Simpul sing bakal dibusak duwe anak siji

Kasus iki uga ora rumit banget. Ayo bali menyang conto kita. Ayo kita ngomong yen kita kudu mbusak unsur karo tombol 14. Setuju yen amarga iku turunan tengen saka simpul karo tombol 10, banjur samubarang turunane (ing kasus iki tengen) bakal duwe tombol luwih saka 10, supaya sampeyan bisa gampang "Cut" metu saka wit, lan nyambung tuwane langsung menyang anak saka simpul dibusak, i.e. nyambungake simpul karo tombol 10 kanggo simpul 13. Kahanan bakal padha yen perlu kanggo mbusak simpul sing anak kiwa tuwane. Coba pikirake dhewe - analogi sing tepat.

Kasus katelu. A simpul duwe anak loro

Kasus paling angel. Ayo goleki conto anyar.

Binary Tree utawa carane nyiyapake wit telusuran binar

Nggoleki penerus

Ayo dadi ngomong kita kudu mbusak simpul karo tombol 25. Sapa sing kudu dilebokake ing panggonane? Salah sawijining pandherekipun (turun utawa turunan) kudu dadi penerus(sing bakal njupuk panggonan simpul sing dibusak).

Kepiye ngerti sapa sing kudu dadi penerus? Secara intuisi, iki minangka simpul ing wit sing kunci paling gedhe sabanjure saka simpul sing dibusak. Algoritma kasebut kaya ing ngisor iki. Sampeyan kudu pindhah menyang turunane tengen (tansah ing sisih tengen, amarga wis ngandika yen kunci penerus luwih gedhe tinimbang tombol simpul sing dibusak), lan banjur pindhah liwat rantai keturunan kiwa saka turunan tengen iki. . Ing conto, kita bakal pindhah menyang simpul kanthi tombol 35, banjur mudhun menyang rwaning liwat rantai anak kiwa - ing kasus iki, rantΓ© iki mung dumadi saka simpul kanthi tombol 30. Tegese, kita nggoleki kanggo simpul paling cilik ing set simpul luwih gedhe tinimbang sing kita goleki simpul.

Binary Tree utawa carane nyiyapake wit telusuran binar

Kode metode telusuran penerus:

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

Kode lengkap kanggo cara mbusak:

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

Kompleksitas bisa dikira-kira O(log(n)).

Nemokake maksimum / minimal ing wit

Cetha carane nemokake nilai minimal / maksimal ing wit - sampeyan kudu mindhah kanthi urutan ing sadawane rantΓ© unsur kiwa / tengen wit kasebut; nalika sampeyan njaluk menyang sheet, bakal minimal / unsur maksimum.

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

Kompleksitas - O(log(n))

Bypass simetris

Traversal ngunjungi saben simpul wit kanggo nindakake sawetara tumindak.

Algoritma traversal simetris rekursif:

  1. Tumindak ing bocah kiwa
  2. Nindakake tumindak dhewe
  3. Tumindak ing bocah sing bener

Kode:

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

kesimpulan

Akhire! Yen aku durung nerangake apa-apa utawa duwe komentar, mangga tinggalake ing komentar. Kaya sing dijanjekake, aku menehi kode lengkap.

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

Degenerasi dadi O(n)

Akeh sing ngerti: kepiye yen sampeyan nggawe wit ora seimbang? Contone, sijine simpul kanthi nambah tombol ing wit: 1,2,3,4,5,6... Banjur wit bakal kaya daftar sing disambung. Lan ya, wit bakal kelangan struktur wit, lan mulane efisiensi akses data. Kompleksitas operasi telusuran, sisipan, lan pambusakan bakal padha karo dhaptar sing disambung: O(n). Iki minangka salah sawijining sing paling penting, miturut pendapatku, kekurangan wit binar.

Mung pangguna pangguna sing bisa melu survey. mlebunggih.

Aku wis ora ana ing hub kanggo banget dawa, lan aku kaya kanggo ngerti apa artikel ing topik apa sampeyan pengin ndeleng liyane?

  • Struktur data

  • Algoritma (DP, rekursi, kompresi data, lsp)

  • Aplikasi struktur data lan algoritma ing urip nyata

  • Pemrograman Aplikasi Android ing Jawa

  • Pemrograman aplikasi web ing Jawa

2 pangguna milih. 1 pangguna abstain.

Sumber: www.habr.com

Add a comment