Fizika-matematika fakulteti

Ota-onasi 2-tugun bo'lgan elementni 3-tugunga joylashtirish. Ikkinchi urinish sifatida, ota-onasi 2-tugun bo'lgan pastki qismdagi 3-tugun bo'yicha qidirish tugadi deb taxmin qilamiz. Bu holda biz daraxtda mukammal muvozanatni saqlab, yangi tugmachani ochishimiz mumkin, vaqtincha 4-tugunni avval aytib o'tilganidek tuzamiz va keyin 4 ta tugunni xuddi ta'riflanganidek ajratamiz, lekin keyin yangi yaratish o'rniga yangi tugmani ota-onasiga o'tkazib, o'rta tugmachani ushlab turamiz, Bizning taxminimizga ko'ra, ota-onada buni amalga oshirish uchun joy bor: ota-ona 2 tugunli (bitta kalit ikkita havolali) edi va 3 tugunga aylandi (ikkita kalit va uchta ulanish bilan). Bundan tashqari, bu transformatsiya 2-3 ta daraxtning aniq xususiyatlariga ta'sir qilmaydi. Daraxt buyurtma qilinmoqda, chunki o'rta kalit ota-ona tomon yo'naltiriladi va u mutanosib ravishda saqlanib qoladi: agar barcha nol ulanishlar qo'shilishdan oldin ildizdan bir xil masofada joylashgan bo'lsa, ular kiritilganidan keyin ham barchasi bir xil masofada bo'ladi. Ushbu o'zgarishlar 2-3 daraxt dinamikasining asosini tashkil qiladi.

7-rasm. Ota-onasi 2-tugun bo'lgan elementni 3-tugunga joylashtirish.

Ota-onasi 3-tugun bo'lgan elementni 3-tugunga joylashtirish. Endi qidiruv 3-tugunda tugaydi deb taxmin qilamiz. Yana, biz yuqorida aytib o'tilganidek, vaqtincha 4 hosil tugunni qilamiz, keyin uni ajratamiz va o'rtadagi kalitni ota-onaga joylashtiramiz. Ota 3-tugun edi, shuning uchun biz uni 4 tugunli bo'linishdan o'rta kalitni o'z ichiga olgan vaqtincha yangi 4-tugun bilan almashtiramiz.

8-rasm. Ota-onasi 3-tugun bo'lgan D elementni 3-tugunga joylashtirish.

Keyin, xuddi shu tugunni bir xil o'zgartiramiz. Ya'ni, yangi 4-tugunni ajratamiz va o'rtadagi kalitni ota-onasiga joylashtiramiz. Umumiy ishning kengayishi aniq: daraxtni davom ettirmoqdamiz, 4 tugunni ajratamiz va o'rta tugmachalarni ota-onalariga 2 tugunli bo'lgunga qadar joylashtiramiz, uni 3-tugun bilan almashtiramiz, bu esa qo'shimcha bo'lishni talab qilmaydi.