Bagian 1. Pendahuluan
Bagian 2. Penyeimbangan dan penyisipan
Ini adalah bagian 2 dari seri Memahami Pohon Merah-Hitam. Jika Anda melewatkan bagian pertama, saya sangat menyarankan untuk memeriksanya di sini . Di sana kami memilah alasan kemunculan cchd dan meletakkan beberapa propertinya di rak.
Pada bagian ini kita akan melihat penyisipan dan penyeimbangan. Hal-hal ini berjalan berdampingan, tanpa keseimbangan pohon akan kehilangan sifat-sifatnya, dan akan ada sedikit pengertian darinya.
Mengingat bahwa kchd adalah pohon 2-3 (kadang-kadang saya akan mengingatkan Anda tentang ini), kami akan segera mulai dengan konstruksinya. Tetapi beberapa klarifikasi masih dibutuhkan sekarang.
Semua node yang disisipkan, kecuali akar pohon, disisipkan dengan warna merah. Hal ini dijelaskan oleh fakta bahwa kami selalu pertama kali menambahkan nilai ke node yang sudah ada dan baru setelah itu kami melakukan penyeimbangan (ingat situasi dengan 4-node yang dihasilkan).
Pada bagian pertama, kami menemukan bahwa kami membongkar pohon merah-hitam sisi kiri , dari sini dapat disimpulkan bahwa simpul merah hanya dapat terletak di sebelah kiri (kasus sebaliknya membutuhkan penyeimbangan).
Mari kita juga membahas tiga operasi yang kita butuhkan saat menyeimbangkan. Saya meminta Anda untuk tidak memikirkannya sekarang dan menyelidiki lebih detail selama pembangunan pohon. Saya akan memberikan uraiannya di sini agar tidak mengganggu nanti :)
- . , , -. , . - .
, . , .
( )
. .
, parentNode ( parentNode - x, childNode - y) childNode, . ! , , childNode , parentNode , ( , childNode - , , parentColor = RED, ). "" childNode (, tempNode). , . , childNode, parentNode, childNode, , (/) parentNode, parentNode .
( )
, . .
, parentNode . , parentNode - . , .
, ( , ), parentNode! ( ). .
- .
, .
24. . , , .
, , 5. , .
1 5. . , !
, - ( ). . - . , - . \ . , .
. , , , .
, 3 : , , .
1 , . . 5 - , ( ). 24 , , .
. - . , . - 24. .
, . ! . ( 24 , , )
( )! 2-3 .
, 2-3 ("" + ), , :) , , 2-3 , - , , "" .
. 15. 24. .
3. , 1, -1.
, . . + . ( , , ). , .
! .
, - , .
- 8. , . . , , .
+ .
, ( 15) - , . . , - . . !
- - .
, . , , . . .
. , . 2-3 ( 13 16, , ).
- , , \. .
, , .
-
-
- - , . , , . , !
- , . , , . , !
Sekarang Anda dapat membahas konstruksi pohon lagi dan menganalisis, memeriksa properti dari artikel pertama, mengajukan pertanyaan "bagaimana jika ...?" (percayalah, ini sangat berguna!). Secara umum, ini semua yang ingin saya ceritakan kepada Anda tentang memasukkan node ke dalam pohon merah-hitam sisi kiri.
Sedikit tentang operasi pencarian nilai
Operasi memperoleh tidak akan berbeda dengan pencarian di pohon biner lainnya - warna tidak terlibat di dalamnya dengan cara apa pun.
Kesimpulan
Ini menyimpulkan bagian kedua kita tentang penyisipan dan penyeimbangan ccd. Ajukan pertanyaan Anda, kritik dan lengkapi artikel di bawah ini! Di bagian terakhir, ketiga, bagian saya akan berbicara tentang topik tersulit dari pohon merah-hitam - menghapus elemen. Sampai jumpa:)