Pohon Pencarian Biner (BST) dengan Contoh

Apa itu Pohon Pencarian Biner?

Binary Search Tree (BST) adalah algoritma canggih yang digunakan untuk menganalisis simpul, cabang kiri dan kanannya, yang dimodelkan dalam struktur pohon, dan mengembalikan nilainya. BST dirancang berdasarkan arsitektur algoritma pencarian biner dasar; oleh karena itu, BST memungkinkan pencarian, penyisipan, dan penghapusan simpul yang lebih cepat. Hal ini membuat program menjadi sangat cepat dan akurat.

Atribut Pohon Pencarian Biner

BST terdiri dari beberapa node dan memiliki atribut berikut:

• Node-node pada pohon direpresentasikan dalam hubungan induk-anak.
• Setiap node induk dapat memiliki nol node anak atau maksimal dua subnode atau subpohon di sisi kiri dan kanan.
• Setiap sub-pohon, juga dikenal sebagai pohon pencarian biner, memiliki sub-cabang di kanan dan kirinya.
• Semua node dihubungkan dengan pasangan nilai kunci.
• Kunci dari node yang terdapat pada subpohon sebelah kiri lebih kecil daripada kunci dari node induknya.
• Demikian pula, kunci dari node yang ada di subpohon sebelah kanan lebih besar daripada kunci dari node induknya.

1. Terdapat node utama atau induk level 11. Di bawahnya, terdapat node/cabang kiri dan kanan dengan nilai kunci masing-masing.
2. Sub-pohon sebelah kanan memiliki nilai kunci yang lebih besar daripada simpul induknya.
3. Sub-pohon sebelah kiri memiliki nilai kunci yang lebih kecil daripada simpul induknya.

Mengapa kita memerlukan Pohon Pencarian Biner?

• Dua faktor utama yang menjadikan pohon pencarian biner sebagai solusi optimal untuk setiap masalah di dunia nyata adalah Kecepatan dan Akurasi.
• Karena fakta bahwa pencarian biner berada dalam format seperti cabang dengan hubungan induk-anak, algoritme mengetahui di lokasi pohon mana elemen perlu dicari. Hal ini mengurangi jumlah perbandingan nilai kunci yang harus dilakukan program untuk menemukan elemen yang diinginkan.
• Selain itu, jika elemen yang dicari lebih besar atau lebih kecil dari node induk, node tersebut mengetahui sisi pohon mana yang harus dicari. Alasannya adalah sub-pohon kiri selalu lebih kecil dari node induk, dan sub-pohon kanan memiliki nilai yang selalu sama dengan atau lebih besar dari node induk.
• BST umumnya dimanfaatkan untuk mengimplementasikan penelusuran kompleks, logika permainan yang kuat, aktivitas pelengkapan otomatis, dan grafik.
• Algoritma ini secara efisien mendukung operasi seperti pencarian, penyisipan, dan penghapusan.

Jenis Pohon Biner

Tiga jenis pohon biner adalah:

• Pohon biner lengkap: Semua level dalam pohon sudah penuh, kecuali mungkin pada level terakhir. Demikian pula, semua node sudah penuh, mengarah ke paling kiri.
• Pohon biner lengkap: Semua node memiliki 2 node anak kecuali node daun.
• Pohon biner seimbang atau sempurna: Dalam pohon tersebut, semua node memiliki dua anak. Selain itu, setiap subnode memiliki level yang sama.

Pelajari lebih lanjut tentang Pohon Biner dalam Struktur Data jika Anda tertarik.

Bagaimana Cara Kerja Pohon Pencarian Biner?

Pohon selalu memiliki simpul akar dan simpul anak selanjutnya, baik di kiri maupun kanan. Algoritme melakukan semua operasi dengan membandingkan nilai dengan akar dan node anak selanjutnya di subpohon kiri atau kanan.

Tergantung pada elemen yang akan disisipkan, dicari, atau dihapus, setelah perbandingan, algoritma dapat dengan mudah menghapus subpohon kiri atau kanan dari simpul akar.

BST terutama menawarkan tiga jenis operasi berikut untuk penggunaan Anda:

• Pencarian: mencari elemen dari pohon biner.
• Memasukkan: menambahkan elemen ke pohon biner.
• Menghapus: Menghapus elemen dari pohon biner.

Tiap operasi memiliki struktur dan metode eksekusi/analisisnya sendiri, tetapi yang paling rumit adalah operasi Hapus.

Cari Operaproduksi

Selalu mulai menganalisis pohon dari simpul akar, lalu lanjutkan ke subpohon kanan atau kiri dari simpul akar, tergantung apakah elemen yang akan dicari lebih kecil atau lebih besar dari akar.

1. Elemen yang akan dicari adalah 10.
2. Bandingkan elemen tersebut dengan node akar 12, 10 < 12, oleh karena itu Anda pindah ke subpohon kiri. Tidak perlu menganalisis subpohon kanan.
3. Sekarang bandingkan 10 dengan node 7, 10 > 7, jadi pindah ke subpohon kanan.
4. Kemudian bandingkan 10 dengan node berikutnya, yaitu 9, 10 > 9, lihat pada anak subpohon sebelah kanan.
5. 10 cocok dengan nilai di node, 10 = 10, mengembalikan nilai ke pengguna.

Pseudo Code untuk Pencarian dalam BST

search(element, root)
    if !root
        return -1
    if root.value == element
        return 1
    if root.value < element
        search(element, root.right)
    else
        search(element, root.left)

Menyisipkan Operaproduksi

Ini adalah operasi yang sangat sederhana. Pertama, simpul akar dimasukkan, kemudian nilai berikutnya dibandingkan dengan simpul akar. Jika nilainya lebih besar dari akar, maka ditambahkan ke subpohon kanan, dan jika lebih kecil dari akar, maka ditambahkan ke subpohon kiri.

1. Terdapat daftar berisi 6 elemen yang perlu dimasukkan ke dalam BST secara berurutan dari kiri ke kanan.
2. Masukkan angka 12 sebagai simpul akar dan bandingkan nilai berikutnya, yaitu 7 dan 9, untuk dimasukkan sesuai ke dalam subpohon kanan dan kiri.
3. Bandingkan nilai-nilai yang tersisa, yaitu 19, 5, dan 10, dengan simpul akar 12 dan tempatkan sesuai dengan posisinya. 19 > 12, tempatkan sebagai anak kanan dari 12; 5 < 12 dan 5 < 7, oleh karena itu tempatkan sebagai anak kiri dari 7. Sekarang bandingkan 10, 10 < 12 dan 10 > 7 dan 10 > 9, tempatkan 10 sebagai subpohon kanan dari 9.

Pseudocode untuk Memasukkan Node di BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
        y = x
        if x.value < element.value
            x = x.right
        else
            x = x.left
    if y.value < element
        y.right = element
    else
        y.left = element

Delete Operations

Untuk menghapus sebuah node dari BST, ada beberapa kasus, misalnya menghapus node akar atau menghapus node daun. Selain itu, setelah menghapus node akar, kita perlu memikirkan node akar tersebut.

Misalnya kita ingin menghapus simpul daun, kita dapat langsung menghapusnya, tetapi jika kita ingin menghapus simpul akar, kita perlu mengganti nilai akar dengan simpul lain. Mari kita ambil contoh berikut:

• Kasus 1 – Node dengan nol anak: Ini adalah situasi paling mudah, Anda hanya perlu menghapus node yang tidak memiliki anak lagi di sebelah kanan atau kiri.
• Kasus 2 – Node dengan satu anak: Setelah Anda menghapus node, cukup hubungkan node anak dari node anak tersebut dengan node induk dari nilai yang dihapus.
• Kasus 3 – Node dengan dua anak: Ini adalah situasi yang paling sulit, dan cara kerjanya berdasarkan dua aturan berikut:
  • 3a – Pendahulu Berurutan: Anda perlu menghapus node dengan dua anak dan menggantinya dengan nilai terbesar pada subpohon kiri dari node yang dihapus.
  • 3b – Penerus Berurutan: Anda perlu menghapus node dengan dua anak dan menggantinya dengan nilai terkecil pada subpohon kanan dari node yang dihapus.

1. Ini adalah kasus penghapusan pertama, di mana Anda menghapus sebuah node yang tidak memiliki anak. Seperti yang Anda lihat pada diagram, 19, 10, dan 5 tidak memiliki anak. Tetapi kita akan menghapus 19.
2. Hapus nilai 19 dan hapus tautan dari node.
3. Lihat struktur baru BST tanpa 19.

1. Ini adalah kasus penghapusan kedua, di mana Anda menghapus sebuah node yang memiliki 1 anak. Seperti yang Anda lihat pada diagram, node 9 memiliki satu anak.
2. Hapus node 9 dan ganti dengan anak node 10, lalu tambahkan tautan dari 7 ke 10.
3. Lihat struktur baru BST tanpa 9.

1. Di sini Anda akan menghapus node 12 yang memiliki dua anak.
2. Penghapusan node akan terjadi berdasarkan aturan pendahulu berurutan (in-order predecessor), yang berarti elemen terbesar pada subpohon kiri dari 12 akan menggantikannya.
3. Hapus node 12 dan ganti dengan 10, karena itu adalah nilai terbesar pada subpohon sebelah kiri.
4. Lihat struktur baru BST setelah menghapus 12.

1. Hapus node 12 yang memiliki dua anak.
2. Penghapusan node akan terjadi berdasarkan aturan In-Order Successor, yang berarti elemen terkecil pada subpohon kanan dari 12 akan menggantikannya.
3. Hapus node 12 dan ganti dengan 19, karena itu adalah nilai terkecil pada subpohon sebelah kanan.
4. Lihat struktur baru BST setelah menghapus 12.

Pseudo Code untuk Menghapus Node

delete (value, root):
    Node x = root
    Node y = NULL
    # searching the node
    while x:
        y = x
        if x.value < value
            x = x.right
        else if x.value > value
            x = x.left
        else if value == x
            break
    # if the node is not null, then replace it with successor
    if y.left or y.right:
        newNode = GetInOrderSuccessor(y)
        root.value = newNode.value
        # after copying the value of successor, delete the successor
        free(newNode)
    else
        free(y)

Istilah Penting

• Memasukkan: Menyisipkan elemen ke dalam pohon / membuat pohon.
• Pencarian: Mencari elemen dalam sebuah pohon.
• Penelusuran Pra-pemesanan: Menjelajahi pohon secara berurutan.
• Penelusuran Inorder: Menelusuri pohon secara berurutan.
• Penelusuran Postorder: Menelusuri pohon secara berurutan.

Pertanyaan Umum Demo Slot