ProHoster > blog > administrasi > Binary Tree atau cara menyiapkan pohon pencarian biner

Binary Tree atau cara menyiapkan pohon pencarian biner

Foreplay

Artikel ini adalah tentang pohon pencarian biner. Saya baru-baru ini menulis artikel tentang kompresi data dengan metode Huffman. Di sana saya tidak terlalu memperhatikan pohon biner, karena metode pencarian, penyisipan, penghapusan tidak relevan. Sekarang saya memutuskan untuk menulis artikel tentang pohon. Mungkin kita akan mulai.

Pohon adalah struktur data yang terdiri dari node-node yang dihubungkan oleh tepi-tepinya. Kita dapat mengatakan bahwa pohon adalah kasus khusus dari sebuah graf. Berikut adalah contoh pohon:

Binary Tree atau cara menyiapkan pohon pencarian biner

Ini bukan pohon pencarian biner! Semuanya di bawah potongan!

Terminologi

Root

Akar pohon adalah node paling atas. Dalam contoh, ini adalah simpul A. Di dalam pohon, hanya satu jalur yang dapat mengarah dari akar ke simpul lainnya! Bahkan, setiap node dapat dianggap sebagai akar dari subtree yang sesuai dengan node ini.

Orang tua/keturunan

Semua node kecuali root mempunyai tepat satu sisi yang mengarah ke node lainnya. Node di atas node saat ini disebut induk simpul ini. Sebuah node yang terletak di bawah node saat ini dan terhubung dengannya disebut keturunan simpul ini. Mari kita ambil contoh. Ambil node B, maka induknya adalah node A, dan anaknya adalah node D, E, dan F.

Лист

Simpul yang tidak mempunyai anak disebut daun dari pohon. Pada contoh, node D, E, F, G, I, J, K akan menjadi daun.

Ini adalah terminologi dasar. Konsep lain akan dibahas nanti. Jadi, pohon biner adalah pohon yang setiap simpulnya mempunyai tidak lebih dari dua anak. Seperti yang Anda duga, pohon dari contoh tersebut tidak akan biner, karena node B dan H memiliki lebih dari dua anak. Berikut adalah contoh pohon biner:

Binary Tree atau cara menyiapkan pohon pencarian biner

Simpul pohon dapat berisi informasi apa pun. Pohon pencarian biner adalah pohon biner yang memiliki sifat-sifat berikut:

  1. Baik subpohon kiri dan kanan adalah pohon pencarian biner.
  2. Semua node pada subpohon kiri dari node X yang berubah-ubah memiliki nilai kunci data yang lebih kecil dari nilai kunci data dari node X itu sendiri.
  3. Semua node dari subpohon kanan dari node X yang berubah-ubah memiliki nilai kunci data yang lebih besar atau sama dengan nilai kunci data dari node X itu sendiri.

ΠšΠ»ΡŽΡ‡ - beberapa karakteristik dari node (misalnya, angka). Kunci diperlukan agar dapat menemukan elemen pohon yang sesuai dengan kunci tersebut. Contoh pohon pencarian biner:

Binary Tree atau cara menyiapkan pohon pencarian biner

pemandangan pohon

Seiring berjalannya waktu, saya akan menyertakan beberapa potongan kode (mungkin tidak lengkap) untuk meningkatkan pemahaman Anda. Kode lengkapnya ada di akhir artikel.

Pohon itu terdiri dari node. Struktur simpul:

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

Setiap node mempunyai dua anak (sangat mungkin bahwa anak kiri dan/atau anak kanan akan bernilai null). Anda mungkin memahami bahwa dalam hal ini data angka adalah data yang disimpan dalam node; kunci - kunci simpul.

Kita sudah menemukan jawabannya, sekarang mari kita bicara tentang masalah mendesak tentang pepohonan. Selanjutnya yang dimaksud dengan kata β€œpohon” adalah konsep pohon pencarian biner. Struktur pohon biner:

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

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

Sebagai bidang kelas, kita hanya memerlukan akar pohon, karena dari akar, dengan menggunakan metode getLeftChild() dan getRightChild(), Anda dapat mengakses simpul mana pun di pohon.

Algoritma Pohon

pencarian

Katakanlah Anda memiliki pohon yang dibangun. Bagaimana cara menemukan elemen dengan kunci kunci? Anda perlu berpindah secara berurutan dari akar ke bawah pohon dan membandingkan nilai kunci dengan kunci dari simpul berikutnya: jika kunci lebih kecil dari kunci simpul berikutnya, maka lanjutkan ke turunan kiri dari simpul, jika lebih - ke kanan, jika kuncinya sama - simpul yang diinginkan ditemukan! Kode yang relevan:

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

Jika arus menjadi nol, maka iterasi telah mencapai ujung pohon (pada tingkat konseptual, Anda berada di tempat yang tidak ada di pohon - anak dari daun).

Pertimbangkan efisiensi algoritma pencarian pada pohon seimbang (pohon di mana node didistribusikan kurang lebih merata). Maka efisiensi pencariannya adalah O(log(n)), dan logaritma basis 2. Lihat: jika ada n elemen dalam pohon seimbang, berarti akan ada level log(n) basis 2 dari pohon tersebut. Dan dalam pencarian, untuk satu langkah siklus, Anda turun satu tingkat.

menyisipkan

Jika Anda sudah memahami inti pencarian, maka tidak akan sulit bagi Anda untuk memahami penyisipan. Anda hanya perlu turun ke daun pohon (sesuai aturan keturunan yang dijelaskan dalam pencarian) dan menjadi keturunannya - kiri atau kanan, tergantung kuncinya. Penerapan:

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

Dalam hal ini, selain node saat ini, perlu untuk menyimpan informasi tentang induk dari node saat ini. Ketika saat ini menjadi nol, variabel induk akan berisi lembar yang kita butuhkan.
Efisiensi penyisipan jelas akan sama dengan efisiensi pencarian - O(log(n)).

Pemindahan

Penghapusan adalah operasi paling rumit yang perlu dilakukan dengan pohon. Jelas bahwa pertama-tama kita perlu menemukan elemen yang akan kita hapus. Tapi lalu apa? Jika kita menyetel referensinya ke nol, maka kita akan kehilangan informasi tentang subpohon yang akarnya adalah simpul ini. Metode penebangan pohon dibagi menjadi tiga kasus.

Kasus pertama. Node yang akan dihapus tidak memiliki turunan.

Jika node yang akan dihapus tidak mempunyai anak, berarti node tersebut adalah daun. Oleh karena itu, Anda cukup menyetel kolom leftChild atau rightChild dari induknya ke null.

Kasus kedua. Node yang akan dihapus memiliki satu anak

Kasus ini juga tidak terlalu sulit. Mari kita kembali ke contoh kita. Misalkan kita perlu menghapus sebuah elemen dengan kunci 14. Setuju bahwa karena elemen tersebut adalah anak kanan dari node dengan kunci 10, maka setiap turunannya (dalam hal ini, yang kanan) akan memiliki kunci lebih besar dari 10, jadi Anda dapat dengan mudah "memotongnya" dari pohon, dan menghubungkan induknya langsung ke anak dari simpul yang sedang dihapus, mis. hubungkan node dengan kunci 10 ke node 13. Situasinya akan serupa jika kita harus menghapus node yang merupakan anak kiri dari induknya. Pikirkan sendiri - sebuah analogi yang tepat.

Kasus ketiga. Node memiliki dua anak

Kasus yang paling sulit. Mari kita lihat contoh baru.

Binary Tree atau cara menyiapkan pohon pencarian biner

Cari penerus

Katakanlah kita perlu menghapus simpul dengan kunci 25. Siapa yang akan kita tempatkan sebagai gantinya? Salah satu pengikutnya (keturunan atau keturunan dari keturunan) harus menjadi penerus(orang yang akan menggantikan node yang dihapus).

Bagaimana Anda tahu siapa yang seharusnya menjadi penerusnya? Secara intuitif, ini adalah simpul di pohon yang kuncinya terbesar berikutnya dari simpul yang dihapus. Algoritmanya adalah sebagai berikut. Anda harus pergi ke anak kanannya (selalu ke anak kanannya, karena telah dikatakan bahwa kunci penerusnya lebih besar daripada kunci dari node yang dihapus), dan kemudian menelusuri rantai anak kiri dari kanan ini anak. Dalam contoh, kita harus pergi ke node dengan kunci 35, dan kemudian turun ke rantai anak kirinya ke daun - dalam hal ini, rantai ini hanya terdiri dari node dengan kunci 30. Sebenarnya, kita sedang mencari simpul terkecil dalam kumpulan simpul yang lebih besar dari simpul yang diinginkan.

Binary Tree atau cara menyiapkan pohon pencarian biner

Kode metode pencarian 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 dari metode hapus:

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

Kompleksitasnya dapat diperkirakan menjadi O(log(n)).

Menemukan maksimum/minimum dalam sebuah pohon

Jelasnya, cara menemukan nilai minimum / maksimum di pohon - Anda harus menelusuri rantai elemen kiri / kanan pohon secara berurutan; ketika Anda sampai ke daun, itu akan menjadi elemen minimum/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))

Jalan pintas simetris

Traversal adalah kunjungan ke setiap simpul pohon untuk melakukan sesuatu dengannya.

Algoritma traversal simetris rekursif:

  1. Lakukan tindakan pada anak kiri
  2. Buatlah tindakan dengan diri Anda sendiri
  3. Lakukan tindakan pada anak yang tepat

Kode:

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

Kesimpulan

Akhirnya! Jika saya tidak menjelaskan sesuatu atau memiliki komentar, maka saya menunggu di komentar. Seperti yang dijanjikan, berikut kode lengkapnya.

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 menjadi O(n)

Banyak dari Anda mungkin memperhatikan: bagaimana jika Anda membuat pohon menjadi tidak seimbang? Misalnya, letakkan node di pohon dengan kunci yang bertambah: 1,2,3,4,5,6... Maka pohon itu akan menyerupai daftar tertaut. Dan ya, pohon tersebut akan kehilangan struktur pohonnya, dan karenanya efisiensi akses data. Kompleksitas operasi pencarian, penyisipan, dan penghapusan akan menjadi sama dengan kompleksitas daftar tertaut: O(n). Menurut pendapat saya, ini adalah salah satu kelemahan pohon biner yang paling penting.

Hanya pengguna terdaftar yang dapat berpartisipasi dalam survei. Masuk, silakan.

Saya sudah lama tidak berada di HabrΓ©, dan saya ingin tahu artikel apa tentang topik apa yang ingin Anda lihat lebih lanjut?

  • Struktur data

  • Algoritma (DP, rekursi, kompresi data, dll.)

  • Penerapan struktur data dan algoritma dalam kehidupan nyata

  • Pemrograman aplikasi android di Java

  • Pemrograman Aplikasi Web Java

2 pengguna memilih. 1 pengguna abstain.

Sumber: www.habr.com

Tambah komentar