|
Reja qidiruv binar daraxti tushunchasiQo’yilayotgan yangi element chap yoki o’ng o’g’il bo’lishini aniqlash lozim
|
səhifə | 4/4 | tarix | 30.12.2023 | ölçüsü | 11,58 Kb. | | #167120 |
| 4gY1tIJRbr61EFKVy52ED6yB5b74D6XlEA6kx92RQo’yilayotgan yangi element chap yoki o’ng o’g’il bo’lishini aniqlash lozim. - Qo’yilayotgan yangi element chap yoki o’ng o’g’il bo’lishini aniqlash lozim.
- If(keykey) q->left=yangi;
- else q->right=yangi;
- search=yangi;
- return 0;
Binar daraxtdan elementni o’chirish prosedurasi - Tugunni o’chirib tashlash natijasida daraxtning tartiblanganligi buzilmasligi lozim. Tugun daraxtda o’chirilayotganda 3 hil variant bo’lishi mumkin:
- 1) Topilgan tugun terminal (barg). Bu holatda tugun shunchaki o’chirib tashlanadi.
- 2) Topilgan tugun faqatgina bitta o’g’ilga ega. U holda o’g’il ota o’rniga joylashtiriladi.
- 3) O’chirilayotgan tugun ikkita o’g’ilga ega. Bunday holatda shunday qism daraxtlar zvenosini topish 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 o’ng tomondagi elementi (ushbu zvenoga erishish uchun keyingi uchiga chap shoh orqali o’tib, navbatdagi uchlariga esa, murojaat NIL bo’lmaguncha, faqatgina o’ng shohlari orqali o’tish zarur).
- - yoki o’ng qism daraxtning eng chap elementi (ushbu zvenoga erishish uchun keyingi uchiga o’ng shoh orqali o’tib, navbatdagi uchlariga esa, murojaat NIL bo’lmaguncha, faqatgina chap shohlari orqali o’tish zarur).
- O’chirlayotgan element chap qism daraxtining eng o’ngidagi element o’chirilayotgan element uchun “Predshestvennik” bo’ladi ( 12 uchun – 11 bo’ladi). Merosxo’r esa o’ng qism daraxtning eng chapidagi tuguni (12 uchun - 13).
Merosxo’rni topish algoritmini ishlab chiqaylik (5.9 chizma). - p – ishchi ko’rsatkich;
- q - r dan bir qadam orqadagi ko’rsatkich;
- v – o’chiralyotgan tugun merosxo’rini ko’rsatadi;
- t - v dan bir qadam orqada yuradi;
- s - v dan bir qadam oldinda yuradi (chap o’g’ilni yoki bo’sh joyni ko’rsatib boradi).
-
- Yuqoridagi daraxt bo’yicha qaraydigan bo’lsak, oxir oqibatda, v ko’rsatkich 13 tugunni, s esa bo’sh joyni ko’rsatishi lozim.
- 1) Elementni qidirish prosedurasi orqali o’chirilayotgan elementni topamiz. r ko’rsatkich o’chirilanyotgan elementni ko’rsatadi.
- 2) O’chiriladigan elementni o’rniga qo’yiluvchi tugunga v ko’rsatkich qo’yamiz
- Mukammal qidiruv daraxti – bu muvozalangan binary daraxtdir/
-
-
- NAZORAT SAVOLLARI
- binary daraxti qanday quriladi ?
- Daraxt bir tomonlama yo’naltirilgan ro’yxatdagi kabi bo’lsa, qidiruv vaqti
- Qancha?
- 3.Agar daraxt muvozalangan bo’lsa-chi ?
Dostları ilə paylaş: |
|
|