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

Ağacvari strukturlar

Kompüter elmlərində verilənləri saxlamaq üçün istifadə olunan üsullardan biri də ağaclardır. Bu strukturlar da qeyri - xətti dinamik strukturlara aiddir. Bu strukturlar açarlı axtarışda açarın səmərəli təşkili və axtarışı üçün istifadə olunur. Açar hər bir yazının ( söhbət cədvəldən və fayldan gedir ) bir mənalı təyin edən əlamətidir. Açarları yazılarla birlikdə və ya onlardan ayrıca saxlamaq olar. Açarın ən yaxşı təsvir üsulu indeks hesab olunur. İndekslə açarın axtarışı üçün ağacvari strukturlardan geniş istifadə olunur.

Ağacvari strukturun məntiqi forması təbiətdə mövcud olan ağacı xatırladır. Burada ağac başayaq təsvir olunur.
Proqramlaşdırmada ağacvari struktur aşağıdakı xassələrlə təyin olunur :
1. Ağacın kökü yuxarıda, budaq və yarpaqları isə aşağıda təsvir olunur.
2. Ağac təpə və budaqlardan ibarətdir.
3. Ağacın təpələri içərisində eləsi var ki, ona budaq daxil olmur, ondan yalnız budaqlar xaric olur. Buna ağacın kökü və ya baş təpəsi deyilir.
4. Təpələr içərisində elələri var ki, onlardan heç bir budaq çıxmır, onlara yalnız budaqlar daxil olur. Belə təpələrə ağacın yarpaqları deyilir.
5. Ağacın hər bir təpəsinə baş təpədən başlayan yalnız bir yol var. Təpəyə başqa yolla müraciət mümkün deyil.

Əgər bir qarafik bağlı deyilsə və dövrü olmayandırsa onda belə qrafikə ağac deyilir. Bu strukturda verilənlər ağac formasında (kök, gövdə, yarpaq) saxlanılır.

Məsələn aşağıdaki şəkildə 7 düyümdən (node) ibarət olan və yarpaqlarında (leaf) 4 düyüm olan bir ağac strukturu göstərilmişdir.



Bu ağacın dərinliyi (depth) 2-yə bərabərdir və hər səviyyənin (level) nömrəsi yanında verilmişdir. Ağacların bir ədəd başlanğıc düyümü olur ki buna da kök (root) deyilir.
Ağacların xüsusi bir forması olan ikili ağaclarda hər düyümün maksimum iki uşağı ola bilər. Bir düyümdə daha az uşağın olması (0 və ya 1) ağacın strukturuna xələl yetirmir. Yarpaqları çıxsaq qalan bütün iki uşağı olarsa və yarpaqlar eyni dərinliyə sahib olduqda belə ağaca balanslı (balanced) ağac deyilir. Yuxarıdaki şəkildə təsvir olunan ağac balanslaşdırılmış bir ağacdır.
Həmin ağacı fərqli sıralarda yenidən qura bilərik. Məsələn aşağıda təsvir olunan ağac da yuxarıdaki ağac ilə eyni verilənləri saxlayır:

Bu ağacın ilk şəkildəki ağacdan fərqli cəhəti balanslaşdırılmamış olması və xüsusi olaraq hər düyümün bir uşağının olmasıdır. Əgər tərifə fikir versək bu ağacında ikili ağac olaraq qəbul edilməli olduğunu görərik.
İkili ağacların xüsusi bir halı olan ikili axtarış ağaclarındakı (Binary Search Tree) düyümlərdə saxlanılan verilənlərin arasında böyükdür-kiçikdir əlaqəsi olur. Məsələn tam ədədlərdən (integer) ibarət olan verilənlər saxlanılırsa bu verilənlərin aralarında böyükdür-kiçikdir əlaqəsi olmalıdır.
İkili axtarış ağacı hər düyümün solundaki qoldan çata biləcəyimiz bütün verilənlərin həmin düyümün dəyərindən kiçik, sağ qolundan çata biləcəyimiz bütün verilənlərin isə həmin düyümün dəyərindən böyük olmasını təmin etməlidir.
Misal üçün aşağıda bir ikili axtarış ağacı təsvir olunmuşdur. Bu ağaca diqqətlə fikir versək kökün solunda olan bütün ədədlərin kökdən kiçik, sağında duran bütün ədədlərin isə kökdən böyük olduğunu görərik:

İkili axtarış ağacları olduqca populyardır və qanunauyğunluq gözləndiyindən bu ağaclar üzərində əməliyyatlar aparmaq olar. Qeyd edək ki, hər hansı bir əməliyyat aparıldıqdan sonra ikili axtarış ağacının strukturu pozulmamış olaraq qalmalıdır.

Ağacın məntiqi strukturu aşağıdakı kimidir:

Şəkil 4.3. Ağacın məntiqi strukturu

Ağacın hər bir təpəsi bir açar üçün nəzərdə tutulur. Yəni hər bir təpədə bir açar saxlanılır. A,B, C, D, E, F – açarlardır.

Şəkil 4.4. Ağacın fiziki strukturu

P_y – yazının göstəricisi, yəni baxılan açara malik olan yazının saxlandığı yerin (o əməli və ya xarici yaddaşda ola bilər) ünvanıdır.

Ø – göstəricinin olmamasıdır.
Praktikada ən çox binar ( ikilik ), nizamlanmış və balanslaşmış ağaclardan istifadə edilir.
Biz də burada C dilindən istifadə edərək ikili axtarış ağacının yaradılması, onun üzərində axtarış, əlavə etmə və silmə əməliyyatlarının yerinə yetirilməsi məsələlərinə nəzər yetirəcəyik.