Cukup lama saya bertarung dengan pohon merah-hitam ( selanjutnya - kchd ). Semua informasi yang saya temukan adalah semangat "daun dan akar pohon selalu hitam KARENA", "5 properti teratas dari pohon merah-hitam" atau "3 kasus saat menyeimbangkan dan 12 kasus saat menghapus node". Pengaturan ini tidak cocok untukku.
Saya tidak ingin menghafal properti pohon, kode pseudo, dan opsi penyeimbangan, saya ingin tahu alasannya. Bagaimana warna membantu keseimbangan? Mengapa simpul merah tidak memiliki anak merah? Mengapa kedalaman pohon diukur sebagai "tinggi hitam"?
Saya menerima jawaban atas pertanyaan-pertanyaan ini hanya ketika saya diberi tautan ke ceramah tentang dua atau tiga pohon, yang akan kita mulai.
Artikel ini dibagi menjadi 3 bagian logis. Saya sarankan membacanya dalam urutan yang ditunjukkan. Bagian pertama (yang ini) akan ditujukan untuk pengenalan tentang ccd dan mengetahuinya. Pada bagian kedua, kita akan berbicara tentang balancing dan penyisipan ke dalam ccd. Di bagian ketiga dan terakhir, kami akan menganalisis proses penghapusan node. Harap bersabar dan selamat membaca :)
Penolakan
Dalam artikel ini, tidak akan ada informasi tentang pro dan kontra pohon, aplikasinya, dll .: ada banyak informasi tentang asimtotik pohon dan bekerja dengannya di Internet.
Materi ini ditujukan bagi mereka yang sudah terbiasa dengan ccd dan sekarang ingin memahaminya, serta bagi mereka yang baru mengenalnya.
Artikel tidak akan berisi detail implementasi struktur.
— . .
-
- , -
, , - - , , , . - - .
- - , . - ( , ). 2-, - 3-. : . :
, .
- , - .
- - , .
, , 5. - 5 .
12. 12 (, ), "" ( , ), .. . 5-12.
. 17. . 5-12-17.
- , . ! "" . . 12, 5, - 17.
, , - . : , "" . 3 :
. , ( ).
. ( ).
. , .
.
, . 3. , . , 3 5. 3 5 . 3-5.
, :)
4 3-5. 3-4-5, , , . ? , .. "" 4 .
. , 4 , - , 4. 5. :
5 ? : - , - . 5 4, 5 , .. . 5 , "", 4-12 (, 5 , "" ).
, . :
, , .
, , , .
, , .
, . , , - . , - (, 4-5-12, , 5 4 12). , . , , ( , 7? 9?).
, , , . , , , . .
, , , . , , ( ). - .
-
, - - . - . ?
, 3-. 3- 2- . - , , , ( ), .
, , .
, - . , , ( , ).
-
, - , , 3- ( ). , , . , ( ).
1.
. , , - 3- 2-3 . , 4-, :)
2.
. , : .
3.
null- (, ) - . , . , , .
Karena kita telah menyentuh node nol, harus dikatakan bahwa semua node di pohon harus selalu memiliki dua turunan, dan jika referensi ke turunan adalah nol, maka itu mengarah tepat ke node nol. Faktanya, ini menimbulkan pertanyaan dalam implementasi, lebih mudah bagi saya untuk menambahkan node null (lebih sedikit masalah dengan iterator, balancing, dll.).
Properti 4.
Tinggi pohon diukur hanya dengan simpul hitam dan disebut "tinggi hitam". Di sini sekali lagi, semuanya secara umum menjadi jelas: simpul merah hanyalah tambahan dari simpul hitam, itu adalah bagian darinya, oleh karena itu, ketinggian dianggap berdasarkan pada simpul hitam.
Ini mengakhiri pendahuluan. Pada bagian selanjutnya, kita akan berbicara tentang cara memasukkan node ke dalam pohon dan menyeimbangkannya.