135
1) Agar bargdan o'chirish sodir bo'lsa, unda qancha kalit borligini
tekshirish kerak. Agar t-1 dan ko'p bo'lsa, biz shunchaki o'chirib
tashlaymiz va boshqa hech narsa qilishimiz shart emas. Aks holda,
agarda t-1 dan ortiq kalitlarni o'z ichiga oluvchi qo'shni barg bo'lsa
(uning yonida joylashgan va avlod-ajdodi bir xil bo'lsa), biz qo'shni
tugunning qolgan kalitlari orasidagi ajratuvchi bo'lgan bu qo'shnidan
kalitni tanlaymiz. Bu kalit k
1
bo'lsin. Avval tugunni va uning qo'shnisini
ajratuvchi asosiy tugundan k
2
kalitini tanlaymiz. Kerakli kalitni manba
tugundan olib tashlaylik (o'chirilishi kerak edi), bu tugunga k
2
ni
tushiring va ajdod tugunidagi k
2
o'rniga k
1
qo'ying. Tushunarli bo'lishi
uchun quyida "9" tugmasi o'chirilgan rasm (48 -rasm) ko'rsatilgan. Agar
bizning tugunning barcha qo'shnilarida t-1 kalitlari bo'lsa. Keyin biz uni
qo'shnisi bilan birlashtiramiz, kerakli kalitni o'chirib tashlaymiz va bu
ikkita "sobiq" qo'shnilar uchun ajratuvchi bo'lgan avlod-ajdod
tugunining kaliti, yangi tashkil etilgan tugunimizga o'tamiz (bu, albatta,
undagi mediana bo'ladi).
