Pokok, pokok merah-hitam

"Hai, Amigo!"

"Hello, Rishi!"

"Saya jumpa nota lama saya di sana dan sediakan beberapa bahan menarik untuk awak. Saya rasa awak akan berminat untuk mendengarnya."

"Mari kita dengar. Anda sentiasa mendapati sesuatu yang menarik yang kemudiannya terbukti sangat berguna."

"OK. Hari ini saya ingin memberitahu anda tentang pokok , jadi saya akan mulakan dengan graf ."

" Graf ialah sistem titik dan garis yang menghubungkannya. Titik itu dipanggil bucu graf, dan garisan dipanggil tepi graf. Contohnya:"

"Graf sangat mudah digunakan sebagai model matematik untuk pelbagai proses dan tugasan dunia sebenar. Banyak tugasan dan algoritma yang berbeza telah dicipta untuk graf, jadi ia digunakan dengan agak kerap."

"Sebagai contoh, katakan bucu ialah bandar, dan tepi ialah jalan. Kemudian mencari jalan terpendek antara bandar menjadi: «diberi graf, cari laluan terpendek antara dua bucu». "

"Tetapi laluan dari A ke B tidak selalu sama dengan laluan dari B ke A. Jadi, kadangkala mempunyai dua garisan yang berbeza lebih diutamakan. Untuk melakukan ini, garisan (tepi graf) digantikan dengan anak panah. Dalam dengan kata lain, graf boleh mempunyai dua anak panah: satu dari A ke B, dan satu lagi dari B ke A."

"Jika graf menggunakan anak panah, maka ia dipanggil graf berarah ; jika ia hanya mempunyai garis, maka ia dipanggil graf tidak berarah ."

"Setiap bucu boleh mempunyai bilangan tepinya sendiri. Bucu juga boleh tidak mempunyai tepi sama sekali. Sebaliknya, bucu boleh disambungkan oleh tepi ke setiap bucu yang lain.  Jika setiap pasangan bucu dalam graf disambungkan oleh tepi, maka ia dipanggil graf lengkap. "

"Jika anda boleh menggunakan tepi untuk mencapai setiap bucu dalam graf, maka ia dipanggil graf bersambung . Graf yang mempunyai tiga bucu yang berasingan dan tiada tepi masih merupakan graf, tetapi kami memanggilnya graf terputus ."

"Untuk membentuk graf bersambung daripada N bucu, anda memerlukan sekurang-kurangnya N-1 tepi. Graf jenis ini dipanggil pokok."

"Selain itu, biasanya satu bucu dipilih untuk menjadi akar pokok , dan selebihnya diisytiharkan sebagai dahan. Cawangan pokok yang tidak mempunyai dahan sendiri dipanggil daun . Contohnya:"

"Jika setiap elemen pokok itu mempunyai dua anak, maka ia dipanggil pokok binari . Dalam erti kata lain, boleh ada sama ada 0 atau 2 cabang. Anda boleh melihat pokok binari di bahagian atas sebelah kanan."

" Sebatang pokok dipanggil pokok binari lengkap apabila setiap dahan mempunyai 2 anak, dan semua daun (bucu tanpa anak) berada pada baris yang sama."

"Sebagai contoh:"

"Kenapa pokok ini diperlukan?"

"Oh, pokok digunakan di banyak tempat. Secara amnya, pokok binari ialah data berstruktur diisih."

"Apa itu?"

"Ya, ia sangat mudah. ​​Kami menyimpan nilai tertentu dalam setiap bucu. Dan setiap elemen mengikut peraturan: nilai yang disimpan dalam anak kanan mestilah lebih besar daripada nilai yang disimpan dalam bucu, dan nilai yang disimpan dalam anak kiri mesti kurang daripada nilai yang disimpan dalam bucu.  Susunan ini membolehkan anda mencari dengan cepat unsur pokok yang anda perlukan."

"Boleh awak jelaskan apa maksudnya?"

"Unsur pokok biasanya diisih dengan menambah. Katakan kita mempunyai 7 elemen: 13, 5, 4, 16, 8, 11, 10"

"Beginilah cara unsur-unsur ditambahkan pada pokok itu."

"Jika kita mencari nombor 7 dalam pokok ini, maka beginilah cara pencariannya"

"0) Mulakan pada akarnya."

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

"1b) Adakah 7 lebih besar daripada 13? Tidak, jadi kita beralih ke subpokok kiri."

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

"2b) Adakah 7 lebih besar daripada 5? Ya, jadi kita beralih ke subpokok kanan."

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

"3b) Adakah 7 lebih besar daripada 8? Tidak, jadi kita beralih ke subpokok kiri."

"4a) Tiada subpokok kiri, yang bermaksud nombor 7 tiada dalam pokok itu."

"Ah. Dalam erti kata lain, kita hanya perlu menyemak bucu pada laluan dari akar ke lokasi yang akan menjadi nombor yang dikehendaki. Ya, itu benar-benar pantas."

"Apatah lagi, jika pokok itu seimbang, maka anda hanya perlu melalui kira-kira 20 bucu untuk mencari sejuta elemen."

"Saya setuju - itu tidak terlalu banyak."

"Apakah yang anda maksudkan dengan pokok seimbang?"

"Pokok yang tidak terherot, iaitu yang tidak mempunyai dahan yang panjang. Contohnya, jika unsur-unsur itu telah disusun semasa kita membina pokok itu, maka kita akan membuat pokok yang sangat panjang yang terdiri daripada satu dahan. "

"Hmm. Awak betul. Jadi apa yang kita buat?"

"Seperti yang anda mungkin telah meneka, pokok yang paling cekap mempunyai dahan yang lebih kurang sama panjang. Kemudian setiap perbandingan membuang bahagian terbesar subpokok yang tinggal."

"Jadi, kita perlu membina semula pokok itu?"

"Ya. Ia perlu «seimbang» — dibuat sedekat mungkin dengan pokok binari yang lengkap."

"Untuk menyelesaikan masalah ini, pokok pengimbangan diri telah dicipta.  Jika pokok itu menjadi herot selepas menambah elemen, maka ia menyusun semula elemen sedikit untuk menjadikan semuanya OK.  Berikut ialah contoh pengimbangan:"

"Sesetengah pokok ini dikenali sebagai pokok merah -hitam ."

"Kenapa mereka dipanggil merah-hitam?"

"Pencipta mereka melukis semua bucu menggunakan dua warna. Satu warna merah, dan satu lagi hitam. Bucu yang berbeza mematuhi peraturan yang berbeza. Ini membentuk keseluruhan asas untuk prosedur pengimbangan."

"Sebagai contoh:"

"Jadi apakah peraturan ini?"

"1) Bucu merah tidak boleh menjadi anak bucu merah."

"2) Kedalaman hitam setiap daun adalah sama (kedalaman hitam merujuk kepada bilangan bucu hitam pada laluan dari akar)."

"3) Akar pokok itu hitam."

"Saya tidak akan menerangkan cara ini berfungsi — kepala anda mungkin sudah meletup."

"Ya. Pemproses saya mengeluarkan sedikit asap."

"Ini pautan untuk anda. Jika anda mahu, anda boleh membaca lebih lanjut mengenainya di sini."

Pautan ke bahan tambahan

"Dan sekarang, pergi berehat."