Fizika-matematika fakulteti

Yuqoridan pastga 2-3-4 daraxt. O'chirish uchun birinchi iliqlik sifatida pastga tushishda ham, yuqoriga ko'tarilishda ham o'zgarishlarni amalga oshiradigan sodda algoritmni ko'rib chiqamiz: 2-3-4 daraxt uchun qo'shimchalar algoritmi, bu yerda 2-3 daraxtda ko'rgan vaqtinchalik 4-tugunlar daraxtda turishi mumkin. Kiritish algoritmi joriy tugun 4-tugun emasligiga ishonch hosil qilish uchun pastga tushadigan yo'lda o'zgarishlarni amalga oshirishga asoslanadi (shuning uchun yangi kalitni pastki qismga kiritish uchun joy borligiga ishonamiz) va har qanday 4-tugunni muvozanatlash uchun yo'lni ochishga o'zgarishlar yaratilgan bo'lishi mumkin. Pastga tushish yo'lidagi o'zgarishlar aynan to'rtta tugunni 2-3 daraxtga bo'laklashda ishlatilgan. Agar ildiz 4-tugun bo'lsa, uni uchta 2-tugunga ajratamiz va daraxtning balandligini 1-ga ko'paytiramiz. Daraxtdan pastga ketayotganimizda, agar ota-ona sifatida 2-tugunli 4-tugunga duch kelsak, 4-tugunni ikkita 2 tugunga ajratamiz va o'rta tugmachani ota-onaga o'tkazamiz, uni 3 tugunga aylantiramiz; agar 3 tugunli ota-ona sifatida 4-tugunga duch kelsak, biz 4-tugunni ikkita 2-tugunga ajratamiz va o'rta tugmachani ota-onaga o'tkazamiz va uni 4-tugunga aylantiramiz. 4-tugunni 4 tugunli invariantning ota-onasi tomonidan ko'rib chiqsak, tashvishlanishga hojat yo'q. Pastki qismida, yana invariant, 2 tugunli yoki 3 tugunli, shuning uchun bizda yangi kalitni kiritish uchun joy bor. Ushbu algoritmni qizil qora BSTlar bilan amalga oshirish uchun :

■ 4-tugunni uchta 2-tugunning muvozanatli pastki qismi sifatida ifodalab, chap va o'ng bolani ota-onasiga qizil ulanish bilan ulanadi.

■ Daraxt bo'ylab 4-tugunni rangli chiziqlar bilan ajratiladi.

■ O'rnatish paytida daraxtni aylantirish bilan 4-tugunni muvozanatlanadi.

Shunisi e'tiborga loyiqki, put() kodning bir qatorini siljitish orqali 2-3-4 daraxtlarni yuqoridan pastga tushirish mumkin: colorFlip () va rekursiv qo'ng'iroqlardan oldin o'tkaziladi. Ushbu algoritm bir nechta jarayonlar bitta daraxtga kirish huquqiga ega bo'lgan dasturlarda 2-3 daraxtga nisbatan bir qator afzalliklarga ega, chunki u har doim bog'lanish yoki ikkita tugun ichida ishlaydi. Keyingi o'chirish algoritmlari shunga o'xshash sxema bo'yicha tuzilgan va bu daraxtlar uchun ham, 2 3 daraxt uchun ham samarali.

24-rasm. Yuqoridan pastga 2-3-4 daraxtga kiritish uchun transformatsiyalar.