[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.