- İkili ağacı preorder, inorder, postorder və səviyyə-səviyyə dolaşmaq
- İkili axtarış ağacında axtarış, əlavə və silməni yerinə yetirmək və O(h) mürəkkəbliyini izah etmək
- Yığında əlavə və minimumun çıxarılmasını massiv üzərində izləmək
Kompüterindəki qovluqlar, ailə şəcərəsi, veb-səhifənin HTML elementləri, kompilyatorun proqramdan qurduğu sintaksis ağacı — hamısı ağac strukturudur. Xəstəxananın təcili yardım şöbəsində isə xəstələr gəlmə sırası ilə yox, vəziyyətin ağırlığına görə qəbul olunur: bu, ağac üzərində qurulan prioritet növbəsidir. Bu dərsdə ağacların riyazi xassələrini və iki ən vacib növünü — ikili axtarış ağacını və yığını öyrənəcəyik.
İkili ağaclar və onların dolaşılması
Hər düyünün ən çoxu iki övladı (sol və sağ) olan ağac. Yuxarıdakı düyün kök, övladı olmayan düyün yarpaq adlanır. Düyünün dərinliyi kökdən ona qədər olan tillərin sayı, ağacın hündürlüyü h isə ən böyük dərinlikdir.
- ndüyünlərin sayı
- hağacın hündürlüyü (tillərlə)
d dərinliyində ən çoxu 2ᵈ düyün ola bilər: 1 + 2 + 4 + … + 2ʰ = 2ʰ⁺¹ − 1. Deməli, n düyünlü ikili ağacın hündürlüyü log₂ n-dən kiçik ola bilməz, amma n − 1-ə qədər böyük ola bilər.
50
/ \
30 70
/ \ / \
20 40 60 80
/
35| Dolaşma | Qayda | Nümunə ağac üçün nəticə | Harada lazımdır |
|---|---|---|---|
| Preorder | kök, sol, sağ | 50 30 20 40 35 70 60 80 | ağacın surətini çıxarmaq |
| Inorder | sol, kök, sağ | 20 30 35 40 50 60 70 80 | açarları artan sıra ilə almaq |
| Postorder | sol, sağ, kök | 20 35 40 30 60 80 70 50 | silmə, qovluğun ölçüsünü hesablamaq |
| Səviyyə-səviyyə | növbə ilə, yuxarıdan aşağı | 50 30 70 20 40 60 80 35 | ən qısa yol, səviyyələrə görə çap |
İkili axtarış ağacı (BST)
İkili axtarış ağacında hər düyün üçün sol alt ağacdakı bütün açarlar ondan kiçik, sağ alt ağacdakılar isə böyükdür. Axtarış kökdən başlayır: açar kiçikdirsə sola, böyükdürsə sağa gedirik — ikili axtarışın ağac variantı. Əlavə etmə eyni yolla boş yeri tapır. Hər iki əməliyyat O(h) vaxt aparır.
Nümunə ağacdan 30-u sil. Silmədən sonra ağacın inorder dolaşması necə olacaq?
Həllini göstərHəllini gizlət
30-un iki övladı var (20 və 40). Sağ alt ağac: 40 → 35. Ən kiçiyi 35-dir (sola gedə bildikcə gedirik).
30-un yerinə 35 yazılır, 35 isə köhnə yerindən silinir (o, yarpaqdır).
Yeni ağac: 50 → (35 → 20, 40), (70 → 60, 80).
Inorder: 20 35 40 50 60 70 80 — hələ də artan sıradadır, BST xassəsi qorunub.
class Node:
def __init__(self, key):
self.key, self.left, self.right = key, None, None
def insert(root, key):
if root is None:
return Node(key)
if key < root.key:
root.left = insert(root.left, key)
else:
root.right = insert(root.right, key)
return root
def inorder(t):
return inorder(t.left) + [t.key] + inorder(t.right) if t else []
def preorder(t):
return [t.key] + preorder(t.left) + preorder(t.right) if t else []
def height(t):
return -1 if t is None else 1 + max(height(t.left), height(t.right))
root = chain = None
for k in [50, 30, 70, 20, 40, 60, 80, 35]:
root = insert(root, k)
for k in range(1, 9):
chain = insert(chain, k)
print('inorder: ', inorder(root))
print('preorder:', preorder(root))
print('height:', height(root), '| sorted input height:', height(chain))▸ Gözlənilən nəticə
inorder: [20, 30, 35, 40, 50, 60, 70, 80] preorder: [50, 30, 20, 40, 35, 70, 60, 80] height: 3 | sorted input height: 7
Çıxış yolu balanslı ağaclardır: onlar hər əlavə və silmədən sonra fırlatmalarla (rotation) hündürlüyü O(log n) saxlayır. AVL ağacında hər düyünün sol və sağ alt ağaclarının hündürlükləri ən çoxu 1 fərqlənir (h < 1,44 log₂ n); qırmızı-qara ağacda h ≤ 2 log₂(n + 1). Java TreeMap və C++ std::map qırmızı-qara ağacdır, verilənlər bazalarının indeksləri isə hər düyündə yüzlərlə açar saxlayan B-ağaclarıdır.
Yığınlar və prioritet növbəsi
Tam ikili ağac (bütün səviyyələr doludur, sonuncu soldan sağa doldurulur) və hər düyün öz övladlarından kiçik və ya bərabərdir. Deməli, minimum həmişə kökdədir. Ağac göstəricisiz, sadəcə massivdə saxlanır.
- idüyünün massivdəki indeksi (0-dan)
Ağac səviyyə-səviyyə massivə yazılır; tam ağac olduğu üçün boşluq qalmır və hündürlük ⌊log₂ n⌋-dir.
Min-yığın: [3, 5, 8, 10, 7]. a) 2-ni əlavə et. b) Sonra minimumu çıxar. Hər addımda massivi yaz.
Həllini göstərHəllini gizlət
parent(5) = 2, orada 8 > 2 → dəyiş → [3, 5, 2, 10, 7, 8].
parent(2) = 0, orada 3 > 2 → dəyiş → [2, 5, 3, 10, 7, 8]. Kökə çatdıq.
b) Aşağı batırma (sift-down): kökdəki 2 götürülür, son element 8 kökə keçir → [8, 5, 3, 10, 7].
Övladlar: 5 (i = 1) və 3 (i = 2); kiçiyi 3 → dəyiş → [3, 5, 8, 10, 7].
i = 2-nin övladları yoxdur (5 və 6 indeksləri massivdən kənardadır) → [3, 5, 8, 10, 7], çıxarılan 2.
Hər iki əməliyyat ən çoxu h = ⌊log₂ n⌋ dəyişmə edir → O(log n).
import heapq
heap = [3, 5, 8, 10, 7]
heapq.heappush(heap, 2)
print(heap)
print(heapq.heappop(heap), heap)
patients = []
for urgency, name in [(3, 'Aysel'), (1, 'Murad'), (2, 'Leyla'), (1, 'Elvin')]:
heapq.heappush(patients, (urgency, name))
while patients:
print(heapq.heappop(patients))
def heap_sort(a):
h = a[:]
heapq.heapify(h)
return [heapq.heappop(h) for _ in range(len(h))]
print(heap_sort([9, 4, 7, 1, 8, 2]))▸ Gözlənilən nəticə
[2, 5, 3, 10, 7, 8] 2 [3, 5, 8, 10, 7] (1, 'Elvin') (1, 'Murad') (2, 'Leyla') (3, 'Aysel') [1, 2, 4, 7, 8, 9]
heapq modulu adi list üzərində min-yığındır: nəticə əl ilə izləməmizlə üst-üstə düşür. Xəstələr (təcililik, ad) cütü ilə saxlanır: kiçik rəqəm daha təcilidir, təcililik bərabər olanda ad müqayisə olunur. heapify + n dəfə heappop = yığınla çeşidləmə.- hdüyünün yarpaqlardan hündürlüyü
- n / 2ʰ⁺¹n / 2ʰ⁺¹hündürlüyü h olan düyünlərin sayı (təxminən)
heapify massivi aşağıdan yuxarı yığına çevirir: düyünlərin yarısı yarpaqdır (0 iş), dörddə biri 1 addım batır və s. ∑ h/2ʰ = 2 olduğundan cəm O(n)-dir, O(n log n) yox. Yığınla çeşidləmə isə n çıxarma ilə O(n log n) edir.
| Əməliyyat | Balanslı BST | Balanssız BST (ən pis) | İkili yığın |
|---|---|---|---|
| istənilən açarın axtarışı | O(log n) | O(n) | O(n) |
| əlavə | O(log n) | O(n) | O(log n) |
| minimumu görmək | O(log n) | O(n) | O(1) |
| minimumu çıxarmaq | O(log n) | O(n) | O(log n) |
| n elementdən qurmaq | O(n log n) | O(n²) | O(n) |
Əsas fikirlər
- n düyünlü ikili ağacın hündürlüyü ən azı ≈ log₂ n, ən çoxu n − 1-dir.
- Preorder, inorder, postorder kökün yerini göstərir; BST-nin inorder dolaşması açarları artan sıra ilə verir.
- BST əməliyyatları O(h)-dir; balanslı ağaclar (AVL, qırmızı-qara, B-ağacı) h = O(log n) saxlayır.
- Yığın massivdə saxlanan tam ağacdır: övladlar 2i + 1 və 2i + 2; əlavə və minimumun çıxarılması O(log n), qurma O(n).
- Prioritet növbəsi yığınla qurulur; yığınla çeşidləmə O(n log n), yerində, amma stabil deyil.
Özünü yoxla
10 sual. Hər düzgün cavab XP qazandırır.