İkitərəfli axtarış ağacları

3.1 İkilik axtarış ağacının (BST) tərifi

İkilik axtarış ağacı (BST) — bu, aşağıdakı xüsusiyyətlərə malik olan bir ikilik ağacdır:

• Hər bir node üçün, onun sol alt ağacı yalnız bu nodun açarından kiçik olan açarlara malik nodlardan ibarətdir.
• Hər bir node üçün, onun sağ alt ağacı yalnız bu nodun açarından böyük olan açarlara malik nodlardan ibarətdir.
• Hər bir nodun hər iki alt ağacı da ikilik axtarış ağacıdır.

BST nümunəsi:

BST – Binary Search Tree-in qısaltmasıdır – tam mənası ilə "İkilik axtarış ağacı". Əslində bu, dataları "ağac" formasında təşkil etməkdir, hansı ki, çox sürətli axtarış etməyə imkan verir. Ağacın strukturu – əslində elementlərin gizli/ustalıqla sıralanmasıdır.

Mərkəzləşdirilmiş keçid (in-order traversal)

Keçid tapşırığı — xüsusi bir qaydada node-ların siyahısını (yaxud node-lardan dataları, terminologiya məsələsidir və praktikada əhəmiyyətlidir) formalaşdırmaqdır. Mərkəzləşdirilmiş (simmetrik) keçid – belə bir keçiddir ki, burada ağacın kökü sol və sağ alt ağacların müvafiq keçidlərinin nəticələri arasında yer tutur.

İkilik axtarış ağacının xüsusiyyəti ilə (bərabərsizliklər haqqında olan, nəzəriyyəyə bax) birlikdə bu o deməkdir ki, ikilik axtarış ağacının mərkəzləşdirilmiş keçidi bizə sıralanmış node-ların siyahısını formalaşdıracaq – əladır! Budur, əvvəllər müəyyən olunmuş ağacın keçidi necə görünəcək:

3.2 BST iş prinsipləri və xüsusiyyətləri

İş prinsipləri:

• Verilənlərin təşkili: BST məlumatları elə təşkil edir ki, effektiv axtarış, əlavə etmə və silmə əməliyyatlarını təmin etsin.
• Təkrarlanan struktura: BST-də hər bir node ağacın kökü kimi eyni qaydalara tabedir, bu da strukturu rekursiv edir.
• Balanslılıq: Optimal performansı təmin etmək üçün BST balanslı olmalıdır, yəni sol və sağ alt-ağacların hündürlüyü təxminən eyni olmalıdır.

BST-nin xüsusiyyətləri:

• Sifarişlilik: Hər hansı zaman ağacı "in-order" qaydasında keçmək olar (sol alt-ağac → cari node → sağ alt-ağac), bu da bütün elementləri sıralanmış qaydada əldə etməyə imkan verir.
• Əməliyyatların vaxtı:
  • Orta hesabla axtarış, əlavə etmə və silmə əməliyyatlarının icra olunma vaxtı O(log n) təşkil edir, burada n — node-lərin sayıdır.
  • Ən pis halda (əgər ağac balanssızdırsa) əməliyyatların icra olunma vaxtı O(n) ola bilər.
• Unikal açarlar: BST-dəki bütün açarlar unikal olmalıdır ki, sifarişliliyi qoruya bilsin.

3.3 Əsas əməliyyatlar

1. Əlavə etmə (Insertion):

İş prinsipi:

• Kök düyündən başlayırıq.
• Yeni düyünün açarını cari düyünün açarı ilə müqayisə edirik.
• Əgər yeni açar kiçikdirsə, sol alt ağaca keçirik, böyükdürsə sağ alt ağaca.
• Prosesi təkrarlayırıq, ta ki, yeni düyün üçün uyğun yer tapılana qədər (ya sol, ya da sağ övlad yoxdur).

Alqoritm:

1. Əgər ağac boşdursa, yeni düyün kök düyünü olur.
2. Əks halda, doğru yeri tapmaq üçün rekursiv şəkildə hərəkət edib yeni düyünü əlavə edirik.

2. Silmə (Deletion):

İş prinsipi:

• Silinməli düyünü tapın.
• Üç halda baxılır:
• Düyün yarpaqdır (övladı yoxdur): sadəcə düyünü silirik.
• Düyünün bir övladı var: düyünü onun övladı ilə əvəz edirik.
• Düyünün iki övladı var: sağ alt ağacdakı ən kiçik düyünü (və ya sol alt ağacdakı ən böyüyü) tapırıq, onun dəyərini silinən düyünə kopyalayırıq və sağ alt ağacdakı ən kiçik düyünü rekursiv şəkildə silirik.

Alqoritm:

1. Verilmiş açarla düyünü tapın.
2. Hala uyğun olaraq müvafiq silmə və düyünlərin yenidən yerləşməsini icra edin.

3. Axtarış (Search):

İş prinsipi:

• Kök düyündən başlayırıq.
• Axtarılan düyünün açarını cari düyünün açarı ilə müqayisə edirik.
• Əgər açar eynidirsə, düyünü qaytarırıq.
• Əgər açar kiçikdirsə, sol alt ağaca keçirik, böyükdürsə sağ alt ağaca.
• Prosesi təkrarlayırıq, ta ki, axtarılan açarla uyğun düyün tapılana qədər və ya ağacın sonuna çatılana qədər (bu halda düyün tapılmır).

Alqoritm:

1. Əgər ağac boşdursa və ya düyünün açarı axtarılan açarla eynidirsə, düyünü qaytarırıq.
2. Əgər axtarılan açar kiçikdirsə, sol alt ağacda rekursiv axtarış edirik.
3. Əgər axtarılan açar böyükdürsə, sağ alt ağacda rekursiv axtarış edirik.

3.4 BST istifadə etməklə həll olunan məsələlərə nümunələr

1. Dinamik çoxluqda elementin axtarışı

Rəqəmlər çoxluğunu dəstəkləmək lazımdır, ona yeni elementlər əlavə etmək, mövcud olanları silmək və verilmiş rəqəmin çoxluqda olub-olmadığını tez bir zamanda yoxlamaq lazımdır.

BST istifadə etməklə həll:

• Ağaca yeni elementlərin əlavə edilməsi.
• Mövcud elementlərin silinməsi.
• Ağacda elementlərin axtarışı.

İstifadə nümunəsi:

Sistemdə qeydiyyatdan keçmiş istifadəçilərin siyahısını dəstəkləmək, burada istifadəçilər əlavə edilə və silinə bilər, sistem isə tez bir zamanda yoxlamalıdır, istifadəçi qeydiyyatdan keçibmi.

2. Minimum və maksimum elementin tapılması

Verilənlər toplusunda minimum və maksimum dəyərləri tez bir zamanda tapmaq lazımdır.

BST istifadə etməklə həll:

• Minimum element ağacın ən sol node-da yerləşir.
• Maksimum element ağacın ən sağ node-da yerləşir.

İstifadə nümunəsi:

Səhmlərin qiymətlərini izləyən sistem dəstəklənir, burada cari anda minimum və maksimum qiyməti tez bir zamanda tapmaq lazımdır.

3. İfadənin balansının yoxlanması

Verilən riyazi ifadəyə görə, açılan və bağlanan mötərizələrin balansını yoxlamaq lazımdır.

BST istifadə etməklə həll:

Mötərizə balansının yoxlanmasının aralıq vəziyyətlərini saxlamaq üçün BST-dən istifadə edirik.

İstifadə nümunəsi:

Kodun parsinqi və kompilyasiyası, burada ifadələrdə mötərizələrin düzgün sıralanmasını yoxlamaq lazımdır.

4. Lüğət tərtibi

Sözü tapmaq üçün strukturu yaratmaq lazımdır, burada sözləri əlavə etmək, silmək və tez bir zamanda tapmaq mümkündür.

BST istifadə etməklə həll:

• Sözlər ağaca əlifba sırasıyla əlavə olunur.
• Tapılma açarlar əsasında həyata keçirilir.

İstifadə nümunəsi:

Mətnin avtomatik korrektəsi sistemi, burada sözləri tez tapmaq və düzəltmək lazımdır.