Pohon, pohon merah-hitam

"Hai, Amigo!"

"Halo, Rishi!"

"Aku menemukan catatan lamaku di sana dan menyiapkan beberapa materi menarik untukmu. Kurasa kamu akan tertarik mendengarnya."

"Mari kita dengarkan. Kamu selalu menemukan sesuatu yang menarik yang nantinya terbukti sangat berguna."

"Oke. Hari ini saya ingin bercerita tentang pohon , jadi saya akan mulai dengan grafik ."

" Grafik adalah sistem titik dan garis yang menghubungkannya. Titik disebut simpul grafik, dan garis disebut tepi grafik. Misalnya:"

"Grafik sangat mudah digunakan sebagai model matematika untuk berbagai proses dan tugas dunia nyata. Banyak tugas dan algoritme yang berbeda telah ditemukan untuk grafik, sehingga cukup sering digunakan."

"Misalnya, misalkan simpul adalah kota, dan ujungnya adalah jalan. Kemudian mencari jalan terpendek antar kota menjadi: «diberi grafik, temukan jalur terpendek antara dua simpul». "

“Tapi jalur dari A ke B tidak selalu sama dengan jalur dari B ke A. Jadi, terkadang memiliki dua garis berbeda lebih disukai. Untuk melakukan ini, garis (tepi grafik) diganti dengan panah. Di dengan kata lain, grafik dapat memiliki dua anak panah: satu dari A ke B, dan satu lagi dari B ke A."

"Jika grafik menggunakan panah, maka itu disebut grafik berarah ; jika hanya memiliki garis, maka itu disebut grafik tidak berarah ."

"Setiap simpul dapat memiliki jumlah sisinya sendiri. Sebuah simpul juga dapat tidak memiliki sisi sama sekali. Sebaliknya, sebuah simpul dapat dihubungkan oleh sisi ke setiap simpul lainnya.  Jika setiap pasangan simpul dalam grafik dihubungkan oleh sebuah sisi, maka itu disebut grafik lengkap. "

"Jika Anda dapat menggunakan sisi untuk mencapai setiap simpul dalam graf, maka itu disebut graf terhubung . Sebuah graf yang memiliki tiga simpul terpisah dan tidak ada sisi masih merupakan graf, tetapi kami menyebutnya graf tidak terhubung ."

"Untuk membentuk graf terhubung dari N simpul, Anda membutuhkan setidaknya N-1 sisi. Graf jenis ini disebut pohon."

“Selain itu, biasanya satu simpul dipilih menjadi akar pohon , dan sisanya dinyatakan sebagai cabang. Cabang pohon yang tidak memiliki cabang sendiri disebut daun . Contoh:”

"Jika setiap elemen pohon memiliki dua anak, maka itu disebut pohon biner . Dengan kata lain, bisa ada 0 atau 2 cabang. Anda bisa melihat pohon biner di kanan atas."

" Sebuah pohon disebut pohon biner lengkap jika setiap cabang memiliki 2 anak, dan semua daun (simpul tanpa anak) berada pada baris yang sama."

"Misalnya:"

"Mengapa pohon-pohon ini dibutuhkan?"

"Oh, pohon digunakan di banyak tempat. Secara umum, pohon biner adalah data terstruktur yang diurutkan."

"Apa itu?"

"Ya, sangat sederhana. Kami menyimpan nilai tertentu di setiap simpul. Dan setiap elemen mengikuti aturan: nilai yang disimpan di anak kanan harus lebih besar dari nilai yang disimpan di simpul, dan nilai yang disimpan di anak kiri harus kurang dari nilai yang disimpan di simpul.  Pengurutan ini memungkinkan untuk menemukan elemen pohon yang Anda perlukan dengan cepat."

"Bisakah Anda mengklarifikasi apa artinya itu?"

"Elemen pohon biasanya diurutkan dengan menambahkan. Misalkan kita memiliki 7 elemen: 13, 5, 4, 16, 8, 11, 10"

"Beginilah cara elemen ditambahkan ke pohon."

"Jika kita mencari angka 7 di pohon ini, maka pencarian akan seperti ini"

"0) Mulai dari akarnya."

"1a) Apakah 7 sama dengan 13? Tidak"

"1b) Apakah 7 lebih besar dari 13? Tidak, jadi kita pindah ke subpohon kiri."

"2a) Apakah 7 sama dengan 5? Tidak."

"2b) Apakah 7 lebih besar dari 5? Ya, jadi kita pindah ke cabang kanan."

"3a) Apakah 7 sama dengan 8? Tidak"

"3b) Apakah 7 lebih besar dari 8? Tidak, jadi kita pindah ke subpohon kiri."

"4a) Tidak ada subpohon kiri, artinya angka 7 tidak ada di pohon."

"Ah. Dengan kata lain, kita hanya perlu memeriksa simpul pada jalur dari akar ke calon lokasi dari angka yang diinginkan. Ya, itu sangat cepat."

"Terlebih lagi, jika pohonnya seimbang, maka kamu hanya perlu melewati sekitar 20 simpul untuk mencari sejuta elemen."

"Saya setuju - itu tidak terlalu banyak."

"Apa maksudmu dengan pohon seimbang?"

“Pohon yang tidak terdistorsi, yaitu tidak memiliki cabang yang panjang. Misalnya, jika elemen sudah disortir saat kita membangun pohon, maka kita akan membuat pohon yang sangat panjang yang terdiri dari satu cabang. ”

"Hmm. Kamu benar. Jadi apa yang harus kita lakukan?"

"Seperti yang mungkin sudah Anda duga, pohon yang paling efisien memiliki cabang yang kira-kira memiliki panjang yang sama. Kemudian setiap perbandingan membuang bagian terbesar dari subpohon yang tersisa."

"Jadi, kita perlu membangun kembali pohon itu?"

"Ya. Itu perlu «seimbang» — dibuat sedekat mungkin dengan pohon biner lengkap."

"Untuk mengatasi masalah ini, pohon self-balancing telah ditemukan.  Jika pohon menjadi terdistorsi setelah menambahkan sebuah elemen, maka elemen tersebut akan diurutkan ulang sedikit untuk membuat semuanya baik-baik saja.  Berikut adalah contoh dari keseimbangan:"

"Beberapa pohon ini dikenal sebagai pohon merah -hitam ."

"Mengapa mereka disebut merah-hitam?"

"Penemu mereka menggambar semua simpul menggunakan dua warna. Satu warna merah, dan yang lainnya hitam. Simpul yang berbeda mematuhi aturan yang berbeda. Ini membentuk seluruh dasar untuk prosedur penyeimbangan."

"Misalnya:"

"Jadi apa aturan ini?"

"1) Sebuah simpul merah tidak bisa menjadi anak dari sebuah simpul merah."

"2) Kedalaman hitam setiap daun adalah sama (kedalaman hitam mengacu pada jumlah simpul hitam pada jalur dari akar)."

"3) Akar pohon itu berwarna hitam."

"Aku tidak akan menjelaskan cara kerjanya—kepalamu mungkin sudah meledak."

"Ya. Prosesor saya mengeluarkan sedikit asap."

"Ini tautan untuk Anda. Jika mau, Anda dapat membaca lebih lanjut di sini."

Tautan ke materi tambahan

"Dan sekarang, istirahatlah."