T daraxtini va o'chiriladigan z tugunini - funktsiyasiga o'tkazishdan boshlaymiz DELETE(T, z).
Endi z tugunining bolalar sonini tekshirishimiz kerak . Avval z tugunining chap bolasi bor yoki yo'qligini tekshiramiz NULL. Agar chap bola bo'lsa NULL, u faqat bitta bolaga ega (o'ngda) yoki yo'q. Ikkala holatda ham biz uning to'g'ri bolasini unga ko'chirib o'tkazishimiz mumkin.
DELETE(T, z)
if z.left == NULL
TRANSPLANT(T, z, z.right)
Xuddi shunday, biz keyingi bolaning to'g'ri NULLyoki yo'qligini tekshiramiz.
DELETE(T, z)
...
elseif z.right == NULL
TRANSPLANT(T, z, z.left)
Agar yuqoridagi holatlarning hech biri to'g'ri bo'lmasa, z tugunining ikkala farzandi ham bor va biz minimalni o'ng pastki daraxtda ( y ) topamiz. Endi biz ushbu minimal tugunni ( y ) z o'rniga qo'yishimiz kerak .
Do'stlaringiz bilan baham: |
