Ağacların tətbiqi

5.1 Məlumatların axtarışı üçün ağaclardan istifadə

Məlumatların axtarışı üçün xüsusi ağac növləri - Binar Axtarış Ağacları (Binary Search Trees — BST) istifadə olunur:

Binar Axtarış Ağacları (BST) məlumatları belə təşkil edir ki, hər hansı bir düyün üçün sol alt ağacdakı bütün açarlar həmin düyünün açarından kiçik, sağ alt ağacdakı bütün açarlar isə həmin düyünün açarından böyükdür.

Bu xüsusiyyət axtarış əməliyyatlarının effektiv yerinə yetirilməsinə imkan yaradır.

İş prinsipləri:

• Axtarış BST-də kökdən başlayır.
• Əgər axtarılan dəyər cari düyünün dəyərindən kiçikdirsə, axtarış sol alt ağaca keçir.
• Əgər axtarılan dəyər böyükdürsə, axtarış sağ alt ağaca keçir.
• Proses axtarılan element tapılana qədər və ya ağacın sonuna çatana qədər təkrarlanır.

Üstünlüklər:

• Orta axtarış vaxtı — O(log n), burada n — ağacdakı düyünlərin sayıdır.
• Axtarışın effektivliyi ağacın balanslı olub-olmamasından asılıdır.

5.2 Ağacla sıralama

Ağacla sıralama — bu, binary search tree (BST) istifadə edərək həyata keçirilən sıralama üsuludur. Elementlər BST-ə əlavə olunur, sonra isə ağac "in-order" (sol alt ağac → cari düyün → sağ alt ağac) qaydasında gəzildikdə sıralanmış massiv əldə edilir.

Alqoritm addımları:

1. Massivin bütün elementlərini binary search tree-ə əlavə etmək.
2. Sıralanmış massiv əldə etmək üçün ağacı "in-order" qaydasında gəzmək.

Üstünlüklər:

• Ağacla sıralama orta halda O(n log n) vaxt təmin edir.
• Stabil sıralama təmin edir (əgər ilkin məlumatlar eyni elementlərdən ibarətdirsə, onların nisbi sıralaması qorunur).

Çatışmazlıqlar:

Ən pis halda, ağac balanssız olduqda, vaxt O(n^2) qədər ola bilər.

5.3 Ağaclardan istifadə edilərək həll olunan məsələlərin nümunələri

1. Minimum və maksimum elementin axtarışı:

Təsvir:

• BST-də minimum dəyəri tapmaq üçün ən sol düyünə keçmək lazımdır.
• Maksimum dəyəri tapmaq üçün ən sağ düyünə keçmək lazımdır.

Tətbiqi:

• Ehtiyatların idarə olunması sistemlərində məhsulların minimum və maksimum sayını tapmaq üçün istifadə olunur.
• Bank sistemlərində minimum və maksimum tranzaksiyaların müəyyən edilməsi üçün istifadə olunur.

2. Aralıq axtarışı:

Təsvir:

• Məlum bir aralıqda yerləşən bütün elementləri tapmaq.
• "in-order" qaydasında keçidlə yanaşı əlavə yoxlama aparılır, düyünün aralığa düşüb-düşmədiyini yoxlamaq üçün.

Tətbiqi:

• Məlumat bazalarında aralıq sorğularının icra edilməsi üçün.
• Monitorinq sistemlərində parametrlərin müəyyən edilmiş hədlərdə izlənməsi üçün.

3. Avtotamamlanma (Autocomplete) əməliyyatlarının dəstəklənməsi:

Təsvir:

• Mətnlərin (məsələn, sözlərin) ağac şəklində (məsələn, prefiks ağacı) saxlanılması.
• Verilən prefiksdən başlayan bütün mətnlərin tez tapılması.

Tətbiqi:

• Axtarış sistemlərində sorğu daxil edərkən təkliflər üçün.
• Redaktor proqramlarında avtotamamlanma təklifləri üçün.

4. Marşrutlar və yolların optimallaşdırılması:

Təsvir:

• Nöqtələrin və marşrutların ağac şəklində saxlanılması.
• Ağaclarda alqoritmlərdən istifadə edərək optimal yolların və minimal məsafələrin axtarışı.

Tətbiqi:

• Naviqasiya sistemlərində marşrutların hazırlanması üçün.
• Logistika sistemlərində çatdırılmanın optimallaşdırılması üçün.

5. Hierarxik məlumatların təşkili:

Təsvir:

• Ağaclardan istifadə edərək belə olan hierarxik strukturların təqdimatı və idarə olunması: təşkilati strukturlar, fayl sistemləri və nəsil xətləri.

Tətbiqi:

• Korporativ informasiya sistemlərində şirkət strukturunun təqdimatı üçün.
• Məzmun idarəetmə sistemlərində (CMS) faylların və sənədlərin təşkili üçün.

1

Опрос

Qraf və ağaclar,  55 уровень,  4 лекция

недоступен

Qraf və ağaclar

Qraf və ağaclar

Открыть