agar kiritilishi kerak bo'lgan qiymat biz joylashgan tugun qiymatidan kam bo'lsa, chapga o'ting-chap avlod uchun bir xil funktsiyani chaqiring;
agar qiymat biz hozir bo'lgan joyga teng yoki undan katta bo'lsa, o'ng tomonga o'ting — biz o'ng avlod uchun funktsiyani chaqiramiz;
agar biz hali tugun bo'lmagan joyga etib borsak, u erda tugun yarating va u erda yangi qiymat qo'ying;
agar biz hali tugun bo'lmagan joyga etib borsak, u erda tugun yarating va u erda yangi qiymat qo'ying;
balanslash funktsiyasini chaqiring. Qo'shish rekursiv bo'lgani uchun, muvozanatlash kiritish funktsiyasining oxirgi ochiq nusxasidan boshlab va birinchisiga qadar amalga oshiriladi.
Olib tashlash. O'chirish funktsiyasi ham rekursiv, ammo bu qiyinroq. Avval siz o'chiriladigan elementni topishingiz kerak, keyin uning o'ng avlodiga o'ting, agar mavjud bo'lsa va u erda minimal tugunni toping. Va keyin nuances boshlanadi:
Olib tashlash. O'chirish funktsiyasi ham rekursiv, ammo bu qiyinroq. Avval siz o'chiriladigan elementni topishingiz kerak, keyin uning o'ng avlodiga o'ting, agar mavjud bo'lsa va u erda minimal tugunni toping. Va keyin nuances boshlanadi:
ikkilik qidiruv daraxtining tuzilishi mantig'iga ko'ra, minimal tugun maksimal bitta avlodga ega bo'lishi mumkin — o'ngda. Shuning uchun minimal tugunni "olib tashlash" funktsiyasi uning o'ng avlodini qaytaradi-uni almashtirishda foydali bo'ladi;
chapda, minimal tugunga olib tashlangan tugunning chap avlodi, o'ngda — minimal ajratilgandan keyin o'ng avloddan qolgan narsa qo'shiladi;
balanslash mavjud.
Daraxt tuguni o’chrilayotganda 3 hil holat bo’lishi mumkin:
Topilgan tugun terminal. Bu holatda tugun shunchaki o’chirib tashlanadi.
Topilgan tugun faqatgina bitta o’g’ilga ega. U holda o’g’il ota o’rniga joylashtiriladi.
O’chirilayotgan tugun ikkita o’g’ilga ega. Bunday holatda shunday qisim daraxtlar zvenosini toppish lozimki, uni o’chirilayotgan tugun o’rniga qo’yish mumkin bo’lsin. Bunday zveno har doim mavjud bo’ladi. Bu
Yoki chap qism daraxtning eng ‘ng tomondagi tuguni (ushbu zvenoga erishish uchun keying uchiga chap shoh orqali o’tib, navbatdagi uchlariga esa murojaat NIL bo’lmagunicha, faqatgina o’ng shohlari orqali o’tish zarur).
Yoki o’ng qisim daraxtning eng chap tuguni (ushbu zvenoga erishish uchun keying uchta o’ng shoh orqali o’tib, navbatdagi uchlariga esa, murojaat NIL bo’lmaguncha, faqatgina chap shohlari orqali o’tish zarur).
