Ağac əsasları və traversal
Ağac — dövrü olmayan, iyerarxik struktur: hər node-un bir valideyni (root istisna olmaqla) və istənilən sayda övladı olur.
Terminologiya müsahibədə birbaşa soruşulur, ona görə dəqiq bil:
- Root — valideyni olmayan yeganə node.
- Leaf — övladı olmayan node.
- Parent / child / sibling — valideyn, övlad, eyni valideynin övladları.
- Depth (dərinlik) — root-dan həmin node-a qədər olan yolun uzunluğu. Root-un depth-i 0-dır.
- Height (hündürlük) — node-dan ən uzaq leaf-ə qədər olan yolun uzunluğu. Ağacın height-i root-un height-idir. Boş ağacın height-i adətən −1 sayılır.
- Degree — node-un övladlarının sayı.
- Subtree — istənilən node və onun bütün nəsilləri.
Depth və height-i qarışdırmaq ən çox rast gəlinən səhvdir: depth yuxarıdan aşağı, height aşağıdan yuxarı ölçülür.
Binary tree — hər node-un ən çox iki övladı (left, right) olan ağac. N-ary tree — övladlar siyahıda saxlanılır (children: Node[]); DOM, fayl sistemi, UI widget ağacı belədir.
Traversal — ağacın bütün node-larını bir dəfə gəzmək. İki ailə var.
DFS (dərinliyə görə) — bir budağı sona qədər gedib sonra geri qayıdır. Node-un nə vaxt "emal olunmasına" görə üç variant:
- Preorder (node → left → right): ağacı kopyalamaq, serializasiya, iyerarxiyanı yuxarıdan aşağı çap etmək.
- Inorder (left → node → right): BST-də sıralı ardıcıllıq verir — bu, ən çox soruşulan faktdır.
- Postorder (left → right → node): övladlar valideyndən əvvəl emal olunur; silmə, qovluq ölçüsü hesablama, ifadə ağacının qiymətləndirilməsi.
BFS (enə görə, level-order) — ağacı səviyyə-səviyyə gəzir. Növbə (queue) tələb edir. "Ən qısa yol", "səviyyələr üzrə qruplaşdır", "ən yaxın uyğun node" tipli suallar BFS işidir.
| Traversal | Sıra | Struktur | Yaddaş | Tipik istifadə |
|---|---|---|---|---|
| Preorder | node → left → right | Stack (və ya rekursiya) | O(h) | Kopyalama, serializasiya |
| Inorder | left → node → right | Stack (və ya rekursiya) | O(h) | BST-də sıralı çıxış |
| Postorder | left → right → node | Stack (və ya rekursiya) | O(h) | Silmə, aqreqasiya (qovluq ölçüsü) |
| BFS / level-order | Səviyyə-səviyyə | Queue | O(w) — ən geniş səviyyə | Ən qısa yol, səviyyələr üzrə qruplaşdırma |
Mürəkkəblik. Bütün traversal-lar hər node-a bir dəfə baş çəkdiyi üçün vaxt həmişə O(n)-dir. Fərq yaddaşdadır:
- DFS yaddaşı çağırış stack-inin dərinliyi ilə ölçülür: O(h), burada
hağacın hündürlüyüdür. Balanslaşdırılmış ağacdah ≈ log n, deməli O(log n); deqradasiya olmuş (zəncirvari) ağacda isəh = nvə yaddaş O(n) olur. - BFS yaddaşı ən geniş səviyyənin ölçüsü ilə ölçülür: O(w). Tam binary tree-də son səviyyə bütün node-ların təxminən yarısını saxlayır, yəni O(n).
Praktik nəticə: dar və dərin ağacda BFS, geniş və dayaz ağacda DFS yaddaşa daha qənaətlidir.
Rekursiv vs iterativ. Rekursiya qısa və oxunaqlıdır, amma çağırış stack-i məhduddur — çox dərin ağacda (məsələn 100 min node-luq zəncir) RangeError: Maximum call stack size exceeded və ya StackOverflowError alırsan. İterativ variant eyni işi öz stack massivi ilə görür və bu limitə çatmır: heap yaddaşı stack-dən qat-qat böyükdür. İstehsal kodunda dərinliyi idarə olunmayan ağac gəzirsənsə (istifadəçi datası, JSON, DOM), iterativ variant daha təhlükəsizdir.
İnterview ipucu. Bu mövzuda ən çox verilən sual: "DFS və BFS arasında necə seçim edirsən?" Zəif cavab "DFS rekursiv, BFS queue ilədir" — bu, mexanikanı təsvir edir, seçimi yox.
Güclü cavab tələbdən çıxış edir: "Ən qısa yol və ya ən yaxın uyğun node lazımdırsa BFS, çünki o, səviyyələri sıra ilə gəzir və ilk tapdığı ən yaxındır. Bütün yolları gəzmək, iyerarxiyanı yığmaq və ya alt-ağac üzrə aqreqasiya lazımdırsa DFS. Yaddaş baxımından isə dərin və dar ağacda BFS, geniş ağacda DFS sərfəlidir."
İkinci klassik sual: "Inorder traversal nə verir?" — BST-də sıralı ardıcıllıq. Bunu bilməmək BST suallarında dərhal görünür.
Ən çox buraxılan detal: rekursiyanın stack limitini qeyd etmək. "Rekursiv yazardım, amma ağacın dərinliyi idarə olunmursa iterativ variantı seçərdim ki, stack overflow olmasın" — bu bir cümlə səni junior-dan ayırır.