11-mavzu(davomi): Qidiruv binar daraxtini muvozanatlash algoritmlari

Natijada quyidagicha muvozanatlangan binar daraxt hosil bo‘ladi. Oldingi ko‘rinishida daraxt balandligi 4 ga teng edi. Endi esa 3 ga teng. Lekin bu algoritmning bir muncha noqulayligi bor

1 2 3

Bog'liq
IJgT41kLxVhx0kVnr8gDPLkXAEC4O2BzJhk19p82 (1)

Natijada quyidagicha muvozanatlangan binar daraxt hosil bo‘ladi. Oldingi ko‘rinishida daraxt balandligi 4 ga teng edi. Endi esa 3 ga teng. Lekin bu algoritmning bir muncha noqulayligi bor.
- Oldin daraxtni chapdan o‘ngga skanerlab elementlardan massiv hosil qilish kerak.
Bu esa xotiradan joy talab etadi.
Bu usulda daraxtni boshqatdan qurish kerak

19
30
23
15
3
12
29
44
16

Binar daraxtlar bilan ishlaganda unga element qo‘shish yoki o‘chirishda uning muvozanatlanganligi buzilishi mumkin. Bunday xollarda uni muvozanatlab turish kerak. Muvozanatlangan daraxt ko‘rinishlari:
AVL daraxt
Qora-qizil daraxt
B-daraxt va x.k.

AVL-daraxtining nomi uning mualliflari ismlari bosh xarflaridan olingan bo‘lib, ular – sovet matematiklari Georgiy Maksimovich Adelson-Velskiy va Evgeniy Mixaylovich Landis, 1962 yil ushbu muvozanatlangan AVL daraxtni taklif etishgan.
AVL daraxt bu muvozanatlangan binar daraxt bo‘lib, unda xar bir tugunning o‘ng va chap qism daraxtlari balandliklari orasidagi farq 1 dan katta emas.
AVL daraxtda xar bir tugunning muvozanatlanganlik darajasi xaqidagi ma’lumotni saqlash uchun xar bir tugunga qo‘shimcha maydon kiritiladi.

Asosiy g‘oya: agar element ko‘shish, o‘chirish amallarida muvozanat buzilsa, u xolda daraxt muvozanatlanadi
Tugunning muvozanatlanganlik koeffitsienti (balance factor) bu tugunning chap va o‘ng qism daraxtlari balandligi farqi
AVL daraxtda xar bir tugunning muvozanatlanganlik koeffitsienti (-1, 0, 1) to‘plamdan qiymat qabul qiladi
Tugun balandligi (height) bu undan eng uzoq joylashgan barg tugungacha bo‘lgan balandlik xisoblanadi.
Barg tugunnning balandligi 0 ga teng.
Bo‘sh qism daraxtning balandligi -1 ga teng.

Download 0.63 Mb.

Do'stlaringiz bilan baham:

1 2 3