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



Yüklə 0,95 Mb.
səhifə17/44
tarix29.04.2023
ölçüsü0,95 Mb.
#104595
növüMühazirə
1   ...   13   14   15   16   17   18   19   20   ...   44
C fakepathmu hazir struktur

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 Py yerinə Ø işarəsi durur.





Yüklə 0,95 Mb.

Dostları ilə paylaş:
1   ...   13   14   15   16   17   18   19   20   ...   44




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin