[Powered by Google Translate] Bagaimana Anda mewakili semua anggota keluarga Anda di komputer? Kami hanya bisa menggunakan daftar, tapi ada hirarki yang jelas di sini. 

Katakanlah kita mulai dengan besar-nenek Anda, Alice. Dia memiliki 2 anak laki-laki, Bob dan Anda kakek, Charlie. Charlie memiliki 3 anak, Anda paman, Dave, bibimu, Eve, dan ayahmu, Fred. Anda adalah anak tunggal Fred. 

Mengapa mengorganisir anggota keluarga Anda dengan cara ini lebih baik daripada representasi daftar sederhana? Salah satu alasannya adalah bahwa struktur hirarkis, disebut 'pohon,' berisi informasi lebih dari daftar sederhana. Kita tahu hubungan keluarga antara orang hanya dengan memeriksa pohon. Selain itu, dapat mempercepat look-up waktu yang sangat, jika data pohon diurutkan. 

Kita tidak bisa mengambil keuntungan dari itu di sini, tapi kami akan melihat contoh ini segera. Setiap orang diwakili oleh simpul di pohon. Node dapat memiliki node anak serta simpul orangtua. Ini adalah istilah-istilah teknis, bahkan ketika menggunakan pohon untuk hal-hal selain keluarga. Simpul Alice memiliki 2 anak-anak dan tidak ada orang tua, sedangkan simpul Charlie memiliki 3 anak dan 1 orangtua. 

Sebuah simpul daun adalah salah satu yang tidak memiliki anak di tepi luar dari pohon. Simpul paling atas pohon, simpul akar, memiliki orangtua tidak. 

Sebuah pohon biner adalah jenis tertentu pohon, di mana setiap node memiliki, paling banyak, 2 anak-anak. Berikut adalah struct dari simpul dari pohon biner di C. Setiap node memiliki beberapa data yang terkait dengan itu dan 2 pointer ke node lain. 

Dalam pohon keluarga kami, data yang terkait adalah nama setiap orang. Berikut ini adalah int, meskipun itu bisa berupa apa saja. Ternyata, pohon biner tidak akan menjadi representasi yang baik untuk keluarga, karena orang sering memiliki lebih dari 2 anak. 

Sebuah pohon pencarian biner adalah jenis, khusus memerintahkan pohon biner yang memungkinkan kita untuk melihat nilai cepat. Anda mungkin telah memperhatikan bahwa setiap node di bawah akar pohon adalah akar dari pohon lain, disebut 'subtree.' Di sini, akar pohon adalah 6, dan anaknya, 2, adalah akar dari subtree. 

Dalam sebuah pohon pencarian biner semua nilai dari node benar subtree lebih besar dari nilai node. Berikut: 6. Nah, nilai-nilai dalam subtree kiri node kurang dari nilai node. Jika kita perlu untuk menangani nilai ganda, kita dapat mengubah salah satu dari mereka ke ketimpangan yang longgar, yang berarti nilai yang identik dapat jatuh baik di kiri atau kanan, asalkan kita konsisten tentang hal itu seluruh. Pohon ini adalah pohon pencarian biner karena mengikuti aturan-aturan ini. 

Ini adalah bagaimana hal itu akan terlihat jika kita berpaling semua node dalam structs C. Perhatikan bahwa jika seorang anak hilang, pointer adalah null. Bagaimana kita periksa untuk melihat apakah 7 adalah di pohon? Kami mulai dari akar. Tujuh lebih besar dari 6, jadi jika itu di pohon, itu harus ke kanan. Kemudian, itu adalah kurang dari 8, sehingga harus ditinggalkan. Di sini, kami telah menemukan 7. Sekarang, kita akan memeriksa 5. Lima kurang dari 6, sehingga harus ke kiri. Lima lebih besar dari 2, sehingga harus benar, dan juga lebih besar dari 4, sehingga harus benar lagi. Namun, ada tidak ada anak di sini. Pointer adalah null. Ini berarti bahwa 5 tidak di pohon kami. 

Kita bisa mencari pohon biner dengan kode berikut: Pada setiap node, kita periksa untuk melihat apakah kita telah menemukan nilai yang kita cari. Jika kita tidak menemukannya, kita menentukan apakah harus di kiri atau kanan dan periksa subtree. Loop ini akan terus turun pohon sampai tidak ada simpul anak pada salah satu bagian kiri atau kanan. 

Ingat bahwa 5 tidak di pohon. Bagaimana kita masukkan? Proses ini terlihat mirip dengan mencari. Kami iterate bawah pohon mulai dari 6, kiri ke 2, hak untuk 4, dan kanan lagi, tapi 4 memiliki anak tidak di sisi ini. Ini akan menjadi posisi baru untuk 5, dan akan mulai tanpa anak. 

Seberapa cepat operasi pada pohon pencarian biner? Ingat bahwa Bigohnotation berusaha untuk memberikan batas atas. Dalam kasus terburuk, pohon kami hanya bisa menjadi linked list yang berarti bahwa penyisipan, penghapusan, dan pencarian bisa memakan waktu sebanding dengan jumlah node dalam pohon. Ini adalah O (n). 

Sebagai contoh, berikut ini adalah sebuah pohon biner yang valid pencarian. Namun, jika kita mencoba untuk menemukan 9, kita harus melintasi setiap node. Hal ini tidak lebih baik dari sebuah linked list. Idealnya, kita ingin setiap node dari pohon pencarian biner kami memiliki 2 anak. Dengan cara ini, penyisipan, penghapusan dan pencarian akan mengambil, paling buruk, O (log n) waktu. Pohon dari sebelumnya bisa lebih seimbang, seperti ini. Sekarang, mencari nilai apapun membutuhkan, paling, 3 langkah. Pohon ini seimbang, makna yang memiliki kedalaman minimal relatif terhadap jumlah node. 

Mencari nilai dalam sebuah pohon pencarian biner seimbang mirip dengan pencarian biner pada array diurutkan. Padahal, jika kita tidak perlu memasukkan atau menghapus item, mereka berperilaku dengan cara yang persis sama. Namun, struktur pohon lebih baik untuk penanganan sisipan dan penghapusan 

Nama saya Bannus Van der Kloot. Ini adalah CS50.