Q: BST-nin pis halı nədir və praktikada bundan necə qaçınırsan?

Pis halı bir cümlə ilə de, sonra ONU REAL ET — bu sualın bütün dəyəri praktik nümunədədir: "Pis hal sıralı və ya demək olar sıralı input-dur. Hər yeni dəyər əvvəlkindən böyük olduğu üçün həmişə sağ budağa düşür və ağac əlaqəli siyahıya çevrilir: h = n, bütün əməliyyatlar O(n)." Real nümunələr ver: avtoinkrement ID-lər, timestamp-lar, artıq sıralanmış CSV və ya DB export-u. Vurğula ki, bu, ekzotik hal deyil — əksinə, ən təbii input formalarından biridir. Məhz buna görə adi BST istehsal kodunda nadir hallarda əl ilə yazılır. Sonra həlləri prioritetlə sadala: Hazır özü-balanslaşan struktur işlətmək — Kotlin/Java-da TreeMap (red-black tree), Dart-da SplayTreeMap, C++-da std::map. Bu, praktikada birinci cavabdır. AVL və ya Red-Black ağacı — rotasiyalarla h = O(log n) zəmanətini saxlayır. Özün implementasiya etmək lazımdırsa bu. Input-u qarışdırmaq — təsadüfi əlavə sırası gözlənilən hündürlüyü O(log n) edir. Sadədir, amma zəmanət deyil, yalnız ehtimal. Sıralı massiv + binary search — data statikdirsə (nadir dəyişirsə) bu, ağacdan da sadə və cache üçün daha sərfəlidir. Bağlayıcı cümlə mühəndis yetkinliyi göstərir: "Praktikada mən adi BST yazmıram — ya standart kitabxananın sıralı map-ını götürürəm, ya da data statikdirsə sıralı massivlə binary search edirəm. Əl ilə BST yazmaq yalnız müsahibə tapşırığıdır."

Q: BST ilə hash map arasında necə seçim edirsən?

Cavabı bir cümlə ilə çərçivəyə al: "Sual sürət deyil, sıra sualıdır." Hash map seçirəm əgər yalnız açar üzrə axtarış, əlavə və silmə lazımdırsa: orta halda O(1) — balanslaşdırılmış ağacın O(log n)-indən sürətlidir. Bu, halların böyük əksəriyyətidir və mənim default seçimimdir. Ağac (TreeMap / SplayTreeMap) seçirəm əgər sıra tələb olunursa: Açarları sıralı iterasiya etmək — hash-də əvvəlcə sıralamaq lazımdır, O(n log n). Diapazon sorğuları: [a, b] aralığındakı bütün açarlar — ağacda O(log n + k), hash-də O(n). Floor/ceiling: "k-dan kiçik ən böyük açar" — hash-də ümumiyyətlə mümkün deyil. Min/max açar — ağacda O(log n), hash-də O(n). Pis hal zəmanəti lazımdırsa: ağac O(log n) zəmanət verir, hash isə yalnız orta halda O(1)-dir. Hər ikisinin trade-off-unu bir cümlə ilə yekunlaşdır: "Hash sürət üçün sıranı qurban verir; ağac sıranı saxlamaq üçün bir az sürət verir." Praktik nümunə cavabı yaddaqalan edir: "İstifadəçi sessiyalarını id-yə görə saxlayıramsa hash map. Amma 'son 24 saatda yaradılmış bütün sessiyalar' sorğusu lazımdırsa, timestamp açarlı sıralı map — çünki bu, diapazon sorğusudur."

Question 1

Binary Search Tree nədir və hansı əməliyyatları hansı mürəkkəbliklə dəstəkləyir?

Accepted Answer

Tərifi dəqiq ver, çünki dəqiqlik burada yoxlanılır: "BST elə binary tree-dir ki, hər node üçün sol ALT-AĞACDAKI bütün dəyərlər node-dan kiçik, sağ ALT-AĞACDAKI bütün dəyərlər böyükdür. Şərt yalnız birbaşa övladlara yox, bütün alt-ağaca aiddir." Sonra invariantın nə qazandırdığını izah et: "Hər müqayisədə axtarış sahəsinin yarısını atıram, ona görə axtarış, əlavə və silmə O(h)-dır — h ağacın hündürlüyüdür." Burada ən vacib nüansı özün gətir: "O(h) yalnız balanslıdırsa O(log n) deməkdir. Adi BST özünü balanslaşdırmır, ona görə pis halda — məsələn sıralı input-da — h = n olur və hər əməliyyat O(n)-ə enir." Sonda BST-nin varlıq səbəbini de, çünki müsahib çox vaxt "niyə hash map yox?" ilə davam edir: "Hash map tək açar axtarışında daha sürətlidir, amma sıra saxlamır. BST sıralı iterasiya, diapazon sorğuları və floor/ceiling əməliyyatları verir — bunlar hash-də mümkün deyil."

Question 2

BST-də iki övladı olan node-u necə silirsən?

Accepted Answer

Əvvəl üç halı say ki, müsahib strukturu görsün: "Silmənin üç halı var — 0 övlad, 1 övlad, 2 övlad. İlk ikisi sadədir: leaf-i sadəcə ayırıram, tək övladlı node-u isə övladı ilə əvəzləyirəm." Sonra əsl cavabı ver: "İki övladlı node-u fiziki silmirəm. Onun inorder successor-unu tapıram — sağ alt-ağacdakı ən kiçik dəyəri, yəni sağa bir addım gedib sonra sola son həddə qədər. Node-un dəyərini successor-un dəyəri ilə əvəzləyirəm, sonra successor-u sağ alt-ağacdan silirəm." İki əsaslandırmanı mütləq əlavə et — güclü cavabı zəifdən ayıran budur: Niyə successor? Çünki o, node-dan böyük olan ən kiçik dəyərdir. Onu həmin yerə qoysam, sol alt-ağacdakı hər şey ondan kiçik, sağ alt-ağacdakı hər şey ondan böyük qalır — invariant pozulmur. Niyə rekursiya dərinləşmir? Çünki successor sağ alt-ağacın ən kiçiyidir, deməli sol övladı yoxdur. Onu silmək mütləq 0 və ya 1 övladlı sadə haldır. Simmetrik alternativi də qeyd et: inorder predecessor (sol alt-ağacdakı ən böyük) da eyni dərəcədə düzgündür. Bəzi implementasiyalar balansı qorumaq üçün növbə ilə birini, sonra o birini seçir. Mürəkkəblik: O(h) — successor-u tapmaq üçün ən çoxu bir dəfə ağacın hündürlüyü qədər aşağı düşürsən.

Question 3

Verilmiş binary tree-nin doğrudan BST olduğunu necə yoxlayarsan?

Accepted Answer

Bu sual bilərəkdən tələ qurur, ona görə əvvəl SƏHV həlli adlandır — bunu özün etsən, çox güclü təsir bağışlayır: "Sadəlövh yanaşma hər node üçün left.value < node.value < right.value yoxlamaqdır. Bu SƏHVDİR, çünki invariant bütün alt-ağaca aiddir. Məsələn root 10, sol övlad 5, amma həmin 5-in sağ övladı 20 olsa, lokal yoxlama keçir, halbuki 20 root-un sol alt-ağacındadır və 10-dan böyükdür — bu, BST deyil." Sonra iki düzgün həlli ver: 1. Diapazon ötürmək (min, max): hər node-a icazə verilən interval ötürülür. Root üçün (−∞, +∞); sola gedəndə max node-un dəyərinə, sağa gedəndə min node-un dəyərinə dəyişir. Node bu intervalın kənarındadırsa, ağac BST deyil. Vaxt O(n), yaddaş O(h). 2. Inorder traversal: BST-nin inorder çıxışı ciddi artan olmalıdır. Bir keçiddə gedib yalnız əvvəlki dəyəri saxlayırsan; cari dəyər əvvəlkindən böyük deyilsə, false. Bu variant daha yığcamdır və bütün massivi saxlamağa ehtiyac yoxdur. Sərhəd hallarını qeyd et — burada çox namizəd büdrəyir: təkrarlanan dəyərlərə icazə verilirmi (invariantın "ciddi kiçik" yoxsa "kiçik və ya bərabər" olması); Int.MIN_VALUE/Int.MAX_VALUE dəyərləri sərhəd kimi istifadə edilirsə, həmin dəyər ağacda varsa yoxlama səhv nəticə verir — ona görə nullable sərhədlər daha təhlükəsizdir.

Question 4

BST-nin pis halı nədir və praktikada bundan necə qaçınırsan?

Accepted Answer

Pis halı bir cümlə ilə de, sonra ONU REAL ET — bu sualın bütün dəyəri praktik nümunədədir: "Pis hal sıralı və ya demək olar sıralı input-dur. Hər yeni dəyər əvvəlkindən böyük olduğu üçün həmişə sağ budağa düşür və ağac əlaqəli siyahıya çevrilir: h = n, bütün əməliyyatlar O(n)." Real nümunələr ver: avtoinkrement ID-lər, timestamp-lar, artıq sıralanmış CSV və ya DB export-u. Vurğula ki, bu, ekzotik hal deyil — əksinə, ən təbii input formalarından biridir. Məhz buna görə adi BST istehsal kodunda nadir hallarda əl ilə yazılır. Sonra həlləri prioritetlə sadala: Hazır özü-balanslaşan struktur işlətmək — Kotlin/Java-da TreeMap (red-black tree), Dart-da SplayTreeMap, C++-da std::map. Bu, praktikada birinci cavabdır. AVL və ya Red-Black ağacı — rotasiyalarla h = O(log n) zəmanətini saxlayır. Özün implementasiya etmək lazımdırsa bu. Input-u qarışdırmaq — təsadüfi əlavə sırası gözlənilən hündürlüyü O(log n) edir. Sadədir, amma zəmanət deyil, yalnız ehtimal. Sıralı massiv + binary search — data statikdirsə (nadir dəyişirsə) bu, ağacdan da sadə və cache üçün daha sərfəlidir. Bağlayıcı cümlə mühəndis yetkinliyi göstərir: "Praktikada mən adi BST yazmıram — ya standart kitabxananın sıralı map-ını götürürəm, ya da data statikdirsə sıralı massivlə binary search edirəm. Əl ilə BST yazmaq yalnız müsahibə tapşırığıdır."

Question 5

BST ilə hash map arasında necə seçim edirsən?

Accepted Answer

Cavabı bir cümlə ilə çərçivəyə al: "Sual sürət deyil, sıra sualıdır." Hash map seçirəm əgər yalnız açar üzrə axtarış, əlavə və silmə lazımdırsa: orta halda O(1) — balanslaşdırılmış ağacın O(log n)-indən sürətlidir. Bu, halların böyük əksəriyyətidir və mənim default seçimimdir. Ağac (TreeMap / SplayTreeMap) seçirəm əgər sıra tələb olunursa: Açarları sıralı iterasiya etmək — hash-də əvvəlcə sıralamaq lazımdır, O(n log n). Diapazon sorğuları: [a, b] aralığındakı bütün açarlar — ağacda O(log n + k), hash-də O(n). Floor/ceiling: "k-dan kiçik ən böyük açar" — hash-də ümumiyyətlə mümkün deyil. Min/max açar — ağacda O(log n), hash-də O(n). Pis hal zəmanəti lazımdırsa: ağac O(log n) zəmanət verir, hash isə yalnız orta halda O(1)-dir. Hər ikisinin trade-off-unu bir cümlə ilə yekunlaşdır: "Hash sürət üçün sıranı qurban verir; ağac sıranı saxlamaq üçün bir az sürət verir." Praktik nümunə cavabı yaddaqalan edir: "İstifadəçi sessiyalarını id-yə görə saxlayıramsa hash map. Amma 'son 24 saatda yaradılmış bütün sessiyalar' sorğusu lazımdırsa, timestamp açarlı sıralı map — çünki bu, diapazon sorğusudur."

Əməliyyat	Balanslaşdırılmış	Deqradasiya olmuş	Sıralı massiv	Hash map
Axtarış	O(log n)	O(n)	O(log n)	O(1) orta
Əlavə etmə	O(log n)	O(n)	O(n)	O(1) orta
Silmə	O(log n)	O(n)	O(n)	O(1) orta
Sıralı çıxış	O(n) — inorder	O(n)	O(n) — hazırdır	O(n log n) — sıralamaq lazımdır
Diapazon sorğusu	O(log n + k)	O(n)	O(log n + k)	O(n)

Binary Search Tree

📚 Mənbələr və sənədlər