Pohon Pencarian Biner (BST) dengan Contoh

Atribut Pohon Pencarian Biner

BST terdiri dari beberapa node dan memiliki atribut berikut:

• Node pohon direpresentasikan dalam hubungan orangtua-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 ada di subpohon kiri lebih kecil dari kunci dari node induknya
• Demikian pula, kunci simpul subpohon kiri memiliki nilai yang lebih rendah dibandingkan kunci simpul induknya.

1. Ada node utama atau induk level 11. Di bawahnya ada node/cabang kiri dan kanan dengan nilai kuncinya masing-masing
2. Subpohon sebelah kanan mempunyai nilai kunci yang lebih besar dari simpul induk
3. Sub-pohon kiri memiliki nilai lebih dari simpul induk

Mengapa kita memerlukan Pohon Pencarian Biner?

• Dua faktor utama yang menjadikan pohon pencarian biner sebagai solusi optimal untuk setiap masalah 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 akan dicari lebih besar atau lebih kecil dari node induk, node tersebut mengetahui sisi pohon mana yang harus dicari. Pasalnya, subpohon kiri selalu lebih kecil dari simpul induk, dan subpohon kanan mempunyai nilai yang selalu sama atau lebih besar dari simpul 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 di pohon penuh dengan kemungkinan pengecualian level terakhir. Demikian pula, semua node penuh, mengarah ke paling kiri.
• Pohon biner penuh: Semua node memiliki 2 node anak kecuali daun.
• Pohon biner Seimbang atau Sempurna: Di pohon, semua node memiliki dua anak. Selain itu, terdapat level yang sama pada setiap subnode.

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 membuang subpohon kiri atau kanan dari simpul akar.

BST terutama menawarkan tiga jenis operasi berikut untuk penggunaan Anda:

• Pencarian: mencari elemen dari pohon biner
• Sisipkan: menambahkan elemen ke pohon biner
• Hapus: menghapus elemen dari pohon biner

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

Pencarian Operaproduksi

Selalu memulai analisis pohon pada simpul akar dan kemudian bergerak lebih jauh ke subpohon kanan atau kiri dari simpul akar tergantung pada elemen yang akan ditempatkan lebih kecil atau lebih besar dari akar.

1. Elemen yang akan dicari adalah 10
2. Bandingkan elemen tersebut dengan simpul akar 12, 10 < 12, maka Anda berpindah ke subpohon kiri. Tidak perlu menganalisis subpohon kanan
3. Sekarang bandingkan 10 dengan node 7, 10 > 7, jadi pindah ke subpohon kanan
4. Lalu bandingkan 10 dengan node berikutnya yaitu 9, 10 > 9, lihat di subtree kanan
5. 10 cocok dengan nilai di node, 10 = 10, mengembalikan nilai ke pengguna.

Kode Semu untuk Pencarian di 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 mudah. Pertama, node root dimasukkan, kemudian nilai berikutnya dibandingkan dengan node root. Jika nilainya lebih besar dari akar, maka ditambahkan ke subpohon kanan, dan jika lebih kecil dari akar, maka ditambahkan ke subpohon kiri.

1. Ada daftar 6 elemen yang perlu dimasukkan ke dalam BST secara berurutan dari kiri ke kanan
2. Masukkan 12 sebagai simpul akar dan bandingkan nilai berikutnya 7 dan 9 untuk dimasukkan ke dalam subpohon kanan dan kiri
3. Bandingkan sisa nilai 19, 5, dan 10 dengan simpul akar 12 dan tempatkan sesuai dengan itu. 19 > 12 letakkan sebagai anak kanan dari 12, 5 < 12 & 5 < 7, maka letakkan sebagai anak kiri dari 7. Sekarang bandingkan 10, 10 adalah < 12 & 10 adalah > 7 & 10 adalah > 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 node dari suatu BST, terdapat beberapa kasus yaitu menghapus node root atau menghapus node daun. Selain itu, setelah menghapus root, kita perlu memikirkan node root.

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 termudah, Anda hanya perlu menghapus node yang tidak memiliki anak lagi di kanan atau kiri.
• Kasus 2 – Node dengan satu anak: setelah Anda menghapus node, cukup hubungkan node anak tersebut dengan node induk dari nilai yang dihapus.
• Kasus 3 Node dengan dua anak: ini adalah situasi yang paling sulit, dan ini bekerja pada dua aturan berikut
• 3a – Dalam Urutan Pendahulu: Anda perlu menghapus node dengan dua anak dan menggantinya dengan nilai terbesar di subpohon kiri dari node yang dihapus
• 3b – Di Penerus Pesanan: Anda perlu menghapus node dengan dua anak dan menggantinya dengan nilai terbesar di subpohon kanan dari node yang dihapus

1. Ini adalah kasus penghapusan pertama di mana Anda menghapus sebuah node yang tidak memiliki anak. Seperti terlihat pada diagram bahwa 19, 10 dan 5 tidak mempunyai anak. Tapi kami 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 bahwa 9 memiliki satu anak.
2. Hapus node 9 dan ganti dengan anaknya 10 dan tambahkan link 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 urutan pendahulunya, yang berarti elemen terbesar pada subpohon kiri dari 12 akan menggantikannya.
3. Hapus node 12 dan ganti dengan 10 karena ini adalah nilai terbesar di subpohon kiri
4. Melihat struktur baru BST setelah dihapus 12

1. 1 Hapus node 12 yang memiliki dua anak
2. 2 Penghapusan node akan terjadi berdasarkan aturan In Order Successor, yang berarti elemen terbesar di subpohon kanan 12 akan menggantikannya
3. 3 Hapus node 12 dan gantikan dengan 19 karena ini adalah nilai terbesar pada subpohon kanan
4. 4 Melihat struktur BST yang baru setelah dihapus 12

Kode Pseudo 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 to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Istilah Penting

• Sisipkan: Menyisipkan elemen ke dalam pohon/membuat pohon.
• Pencarian: Mencari elemen di pohon.
• Preorder Traversal: Melintasi pohon dengan cara pre-order.
• Inorder Traversal: Melintasi pohon secara berurutan.
• Postorder Traversal: Melintasi pohon dengan cara post-order.

Kesimpulan

• BST merupakan algoritma tingkat lanjutan yang melakukan berbagai operasi berdasarkan perbandingan nilai node dengan node root.
• Setiap titik dalam hierarki induk-anak mewakili simpul. Setidaknya satu simpul induk atau akar tetap ada sepanjang waktu.
• Ada subpohon kiri dan subpohon kanan. Subpohon kiri berisi nilai yang lebih kecil dari simpul akar. Namun, subpohon kanan berisi nilai yang lebih besar dari simpul akar.
• Setiap node dapat memiliki nol, satu, atau dua anak.
• Pohon pencarian biner memfasilitasi operasi utama seperti pencarian, penyisipan, dan penghapusan.
• Hapus menjadi yang paling kompleks karena memiliki banyak kasus, misalnya, simpul tanpa anak, simpul dengan satu anak, dan simpul dengan dua anak.
• Algoritme ini digunakan dalam solusi dunia nyata seperti game, pelengkapan otomatis data, dan grafik.