Panduan Pemula untuk Pohon Biner

Jika Anda telah mengambil kursus struktur data dalam gelar ilmu komputer Anda, atau seorang programmer otodidak, kemungkinan Anda telah menemukan istilah "Pohon Biner". Meskipun mungkin terdengar sedikit berlebihan dan rumit, konsep pohon biner cukup sederhana.

Baca terus saat kami membedah pohon biner, dan mengapa mereka merupakan konsep inti yang diperlukan untuk programmer.

Apa itu Pohon Biner?

Pohon biner adalah salah satu struktur data pertama yang diajarkan kepada siswa dalam kursus struktur data. Pohon biner dibuat dari banyak simpul, dan setiap simpul pohon biner berisi dua pointer yang menunjukkan simpul data anak kiri dan kanan.

Node pertama dalam pohon biner disebut "root". Node tingkat terakhir di pohon disebut daun.

Setiap node berisi item data dan dua pointer node. Pohon biner kosong diwakili oleh pointer nol. Seperti yang mungkin sudah Anda ketahui, pohon biner hanya dapat memiliki dua anak (karena itu namanya).

Jenis Struktur Pohon Biner

Ada beberapa struktur pohon biner yang berbeda tergantung pada cara node diposisikan. Pohon biner disebut pohon biner penuh ketika setiap simpul di pohon memiliki nol atau dua anak. Dalam pohon biner yang sempurna, semua node memiliki dua anak dan semua daun berada pada kedalaman yang sama.

Terkait: Cara Terbaik untuk Mempelajari Cara Membuat Kode Gratis

Pohon biner lengkap memiliki node yang diisi di setiap level, dengan pengecualian level terakhir. Dalam pohon biner lengkap, simpul terkonsentrasi di sisi kiri akar. Struktur umum lainnya adalah pohon biner seimbang; dalam struktur ini ketinggian subpohon kanan dan kiri harus berbeda paling banyak satu. Subpohon kiri dan kanan juga harus seimbang.

Penting untuk dicatat bahwa tinggi pohon biner seimbang adalah O(logn), di mana n adalah jumlah simpul di pohon.

Dalam beberapa kasus, jika setiap node hanya memiliki satu anak kiri atau kanan, maka pohon biner dapat menjadi pohon biner miring. Kemudian akan berperilaku seperti daftar tertaut, pohon seperti itu juga disebut pohon yang merosot.

Apa itu Pohon Pencarian Biner?

Pohon pencarian biner (BST) pada dasarnya adalah pohon biner terurut dengan properti khusus yang dikenal sebagai properti "pohon pencarian biner". Properti BST berarti simpul dengan nilai kunci lebih kecil dari akar ditempatkan di subpohon kiri, dan simpul dengan nilai kunci lebih besar dari akar adalah bagian dari subpohon kanan.

Properti BST harus benar untuk setiap simpul induk berikutnya di pohon.

Pohon pencarian biner menawarkan penyisipan dan pencarian cepat. Operasi penyisipan, penghapusan, dan pencarian memiliki kompleksitas waktu kasus terburuk O(n), yang mirip dengan daftar tertaut.

Manfaat Pohon Biner

Pohon biner menawarkan banyak manfaat, itulah sebabnya mereka tetap menjadi struktur data yang sangat berguna. Mereka dapat digunakan untuk menunjukkan hubungan struktural dan hierarki dalam kumpulan data. Lebih penting lagi, pohon biner memungkinkan pencarian, penghapusan, dan penyisipan yang efisien.

Ini juga sangat mudah untuk menerapkan dan memelihara pohon biner. Pohon biner menawarkan pemrogram manfaat dari array yang dipesan dan daftar tertaut; pencarian di pohon biner secepat dalam array yang diurutkan dan operasi penyisipan atau penghapusan seefisien dalam daftar tertaut.

Pohon Biner Adalah Struktur Data Penting

Pohon Biner adalah struktur data yang sangat penting dan sangat penting bagi programmer untuk nyaman menerapkannya dalam program mereka. Seringkali, pewawancara menanyakan masalah pohon biner sederhana seperti traversal, kedalaman maksimum, mirroring, dll.

Kami sangat menyarankan untuk memahami konsep pohon biner, dan terbiasa dengan masalah wawancara yang khas.

TreeViz: Cara Sederhana Untuk Memvisualisasikan Struktur Data

Baca Selanjutnya

Tentang Penulis