Mustaqil ishlash uchun masalalar: 1) Quyidagi daraxtlarning pryufer kodini toping.(1, 1, 7, 6, 13, 1, 7, 12, 6, 9, 4, 5, 3) (1, 2, 8, 3, 1, 10, 1, 1, 6, 5, 3, 2, 9) (2, 5, 7, 12, 10, 11, 7, 7, 6, 9, 4, 5)9-§. Tartiblangan va muvozanatlashgan daraxtlar 9.1. AVL daraxti AVL daraxt.Uchlarni muvozanatlash |
Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. EshonqulovBog'liq ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARIBu sahifa navigatsiya:
- Mustaqil ishlash uchun masalalar: 1) Quyidagi daraxtlarning pryufer kodini toping.
- (1, 1, 7, 6, 13, 1, 7, 12, 6, 9, 4, 5, 3) (1, 2, 8, 3, 1, 10, 1, 1, 6, 5, 3, 2, 9) (2, 5, 7, 12, 10, 11, 7, 7, 6, 9, 4, 5)
- 9-§. Tartiblangan va muvozanatlashgan daraxtlar 9.1. AVL daraxti AVL daraxt.
- Uchlarni muvozanatlash
Mavzu yuzasidan savollar:
1. Daraxt ma‘lumotlar strukturasiga ta‘rif bering
2. Daraxtning eng asosiy tushunchalariga toʻxtalib oʻting.
3. Pryufer kodini hosil qilish va qoʻlllanishi haqida gapiring
4. Pryufer kodi asosida daraxtni tiklash qanday amalga oshiriladi?
5. Daraxt ma‘lumotlar strukturasi qoʻllaniladigan sohalarga qaysilar
kiradi?
119
Mustaqil ishlash uchun masalalar:
1) Quyidagi daraxtlarning pryufer kodini toping.
2) Quyidagi Pryufer kodi berilgan. Ushbu kodga koʻra
daraxtlarni hosil qiling.
(2, 2, 7, 2, 11, 11, 7, 7, 6, 9, 4, 5)
(1, 1, 7, 6, 13, 1, 7, 12, 6, 9, 4, 5, 3)
(1, 2, 8, 3, 1, 10, 1, 1, 6, 5, 3, 2, 9)
(2, 5, 7, 12, 10, 11, 7, 7, 6, 9, 4, 5)
(12, 2, 1, 1, 1, 1, 3, 3, 4, 1, 2, 3, 8, 9)
120
9-§. Tartiblangan va muvozanatlashgan daraxtlar
9.1. AVL daraxti
AVL
daraxt.
AVL-daraxt
(inglizcha
AVL-Tree)
bu
muvozanatlashgan ikkilik qidiruv daraxti boʻlib, unda quyidagi
xususiyat qoʻllab-quvvatlanadi: uning har bir uchlari uchun uning ikkita
ostki daraxtining balandligi 1 dan koʻp boʻlmagan qiymatga farq qiladi.
AVL daraxtlari birinchi marta 1962-yilda AVL daraxtlaridan
foydalanishni taklif qilgan G. M. Adelson-Velskiy va E. M. Landisning
ismlarining birinchi harflari bilan nomlangan.
Uchlarni muvozanatlash
- bu
| |
chap va oʻng
pastki daraxtlari balandliklari farqi boʻlgan taqdirda,
| |
daraxtining xususiyati tiklanishi uchun ushbu uchlarning pastki
daraxtidagi ajdod va avlod munosabatlarini oʻzgartiradigan amal, aks
holda hech narsani oʻzgartirilmaydi. Muvozanatlash uchun biz har bir
uch uchun uning chap va oʻng
pastki daraxtlari
balandliklari orasidagi farqni saqlaymiz.
Daraxtning balandligi uning maksimal darajasi, ildizdan tashqi
tugunga qadar eng uzun yoʻlning uzunligi sifatida aniqlanadi. Ikkilik
qidiruv daraxti muvozanatli deyiladi, agar biron bir tugunning chap
pastki daraxtining balandligi oʻng pastki daraxtning balandligidan ± 1
dan oshmasa. Keyingi 36-rasmda koʻrsatilgan 5 ta balandlikdagi 17 ta
ichki tugunli muvozanatli daraxt; muvozanat koeffitsiyenti har bir tugun
ichida belgilar bilan va oʻng va chap pastki daraxtlar (+1, 0 yoki -1)
balandliklari orasidagi farq kattaligiga muvofiq belgilanadi.
|
| |
