Question 1

Ağacın balanslaşdırılması niyə lazımdır?

Accepted Answer

Problemdən başla, həlldən yox: "Adi BST özünü balanslaşdırmır — forması tamamilə əlavə sırasından asılıdır. Sıralı data gəlirsə, hər yeni element sağ budağa düşür və ağac əlaqəli siyahıya çevrilir: h = n, bütün əməliyyatlar O(n)." Sonra bunu real et: "Bu, ekzotik hal deyil. Avtoinkrement ID-lər, timestamp-lar, artıq sıralanmış export — real data tez-tez məhz belə gəlir." Rəqəmlə göstər, çünki rəqəm yadda qalır: "1 milyon element üçün fərq 20 müqayisə ilə 1 milyon müqayisə arasındadır." Sonra həlli bir cümlə ilə: "Özü-balanslaşan ağaclar — AVL, Red-Black — hər əlavə/silmədən sonra rotasiyalarla formanı düzəldir və h = O(log n) ZƏMANƏTİ verir. Rotasiya O(1)-dir və inorder sırasını dəyişmədiyi üçün BST invariantını pozmur." Bağlayıcı olaraq real dünyaya bağla: "Java/Kotlin TreeMap, C++ std::map məhz red-black tree-dir; verilənlər bazası indeksləri isə eyni ideyanın disk üçün variantı olan B-tree işlədir."

Question 2

Rotasiya nədir və o nə edir?

Accepted Answer

Rotasiyanı göstərici manipulyasiyası kimi yox, şəkil kimi izah et — müsahiblərin gözlədiyi budur. "Rotasiya alt-ağacın lokal yenidən qurulmasıdır. Tutaq ki, node sağa əyilib — sağ alt-ağac sol alt-ağacdan hündürdür. Sola rotasiya sağ övladı yuxarı qaldırıb köhnə valideyni onun sol övladı edir. Nəticədə hündür budaq bir səviyyə enir, qısa budaq bir səviyyə qalxır və ağac düzləşir." Sonra üç faktı say — bu üçü cavabı tam edir: İnorder sırası dəyişmir. Elementlərin nisbi sırası eyni qalır, ona görə BST invariantı avtomatik qorunur. Bu, rotasiyanın niyə təhlükəsiz olduğunun izahıdır. O(1)-dir. Cəmi bir neçə göstərici dəyişir; heç bir alt-ağac gəzilmir. Dörd hal var — LL, RR, LR, RL. LL və RR bir rotasiya ilə həll olunur; LR və RL iki ardıcıl rotasiya tələb edir (əvvəl övladı, sonra valideyni fırlatmaq). Mürəkkəbliyi yekunlaşdır: bir əlavədən sonra balans yoxlanışı root-a qədər qalxa bilər, yəni ən pisi O(log n) — deməli əlavənin ümumi qiyməti O(log n) olaraq qalır. Dəqiq kodu əzbər bilmədiyini demək zəiflik deyil: "Konkret göstərici ardıcıllığını yaddaşdan yazmıram, amma prinsipi və nə vaxt tətbiq olunduğunu izah edə bilərəm" — bu, tamamilə qəbul olunan cavabdır.

Question 3

AVL və Red-Black ağacını müqayisə et. Hansını nə vaxt seçərdin?

Accepted Answer

Fərqi balans şərtindən çıxar — bütün qalan fərqlər ondan doğur. "AVL sərt şərt qoyur: hər node üçün sol və sağ alt-ağacın hündürlük fərqi ən çox 1. Red-Black rəng qaydaları ilə daha boş bir şərt saxlayır — ən uzun yol ən qısadan ən çox iki dəfə uzun ola bilər." Sonra nəticələri sadala: "AVL daha sərt olduğu üçün ağac daha alçaq olur və axtarış bir az sürətlidir. Amma bu formanı saxlamaq daha çox rotasiya tələb edir, yəni əlavə və silmə bahalaşır. Red-Black əksinə: bir az hündür ağac, amma yazı əməliyyatları ucuz." Seçim qaydasını konkret ver: "Oxu çox, yazı az olan yüklərdə AVL; yazı və silmənin intensiv olduğu yüklərdə Red-Black. Hər ikisi eyni asimptotikanı verir — axtarış, əlavə, silmə O(log n) — fərq sabit əmsallardadır." Real istifadəni əlavə et, çünki bu, cavabı praktikaya bağlayır: "Praktikada Red-Black daha çox yayılıb — Java/Kotlin TreeMap və TreeSet, C++ std::map, Linux nüvəsinin planlayıcısı. Səbəbi odur ki, ümumi təyinatlı kolleksiyalarda yazı yükü də ciddi olur." Son və ən vacib cümlə: "Real layihədə mən bu seçimi çox nadir hallarda edirəm — standart kitabxananın hazır strukturunu götürürəm. Bu seçim yalnız öz strukturunu yazanda və ya çox spesifik performans profili olanda aktual olur."

Question 4

Səndən AVL ağacını implementasiya etməyi xahiş etsələr nə edərsən?

Accepted Answer

Bu, dürüstlük və özünüqiymətləndirmə sualıdır. Uydurmaq və yarımçıq rotasiya kodu yazmaq ən pis seçimdir — müsahib səhvi dərhal görür. Güclü cavabın strukturu belədir: 1. Sərhədi dürüst göstər: "Rotasiyaların dəqiq göstərici ardıcıllığını yaddaşdan yaza bilmərəm — bunu praktikada heç vaxt əl ilə yazmamışam." 2. Prinsipi izah et ki, anlayışın olduğu görünsün: "Amma alqoritmi bilirəm: adi BST əlavəsi edirəm, sonra dəyişmiş yol boyu yuxarı qalxıb hər node-un balans faktorunu — sol və sağ hündürlüyün fərqini — yenidən hesablayıram. |fərq| > 1 olan ilk node-da dörd haldan birini tanıyıram: LL, RR, LR, RL. LL və RR bir rotasiya, LR və RL iki ardıcıl rotasiya tələb edir." 3. Nəyi yaza biləcəyini təklif et: "İstəsəniz, sadə sağa rotasiyanı və balans faktorunun hesablanmasını yaza bilərəm." Bu, sualı bacardığın hissəyə yönləndirir. 4. Praktik seçimi göstər: "İstehsal kodunda mən bunu yazmıram — TreeMap, SplayTreeMap və ya std::map götürürəm. Öz implementasiyam sınaqdan keçmiş kitabxanadan yaxşı olmayacaq və silmə hallarında səhv etmək asandır." Bu cavab üç keyfiyyət göstərir: dürüstlük, mexanizmi başa düşmək və mühəndis mühakiməsi. Middle səviyyəli müsahibədə bu, mükəmməl cavabdır — çünki əsl gözlənti də elə budur.

Question 5

Verilənlər bazası indeksləri niyə AVL/Red-Black yox, B-tree istifadə edir?

Accepted Answer

Cavabın açarı yaddaş iyerarxiyasıdır — sırf asimptotikaya baxsan, sual cavabsız qalır, çünki hər ikisi O(log n)-dir. "Fərq ondadır ki, disk (və ya SSD) oxunuşu bloklarla aparılır — məsələn 4 KB və ya 8 KB. Bir baytı oxumaqla dörd kiloBaytı oxumaq təxminən eyni qiymətə başa gəlir. Deməli əsl xərc əməliyyat sayı yox, disk oxunuşlarının sayıdır." Sonra nəticəni çıxar: "Binary tree-də hər node bir açar saxlayır və hər səviyyə bir disk oxunuşu deməkdir. 1 milyon açar üçün h ≈ 20, yəni 20 disk oxunuşu. B-tree-də isə hər node yüzlərlə açar saxlayır — bir blok bütünlüklə oxunur. Nəticədə eyni 1 milyon açar üçün hündürlük 3-4 olur, yəni cəmi 3-4 disk oxunuşu. Fərq təxminən beş dəfədir." Əlavə səbəbləri say: B+tree-də bütün data leaf səviyyəsindədir və leaf-lər bir-birinə keçidlə bağlanıb, ona görə diapazon skanı (WHERE date BETWEEN ...) ardıcıl oxunuşa çevrilir — disk üçün ən sürətli nümunə. Node-lar blok ölçüsünə uyğun seçildiyi üçün yaddaş səhifələri də səmərəli işlənir. Ümumi prinsipi adlandır — bu, cavabı senior səviyyəsinə qaldırır: "Data strukturu seçimi yalnız asimptotikadan asılı deyil; yaddaş iyerarxiyası və giriş vahidinin ölçüsü çox vaxt daha həlledicidir. Eyni məntiqlə in-memory strukturlarda da cache lokallığı sabit əmsalları kəskin dəyişir."

Xüsusiyyət	AVL	Red-Black
Balans şərti	Hər node üçün sol və sağ hündürlük fərqi ən çox 1	Rəng qaydaları; ən uzun yol ən qısadan ən çox 2 dəfə uzundur
Nə qədər balanslı	Daha sərt — ağac daha alçaqdır	Daha boş — ağac bir az hündür ola bilər
Axtarış	Bir az sürətli (alçaq ağac)	Bir az yavaş
Əlavə / silmə	Daha çox rotasiya — daha bahalı	Daha az rotasiya — daha ucuz
Nə vaxt üstündür	Oxu çox, yazı az (read-heavy)	Yazı və silmə çox (write-heavy)
Harada işlənir	Bəzi DB indeksləri, in-memory indekslər	Java/Kotlin `TreeMap`/`TreeSet`, C++ `std::map`, Linux planlayıcısı

Balanslaşdırma: AVL və Red-Black

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