Algoritm tushunchasi
Tartiblashgan va muvozanatlashgan daraxtlar
Download 86.83 Kb.
|
Algoritm tushunchasi-fayllar.org
|
33 Tartiblashgan va muvozanatlashgan daraxtlar
Uchlarni muvozanatlash - bu |h(L) − h(R)| = 2 chap va oʻng pastki daraxtlari balandliklari farqi boʻlgan taqdirda, |h(L) − h(R)| ≤ 2 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 diff(i) = h(L) − h(R) pastki daraxtlari balandliklari orasidagi farqni saqlaymiz. Muvozanatlashgan daraxtlar haqidagi teorema. Adelson-Velskiy va Landis quyidagi teoremani isbotladilar: Teorema. n ichki tugunli muvozanatli daraxt balandligi lg(n + 1) va 1.4405 lg(n + 2) − 0.3277 qiymatlar bilan chegaralangan. 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. 34 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. AVL daraxtiga yangi tugun kiritilganda paydo boʻladigan variantlarni koʻrib chiqaylik: • hl=hR. Yoqilgandan soʻng, L va R har xil balandliklarga aylanadi, ammo muvozanat mezonlari buzilmaydi; • hLmuvozanat mezonlari yanada yaxshilanadi; • hL>hR. Yoqilgandan soʻng muvozanat mezonlari buziladi va daraxtni qayta qurish kerak. Shunday qilib, biz AVL daraxtiga yangi tugunni kiritish uchun umumiy algoritmni tuzamiz: 1. Kiritilgan daraxtning ichida emasligiga ishonch hosil qilish uchun daraxtni aylanib oʻtish; 2. Yangi uchni kiritish va natijada balans koʻrsatkichini aniqlash; 3. Qidiruv yoʻli boʻylab "orqaga chekinish" va har bir uchda balans koʻrsatkichini tekshirish. Agar kerak boʻlsa, muvozanatni saqlash. 35 AVL daraxtlarining samaradorligini tahlil qilish 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. AVL daraxtiga yangi tugun kiritilganda paydo boʻladigan variantlarni koʻrib chiqaylik: • hl=hR. Yoqilgandan soʻng, L va R har xil balandliklarga aylanadi, ammo muvozanat mezonlari buzilmaydi; • hLmuvozanat mezonlari yanada yaxshilanadi; • hL>hR. Yoqilgandan soʻng muvozanat mezonlari buziladi va daraxtni qayta qurish kerak. Shunday qilib, biz AVL daraxtiga yangi tugunni kiritish uchun umumiy algoritmni tuzamiz: 1. Kiritilgan daraxtning ichida emasligiga ishonch hosil qilish uchun daraxtni aylanib oʻtish; 2. Yangi uchni kiritish va natijada balans koʻrsatkichini aniqlash; 3. Qidiruv yoʻli boʻylab "orqaga chekinish" va har bir uchda balans koʻrsatkichini tekshirish. Agar kerak boʻlsa, muvozanatni saqlash. 36 B-daraxtlar B daraxti (inglizcha B-tree) – izlash, qo'shish va o'chirish imkonini beradigan, juda koʻpshoxli muvozanatlashgan qidiruv daraxti. Tugunlari n bo'lgan B daraxti O(logn) balandlikka ega bo‘ladi. Tugun shoxlari soni bittadan bir necha minggacha bo'lishi mumkin (odatda, B-daraxtining shoxlanish darajasi daraxt ishlaydigan qurilma (disklar) xususiyatlari bilan belgilanadi). B-daraxtlar O(logn) ko'p dinamik to'plam amallarini o'z vaqtida bajarish uchun ham ishlatilishi mumkin. B daraxti birinchi marta 1970-yilda R. Bayer va E. Makkreyt tomonidan taklif qilingan. B daraxt strukturasi. B daraxti mukammal muvozanatlashgan, ya'ni uning barcha barglarining chuqurligi bir xil. B daraxti quyidagi xususiyatlarga ega ( t – bu daraxt parametrlari, B daraxtining minimal Download 86.83 Kb. Do'stlaringiz bilan baham: 
|