Kompyuter injiniringi” fakulteti “axborot texnologiyalari” kafedrasi

1-amal. Daraxtda o’tish.

Daraxtda o’tish asosan uchta ko’rinishi mavjud, ya’ni berilgan daraxtda:

To’g’ri o’tish: Ildiz »» Chap qismdaraxt »» O’ng qismdaraxt

Natijada hosil bo’lgan ro’yxat: {1, 2, 4, 8, 5, 9, 10, 3, 6, 7}

Teskari o’tish: Chap qismdaraxt »» Ildiz »» O’ng qismdaraxt

Natijada hosil bo’lgan ro’yxat: {8, 4, 2, 9, 5, 10, 1, 6, 3, 7}

Oxiridan o’tish: Chap qismdaraxt »» O’ng qismdaraxt »» Ildiz

Natijada hosil bo’lgan ro’yxat: {8, 4, 9, 10, 5, 2, 6, 7, 3, 1}

2-amal. Daraxtga yangi tugun qo’yish.

Daraxtga biror bir yangi tugun qo’shishdan oldin daraxtda berilgan qiymat bo’yicha qidiruvni amalga oshirish lozim bo’ladi.

Agar berilgan qiymatga teng tugun mavjud bo’lsa, u holda dastur o’z ishini yakunlaydi, aks holda daraxtga ushbu qiymatga teng bo’lgan tugunni qo’shish amalga oshiriladi.

Eslatma: Daraxtda yangi tugun faqatgina ko’rsatkichlarining kamida bittasi bo’sh bo’lgan tugundan keyin qo’yiladi.

3-amal. Binar daraxtdan elementni o’chirish.

Daraxt tuguni o’chirilayotganda 3 ta holat bo’lishi mumkin:

1-holat. Topilgan tugun terminal (barg). Bu holatda tugun shunchaki o’chirib tashlanadi.

2-holat. Topilgan tugun faqatgina bitta o’g’ilga ega. U holda o’g’il ota o’rniga joylashtiriladi.

3-holat. O’chirilayotgan tugun ikkita o’g’ilga ega. Bunday holatda shunday qism daraxtni topish lozimki, uni o’chirilayotgan tugun o’rniga qo’yish mumkin bo’lsin. Bunday qismdaraxt har doim mavjud bo’ladi. Bu

• 
  chap qism daraxtning eng o’ng tomondagi tuguni;
  
• 
  o’ng qism daraxtning eng chap tuguni.
  

1-holat. Topilgan tugun terminal (barg).


O’chirilayotgan tugun


2-holat. Topilgan tugun faqatgina bitta o’gilga ega.


Иккинчи ҳолат ўчириладиган тугун битта ўғилга эга

O’chirilayotgan tugun

3-holat. O’chirilayotgan tugun ikkita o’g’ilga ega.

4-amal. Binar daraxtda qidiruv.

Mazkur amal (algoritm)ning vazifasi shundan iboratki, u berilgan qiymat bo’yicha daraxt tugunini izlab topishga yordam beradi. Qidiruv operatsiyasining davomiyligi daraxt tuzilishiga bog’liq bo’ladi. Haqiqatdan, agar elementlar daraxtga qiymatlari o’sish (kamayish) tartibida kelib tushgan bo’lsa, u holda daraxt bir tomonga yo’nalgan ro’yxat hosil qiladi (chiqish darajasi bir bo’ladi, ya’ni yagona shohga ega), masalan:

Bu holda daraxtda qidiruv vaqti, bir tomonlama yo’naltirilgan ro’yxatdagi kabi bo’lib, o’rtacha qarab chiqishlar soni N/2 bo’ladi.

Agar daraxt muvozanatlangan bo’lsa, u holda qidiruv eng samarali natija beradi. Bu holda qidiruv dan ko’p bo’lmagan elementlarni ko’rib chiqadi.