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

Binar ( ikilik ) ağac

Bu ağaclarda hər bir təpədən çıxan budaqların sayı ikidən çox ola bilməz. Formal şəkildə ikilik ağacı belə ifadə edirlər. ( T1, R, T2 ). Burada R – kök, T1 – sol yarım ağac, T2 – sağ yarım ağacdır.

Şəkil 4.5. Binar ağac
Göstərilən ağacvari strukturda açarların axtarışı çox vaxt aparır. Odur ki, səkildə onlardan praktikada istifadə olunmur. Praktikada əsas etibarilə nizamlanmış və balanslaşmış ağaclardan istifadə olunur.


Binar ağaclar üzərində sadə əməliyyatlar.
Əgər binar ağacın nd qovşağının göstəricisi p isə, onda info(p) funksiyası nd qovşağının məzmununu qaytarır. Left(p), right(p), father(p) və brother(p) funksiyaları müvafiq olaraq nd-nin qardaşının göstəricilərini qaytarır. Əgər nd sol oğul, sağ oğul, ata və ya qardaş qovşaqlarına malik deyilsə, onda bu funksiyalar boş göstərici qaytarır. Məntiqi left(p) və right(p) funksiyaları əgər nd müvafiq olaraq hər hansı qovşağın sol və ya sağ oğludursa həqiqi(true) qiyməti və əks halda yalan(false) qaytarır.


Binar ağacların təsvir olunması .
Cədvəl tip dəyişənlərin köməyi ilə binar ağacları Paskalda asanca reallaşdırmaq olar. Bunun üçün binar ağacın hər bir qovşağını aşağıdakı 4 elementin köməyi ilə təsvir edək.

• 
  İNFO – qovşağın məzmunu (qiyməti)
  
• 
  LEFT – qovşağın sol oğlu varsa-true qiyməti əks halda-false
  
• 
  RİGHT- qovşağın sağ oğlu varsa-true qiyməti əks halda false
  
• 
  FATHER- qovşaq ata varsa true qiyməti əks halda false
  

Onda müvafiq Paskal təsvir operatorları belə yazılacaq:
Nizamlanmış ağaclar

Axtarışı asanlaşdırmaq və sürətləndirmək üçün ağacı nizamlayırlar. Nizamlanma hər bir səviyyədə açarların qiymətinin soldan – sağa azalma va artma ardıcıllığı ilə yerləşdirilməsi ilə əldə edilir.

Şəkil 4.6. Nizamlanmış ağac


Nizamlanmış ikilik ağacda axtarış.
Axtarılan açar baş təpədəki açarla müqayisə olunur . Əgər cavab müsbətdirsə, onda yazı tapılır və axtarış bitir. Əgər bərabərlik yoxdursa, onda açarların kiçik və ya böyük olması yoxlanılır. Əgər axtarılan açar saxlanan açardan kiçikdirsə, onda sol əks halda sağ göstərici seçilir. Sonrakı səviyyədə axtarış davam etdirilir. Əgər uyğun göstərici yoxdursa, (Ø) onda axtarış dayandırılır və axtarılan açarın ağacda olmaması haqqında məlumat verilir. [5]

Şəkil 4.7. Nizamlanmış ağacin fiziki strukturu
Ağaca yeni yazının, yəni yazıya uyğun açarın daxil edilməsi uçun əvvəlcə onun yeri müəyyən edilir, sonra həmin yer ondan əvvəlki uyğun təpə ilə əlaqələndirilir.
Yazının ağacdan silinməsi ən ağır və xoşa gəlməz əməliyyat hesab olunur. Belə ki, bir çox halda bu əməliyyatın aparılması üçün ağacı yenidən qurmaq tələb olunur. Əgər silinən təpə ağacın yarpağıdırsa, bu əməliyyat nisbətən sadə yerinə yetirilir. Bu halda silinən təpəyə keçid verən təpədəki uyğun göstərici sıfırla (Ø) əvəz olunur.