Mühazirə 1 Giriş Əsas anlayışlar. "Məlumat"

Balanslaşdırılmış ağac

Balanslaşdırma təpənin hündürlüyü anlayışı ilə əlaqədardır. Təpənin hündürlüyü belə təyin olunur:

L=k+1
k – baxılan təpəyə qədər budaqların sayıdır.
İstənilən açarın tapılması üçün müqayisə elementlərinin sayı açarın aid olduğu təpənin hündürlüyü ilə təyin olunur. Ağacın hündürlüyü maksimum hündürlüyə malik olan yarpağın hündürlüyü ilə təyin olunur. Ağac o vaxt balanslaşdırılmış hesab olunur ki, yarpaqların hündürlükləri arasındakı fərq 1 – dən böyük olmasın.

Şəkil 4.8. Balanslaşdırılmış ağac

Ağacın balanslaşdırılmaması onunla işləməyi çətinləşdirir. Bu zaman axtarıs üçün müqayisələrin sayı çox olur. Odur ki, praktikada əsasən balanslaşdırılmış ağaclardan istifadə olunur. Bu ağaclara ümumi adla B- trie deyilir.

B ağaclar

Bu ağaclar açarların (indekslərin) təşkili üçün ən səmərəli vasitə hesab olunurlar. Balalanslaşma belə aparılır: Ağacda saxlanan açarların təxmini sayı təyin olunur və hər təpədən açarlar elə bölüşdürülür ki, ondan solda və sağda yerləşdirilmiş alt ağaclardakı açarların ( təpələrin ) sayı bir – birindən çox fərqlənməsin, təxminən eyni olsun. Ağaca eyni açarların (təpələrin) daxil edilməsi və lazımsız açarların silinməsi də binar ağacdakı kimi aparılır. Praktikada ən böyük həcmli fayllarla işləyərkən açarların (indekslərin) təşkili üçün ən çox B – ağacdan istifadə olunur. B ağacda axtarış nizamlanmış və binar ağacdakı kimi aparılır.

Şəkil 4.9. B ağaclar


Trie ağaclar

Trie(sınaq). Bu ağaclardan simvol tipli açarların təşkili üçün və həmçinin maşın lüğətlərinin təşkili üçün istifadə edilir. Burada mövqeli kodlaşdırma prinsipindən istifadə olunur. Bu o deməkdir ki, ağacin hər bir təpəsi əlifbadakı hərflərin sayı qədər mövqelərə ayrılır. Hər mövqe bir hərfə uyğun götürülür. Hərf aşkar şəkildə təpədə yazılmır:

Şəkil 4.10. Trie ağaclar

Burada verilmiş ağacın axtarışı belə aparılır. 1-ci səviyyədə (baş təpədə) 1-ci hərfə uyğun mövqe təyin olunur. Həmin mövqedəki göstəricisi 2-ci hərfə uyğun mövqe təyin olunur. Bu proses açarın sonuncu hərfinə qədər davam edirilir. Ola bilsin ki, axtarışın açarı ağacda olmasın. Bu halda P_y yerinə Ø işarəsi durur.