Mavzu: Ikkilik daraxtga element qo‘shish, element o‘chirish va qidiruv algoritmlari Bajardi: aminjonov mansur qabul Qildi: Isroilov Sh

Nihoyat, biz yangi tugunni y ning bolasi qilishimiz kerak . Agar y null bo'lsa, yangi tugun daraxtning ildizi bo'ladi, aks holda biz yangi tugunning ma'lumotlari y ning ma'lumotlaridan katta yoki kichikligini tekshiramiz va shunga mos rav ishda uni chap yoki o'ng bolaga aylantiramiz. .

if y==NULL
T.root = n
else if n.data < y.data
y.left = n
else
y.right = n
INSERT(T, n)
temp = T.root
y = NULL
esa temp != NULL
y = harorat
agar n.data < temp.data
temp = temp.chap
boshqa
temp = temp.to'g'ri
n.ota-ona = y
agar y==NULL bo'lsa
T.root = n
boshqa agar n.data < y.data
y.chap = n
boshqa
y.o'ng = n

BSTda o'chirish

Ikkilik qidiruv daraxtida uni to'liq ishlaydigan ma'lumotlar strukturasiga aylantirishimiz kerak bo'lgan oxirgi operatsiya tugunni o'chirishdir.
BST dan tugunni o'chirish uchun biz pastki daraxtni boshqasiga almashtiramiz, ya'ni bir pastki daraxtni boshqasining o'rniga ko'chirib o'tkazamiz.

Biz o'chirish protseduramizda ushbu texnikadan foydalanmoqchi ekanmiz, keling, avval u tugunida joylashgan pastki daraxt o'rniga v tugunida joylashgan pastki daraxtni ko'chirish kodini yozamiz .
Transplantatsiya qilish uchun bizning funktsiyamiz daraxtni oladi T , tugunlari u va v - TRANSPLANT(T, u, v).
Endi biz v tugunida joylashgan pastki daraxtni u tugunida joylashgan pastki daraxt o'rniga joylashtirmoqchimiz . Bu shuni anglatadiki, v ni ota-onangizning farzandi qilishimiz kerak, ya'ni u chap bola bo'lsa, v ota- onangizning chap farzandiga aylanadi . Xuddi shunday, agar u to'g'ri bola bo'lsa, v sizning ota-onangizning to'g'ri farzandiga aylanadi .

Shuningdek, u ota-onaga ega bo'lmasligi ham mumkin, ya'ni u T daraxtining ildizidir . Bunday holda, biz oddiygina v ni daraxtning ildizi sifatida qilamiz.

Shunday qilib, biz birinchi navbatda u ildiz yoki yo'qligini tekshiramiz, ya'ni u ning ota-onasi bor NULLyoki yo'q.
if u.parent == NULL //u is root
T.root = v
Endi siz chap bolamisiz yoki o'ng bolamisiz , tekshiramiz. Shunga ko'ra, biz v joylashtiramiz .
Agar u chap bola bo'lsa, u holda u ota-onasining chap tomoni u bo'ladi, ya'ni, rost bo'ladi va v ni uning chap bolasi sifatida qilamiz, ya'ni . u == u.parent.leftu.parent.left = v

if u.parent == NULL
...
elseif u == u.parent.left //u is left child
u.parent.left = v
else //u is right child
u.parent.right = v
Va nihoyat, v ning ota-onasini u ning ota-onasiga ham ko'rsatishimiz kerak .
if v != NULL
v.parent = u.parent
Shunday qilib, umumiy kod quyidagicha bo'ladi:
TRANSPLANT (T, u, v)
agar u.parent == NULL //u ildiz bo'lsa
T.root = v
elseif u == u.parent.left //u chap bola
u.parent.left = v
Aks holda // u to'g'ri bola
u.parent.right = v
agar v != NULL
v.ota-ona = u.ota-ona
Keling, ikkilik qidiruv daraxtidan tugunni o'chirishga e'tibor qarataylik.
O'chiriladigan tugun barg bo'lsin, deylik, bu tugunning ota-onasini ga ko'rsatib, bu tugunni osongina o'chirib tashlashimiz mumkin NULL.

NULLBundan tashqari, biz o'ng yoki chap bolani (ikkalasi ham ) o'chiriladigan tugunga ko'chirib o'tkazamiz, deb aytishimiz mumkin .
Shuningdek, biz faqat bitta bolali tugunni uning bolasini tugunga ko'chirib o'chirishimiz mumkin va bu ikkilik qidiruv daraxtining xususiyatiga ta'sir qilmaydi.

Ammo o'chiriladigan tugun ikkala bolaga ega bo'lsa, ishlar biroz murakkablashadi.

Bunday holda, biz o'chiriladigan tugunning o'ng pastki daraxtining eng kichik elementini topishimiz mumkin (o'ng pastki daraxtda chap bolasi bo'lmagan element) va uning mazmunini o'chiriladigan tugun bilan almashtiramiz.

Bu ikkilik qidiruv daraxtining xususiyatiga ta'sir qilmaydi, chunki u o'ng pastki daraxtning eng kichik elementi, shuning uchun o'ng pastki daraxtdagi barcha elementlar hali ham undan kattaroqdir. Bundan tashqari, chap pastki daraxtdagi barcha elementlar undan kichikroq edi, chunki u o'ng pastki daraxtda edi, shuning uchun ular hali ham kichikroq.
O'ng pastki daraxtning eng kichik elementida bola yo'q yoki bitta bola bo'ladi, chunki agar uning chap bolasi bo'lsa, u eng kichik element bo'lmaydi. Shunday qilib, biz birinchi ikkita holatda muhokama qilinganidek, ushbu tugunni osongina o'chirib tashlashimiz mumkin.

Biz tugunni o'chirish tushunchalarini tushundik, endi buning uchun kod yozishimiz mumkin.