Balanslangan daraxtlar va B-tree: AVL, Red-Black, rotatsiya va ma'lumotlar bazasi indeksi

Qisqacha: Oddiy BST saralangan ma'lumotda zanjirga aylanadi va O(n) bo'lib qoladi. Balanslangan daraxtlar har qo'shish va o'chirishdan keyin shaklni rotatsiya (burish) bilan to'g'irlaydi va balandlikni O(log n) da ushlaydi. AVL qat'iy: har tugunda chap va o'ng balandlik farqi ≤ 1. Red-Black yumshoqroq, lekin kamroq buradi. B-tree esa bitta tugunda yuzlab kalit saqlaydi: milliard yozuvda ham 4–5 qavat. Shuning uchun ma'lumotlar bazalari indekslari va fayl tizimlari B-tree'dan foydalanadi.

Bu darsda

• Nega oddiy BST saralangan ma'lumotda yiqilishini va "balans" nima ekanini tushuntira olasiz.
• Chapga va o'ngga rotatsiyani qo'lda bajara olasiz va AVL daraxtga qo'shishni yoza olasiz.
• AVL va Red-Black daraxtlarining farqini va qayerda ishlatilishini ayta olasiz.
• B-tree nega diskdagi ma'lumot uchun eng yaxshi tanlov ekanini va ma'lumotlar bazasi indeksi ichida nima borligini tushuntira olasiz.

Oldin bilishingiz kerak: Binary Search Tree, Daraxt bo'ylab yurish: DFS va BFS, Asosiy murakkablik sinflari.

1. Nega bu kerak?

O'tgan darsda Sardor buyurtmalarni BST'da saqladi va o'lchovlar zo'r chiqdi: 400 000 ta tasodifiy raqam — yarim soniyadan kam. Keyin haqiqiy kassaga ulandi. Kassa esa buyurtmalarni tartib bilan raqamlaydi: 1001, 1002, 1003, … Har yangi raqam oldingilarining hammasidan katta va doim o'ngga ketadi. Daraxt zanjirga aylandi. 40 000 ta buyurtmani qo'shish 1,8 soniya oldi, bu BST tasodifiy tartibdagidan 60 baravar sekin.

Muammo daraxtning g'oyasida emas, shaklida. Bir xil raqamlar to'plamidan juda ko'p xil BST yasash mumkin: zanjir ham, chiroyli "piramida" ham. Hammasi to'g'ri BST, lekin balandligi har xil. Bizga shunday daraxt kerakki, raqamlar qaysi tartibda kelmasin, o'zini piramida shaklida ushlab tursin.

Bu oshxonadagi patnisga o'xshaydi. Ofitsiant hamma likopchani bir chetga qo'ysa, patnis ag'dariladi. Har yangi likopchadan keyin u yukni ozgina suradi — patnis tekis turadi. Balanslangan daraxt ham shunday: har qo'shishdan keyin ozgina tuzatish qiladi.

2. Balans nima

2.1 Muvozanatli daraxt

Muvozanatli (balanslangan) daraxt (balanced tree) — balandligi doim O(log n) bo'lib qoladigan daraxt. n ta tugunli binar daraxtning eng kichik mumkin bo'lgan balandligi — taxminan log₂ n. Million tugunda bu 20. Muvozanatli daraxt aynan 20 bo'lishi shart emas — 25 yoki 28 ham bo'ladi. Muhimi: n ikki baravar oshganda balandlik bitta-ikkitaga oshadi, n ga emas.

Buni ta'minlash uchun daraxtga qo'shimcha qoida qo'yiladi va har o'zgarishdan keyin tekshiriladi. Qoida turlicha bo'lishi mumkin — shundan AVL, Red-Black va boshqa daraxtlar kelib chiqqan.

2.2 Balans farqi

Eng sodda qoida AVL daraxtniki. Har tugun uchun balans farqi (balance factor) hisoblanadi: chap shox balandligi minus o'ng shox balandligi. AVL qoidasi: har tugunda bu farq −1, 0 yoki +1. Farq +2 yoki −2 bo'lsa — qoida buzilgan, tuzatish kerak.

Bu darsda balandlikni qavatlar soni bilan sanaymiz: bo'sh shox — 0, bitta tugun — 1. Bu Daraxt atamalari darsidagi qirralar balandligidan bittaga ko'p. Farq uchun bu ahamiyatsiz: ikkala shoxga bir xil 1 qo'shiladi va ayirmada yo'qoladi. Kodda esa qulay — bo'sh shox uchun manfiy son kerak bo'lmaydi.

   10   farq −2         20   farq 0
     \                 /  \
      20   farq −1   10    30
        \
         30

Chapdagi zanjirda 10 ning chap shoxi bo'sh (balandligi 0), o'ngi 2 qavatli — farq −2. O'ngdagi daraxtda hamma tugunda farq 0. Raqamlar bir xil, tartib (inorder) ham bir xil: 10, 20, 30.

3. Rotatsiya — tartibni buzmasdan shaklni o'zgartirish

3.1 Chapga burish

Chapdagi zanjirni o'ngdagi piramidaga qanday aylantiramiz? Rotatsiya (rotation, burish) bilan. Chapga burishda o'ng bola (20) tepaga chiqadi, ota (10) uning chap bolasiga aylanadi:

     x                y
      \              / \
       y     →      x   C
      / \            \
     B   C            B

Bitta nozik joy — B shoxi: u y ning chap bolasi edi. Burishdan keyin y ning chap joyini x egallaydi. B ni x ning o'ng joyiga o'tkazamiz — u bo'sh qoldi. Bu to'g'rimi? B dagi hamma qiymat x dan katta edi (x ning o'ng shoxida edi) va y dan kichik edi. Yangi joyida ham aynan shunday: x ning o'ngida, y ning chap shoxida. Qoida buzilmadi.

Kodda bu uchta havola o'zgarishi:

const node = (value, left = null, right = null) =>
  ({ value, left, right });

function rotateLeft(x) {
  const y = x.right; // o'ng bola tepaga chiqadi
  x.right = y.left; // B shoxi x ga o'tadi
  y.left = x; // eski ota — endi chap bola
  return y; // shoxning yangi ildizi
}

const chain = node(10, null, node(20, null, node(30)));
const top = rotateLeft(chain);
console.log(top.value, top.left.value, top.right.value); // 20 10 30

Rotatsiya O(1): hech qanday sikl yo'q, faqat uchta havola. Daraxtning qolgan qismiga tegilmaydi.

3.2 O'ngga burish va ikki karra burish

O'ngga burish — chapga burishning ko'zgudagi aksi: chap bola tepaga chiqadi. U chap tomoni og'ir zanjirni (30 → 20 → 10) tuzatadi.

Lekin bitta burish har doim yetmaydi. [30, 10, 20] qo'shilganini olaylik: 30 ning chap bolasi 10, uning o'ng bolasi 20. Zanjir "egri" — avval chapga, keyin o'ngga. Bu yerda 30 atrofida o'ngga burish yordam bermaydi: egri boshqa tomonga o'tadi, xolos. Avval pastki tugunni (10) chapga burib, egrini to'g'rilaymiz — 30 → 20 → 10 zanjiri chiqadi. Keyin 30 atrofida o'ngga buramiz. Bu ikki karra burish (double rotation).

Hammasi bo'lib to'rt holat bor:

Tekshirib ko'ring: [10, 30, 20] ketma-ket qo'shildi. Qaysi holat va natijada ildizda qaysi raqam turadi?

4. AVL daraxt

4.1 Kod

AVL daraxt — 1962-yilda Adelson-Velskiy va Landis ixtiro qilgan birinchi balanslangan daraxt (nomi ularning ismlaridan). Har tugun o'z balandligini saqlaydi: tanish { value, left, right } tuguniga bitta maydon qo'shiladi — height. Yangi tugun barg bo'lib tushadi, uning height i — 1. Qo'shish oddiy BST'dagidek, faqat qaytishda har tugun balandligini yangilaymiz va farqni tekshiramiz. Farq 2 ga yetsa — jadvaldagi burishlardan biri.

Kuzating: 10, 20, …, 70 — o'sish tartibida, oddiy BST zanjirga aylantiradigan ketma-ketlik. Avval boshini qog'ozda yurib chiqamiz:

• 10, keyin 20 — 20 o'ngga tushadi, 10 da farq −1. Qoida bajariladi.
• 30 — yana o'ngga. 10 da farq −2, o'ng-o'ng holat. 10 atrofida chapga burish: ildizda 20, chapida 10, o'ngida 30.
• 40 — burish kerak emas, farqlar ±1 ichida.
• 50 — endi 30 da farq −2. Yana chapga burish: 40 tepaga chiqadi, 30 uning chapiga o'tadi.

Qolganini vizualda kuzating. Tugun yonidagi h — uning balandligi:

Kodning asosiy qismi — rebalance. U tugun balandligini yangilaydi va farqni hisoblaydi. Chap og'ir bo'lsa (diff > 1), avval egri holatni tekshiradi: chap bolaning o'ng shoxi balandroq bo'lsa — bolani chapga buradi. Keyin otani o'ngga buradi. O'ng tomon uchun — ko'zgudagi aksi.

insert rekursiv: har chaqiruv o'z shoxining yangi ildizini qaytaradi (BST'dagi removeNode kabi). Burishdan keyin shox ildizi almashgani uchun bu shart. Rekursiya chuqurligi daraxt balandligiga teng — AVL'da u kichik, stek to'lmaydi.

4.2 Nega AVL balandligi kichik

AVL qoidasi daraxtni mukammal qilmaydi, lekin juda "qiyshaytirib" ham qo'ymaydi. Matematik isbot bor: n tugunli AVL daraxt balandligi 1,44 · log₂ n dan oshmaydi. O'lchab ko'rdik:

O'sish tartibida AVL eng yaxshi natijani berdi — log₂ n ning o'zi! Oddiy BST uchun eng yomon kirish AVL uchun mukammal bo'lib chiqdi. Tasodifiy tartibda ham AVL oddiy BST dan ikki baravar past.

Tekshirib ko'ring: AVL daraxtda 1 000 000 ta buyurtma bor. Bitta buyurtmani qidirish eng ko'pi bilan nechta solishtirish talab qiladi (jadval bo'yicha, o'sish tartibida qo'shilgan bo'lsa)?

4.3 O'lchov: zanjir va AVL

Buyurtma raqamlarini o'sish tartibida qo'shib, vaqtni o'lchadik:

Oddiy BST: n ikki baravar — vaqt to'rt baravar va undan ko'p (O(n²)). AVL: ikki baravar (O(n log n)). 16 000 ta buyurtmada farq 160 baravar. AVL'ni kattaroq n da ham o'lchadik: 100 000 — 25 ms, 200 000 — 53 ms, 400 000 — 117 ms, 800 000 — 238 ms. Har qadamda ×2,0–2,2.

Burishlar tekin emas: har qo'shishda balandliklarni yangilash va tekshirish bor. Tasodifiy tartibda AVL oddiy BST bilan deyarli teng chiqdi (400 000 ta qo'shish va qidirish — ikkalasi ≈ 0,4–0,5 s). AVL'ning foydasi — kafolat: eng yomon kirishda ham O(log n).

5. Red-Black daraxt — g'oyasi

AVL qat'iy: farq 2 bo'lishi bilan buradi. Bu qidirish uchun yaxshi (daraxt past), lekin ko'p qo'shish va o'chirishda burishlar ko'payadi. Red-Black daraxt (qizil-qora daraxt) qoidani yumshatadi. Har tugun qizil yoki qora rangga bo'yaladi va beshta qoida bajariladi. Ularning ikkitasi asosiy:

• qizil tugunning bolasi qizil bo'lmaydi (ikki qizil ketma-ket kelmaydi);
• ildizdan istalgan bo'sh joygacha (null) bo'lgan har yo'lda qora tugunlar soni bir xil.

Natijada eng uzun yo'l eng qisqasidan ikki baravardan uzun bo'lmaydi: balandlik ≤ 2 · log₂(n + 1). AVL'dan biroz balandroq, lekin qo'shish yoki o'chirishda ko'pi bilan 2–3 ta burish yetadi. Ko'p hollarda faqat ranglarni almashtirish kifoya.

Red-Black kodini yozish AVL'dan ancha uzun — o'chirishda o'nga yaqin holat bor. Uni yod olish shart emas. Bilish kerak bo'lgani: u bor, kafolati O(log n), va ko'p tillarning saralangan lug'atlari ichida aynan u turadi:

Maslahat: Intervyuda odatda AVL yoki Red-Black kodini yozish so'ralmaydi. So'raladi: "oddiy BST qachon yomonlashadi va buning yechimi nima?" Javob: saralangan kirishda zanjir; yechim — o'zini balanslaydigan daraxt (AVL, Red-Black), ular rotatsiya bilan balandlikni O(log n) da ushlaydi.

6. B-tree — disk uchun daraxt

6.1 Muammo: disk sekin

«Bahor» bir necha yilda millionlab buyurtma to'pladi. Ular endi kompyuter xotirasida (RAM) emas, diskda — ma'lumotlar bazasida saqlanadi. Diskdan o'qish xotiradan o'qishdan minglab baravar sekin. Disk ma'lumotni bittalab emas, sahifa (page) deb ataladigan bo'laklar bilan o'qiydi. PostgreSQL'da sahifa — 8 KB, MySQL'ning InnoDB tizimida — 16 KB.

Million buyurtmali AVL daraxtni diskda saqlasak, bitta qidiruv 20 ta tugunga sakraydi. Har tugun diskning boshqa joyida bo'lishi mumkin — 20 ta sekin o'qish. Har o'qishda esa 8 KB keladi-yu, undan bitta raqam ishlatiladi.

G'oya: bitta sahifaga ko'p kalit joylaymiz. Omborni eslang: Sardor har safar bitta qog'oz uchun omborga borsa, kuni yo'lda o'tadi. Aqllirog'i — butun papkani olib kelish, kerakli qog'ozni esa stol ustida tez topish. Sahifa bitta o'qishda to'liq keladi — ichidagi yuzlab kalitni solishtirish deyarli tekin.

6.2 B-tree tuzilishi

B-tree — har tugunda bir nechta tartiblangan kalit va kalitlardan bittaga ko'p bola bo'ladigan muvozanatli daraxt. Tugundagi k ta kalit sonlar o'qini k + 1 ta oraliqqa bo'ladi. Har oraliqqa bitta bola. Masalan, 30 | 60 tugunining uchta bolasi bor: 30 dan kichiklar, 30–60 oralig'i va 60 dan kattalar. BST — bu B-tree'ning har tugunda bitta kalit bo'lgan xususiy holi. Kodda B-tree tuguni boshqacha ko'rinadi: left/right o'rniga keys (tartiblangan kalitlar) va children massivlari — Daraxt atamalari darsidagi umumiy daraxtga o'xshab.

Kuzating: kichik B-tree'da 50 va 85 ni qidiramiz:

B-tree'ning ikki asosiy qoidasi:

• Hamma barglar bir xil chuqurlikda. Daraxt tepadan o'smaydi, pastdan o'sadi: tugun to'lsa, u ikkiga bo'linadi va o'rtadagi kalit otaga ko'tariladi. Ildiz bo'linganda yangi ildiz paydo bo'ladi — balandlik shunda oshadi. Shuning uchun B-tree hech qachon qiyshaymaydi.
• Har tugun kamida yarim to'la (ildizdan tashqari). O'chirishda tugun juda bo'shab qolsa, qo'shnisidan kalit oladi yoki u bilan birlashadi.

Bo'linish va birlashtirish kodi uzun, uni yozish shart emas. Asosiysi — natija: balandlik juda kichik.

6.3 Nechta qavat?

d qavatli to'liq daraxtga m^d − 1 ta kalit sig'adi, m — tugundagi bolalar soni. Hisoblab ko'ramiz:

// d qavatli to'liq daraxtga m^d − 1 ta kalit sig'adi
function levels(n, children) {
  let capacity = children - 1; // 1 qavat: faqat ildiz
  let depth = 1;
  while (capacity < n) {
    capacity = capacity * children + (children - 1);
    depth++;
  }
  return depth;
}

for (const n of [1_000_000, 1_000_000_000]) {
  const line = [2, 100, 500].map((m) => `${m} → ${levels(n, m)}`);
  console.log(`${n} kalit: ${line.join(", ")}`);
}

Konsolda:

1000000 kalit: 2 → 20, 100 → 4, 500 → 3
1000000000 kalit: 2 → 30, 100 → 5, 500 → 4

Binar daraxt (m = 2) milliard kalitda 30 qavat. Tugunda 500 ta bola bo'lsa — atigi 4 qavat. 8 KB sahifaga yuzlab kalit bemalol sig'adi, shuning uchun haqiqiy indekslarda m yuzlab bo'ladi. Bundan tashqari, yuqori 2–3 qavat odatda xotirada (keshda) turadi. Milliard qatorli jadvaldan bitta qatorni topish amalda 1–2 ta disk o'qishiga tushadi.

Endi o'zingiz hisoblang. Tugunda 1 000 ta bola bo'lsa, 500 million kalit uchun qavat yetadi (1 000³ — milliard).

6.4 B+tree

Ma'lumotlar bazalarida ko'pincha B+tree varianti ishlatiladi. Ikkita farqi bor:

1. Qiymatlar (yozuvlar yoki ularning manzili) faqat barglarda saqlanadi. Ichki tugunlarda faqat "yo'l ko'rsatkich" kalitlar. Ichki tugunga ko'proq kalit sig'adi — daraxt yanada past.
2. Barglar bir-biriga zanjir bilan ulangan. "Narxi 20 000 dan 40 000 gacha" so'rovida baza 20 000 ni bir marta qidiradi, keyin barglar bo'ylab yon tomonga yuradi. Bu O(log n + k) — o'tgan darsdagi oraliq so'rovining disk varianti.

7. Qayerda ishlatiladi

• Ma'lumotlar bazasi indekslari. PostgreSQL'da CREATE INDEX sukut bo'yicha B-tree yasaydi. MySQL InnoDB'da jadvalning o'zi B+tree ko'rinishida saqlanadi. SQLite ham B-tree ishlatadi. SQL va indekslarni 26-qismda — Indeks nima: B-tree ichidan darsida amalda o'rganamiz. Hozir bilish kerak bo'lgani: "indeks qo'shdim — qidiruv tezlashdi" degani "jadval ustiga B-tree qurildi" degani.
• Fayl tizimlari. NTFS (Windows), APFS (macOS), Btrfs (Linux) papka va fayllarni B-tree turidagi tuzilmalarda saqlaydi.
• Xotiradagi saralangan lug'atlar. Red-Black va AVL — Java, C++, Linux yadrosida. Rust BTreeMap esa xotirada ham B-tree tanlagan: bitta tugundagi kalitlar xotirada yonma-yon turadi va protsessor keshi ularni tez o'qiydi.
• JavaScript. Tilda tayyor balanslangan daraxt yo'q. Map va Set — hash jadval, ular qiymat tartibini saqlamaydi. Kerak bo'lsa: kichik hajmda — saralangan massiv; katta hajmda — tayyor kutubxona (masalan, npm'dagi sorted-btree paketi, 2.1.0 versiya; npm'ni 16-qismda chuqur o'rganamiz, hozir bilish shart emas).

8. Chegaraviy holatlar

• Bo'sh daraxt. Balandligi 0; birinchi qo'shilgan tugun ildiz bo'ladi, burish kerak emas.
• Bitta va ikkita tugun. Ikki tugunda farq ±1 — qoida bajariladi. Burish faqat uchinchi tugundan boshlab kerak bo'lishi mumkin.
• Takroriy kalit. Bizning insert takrorni qo'shmaydi va daraxtni o'zgartirmaydi. rebalance baribir chaqiriladi, lekin farq o'zgarmagani uchun burmaydi.
• O'chirish. AVL'da o'chirishdan keyin ham rebalance kerak — va bitta o'chirish ildizgacha bir nechta burishga sabab bo'lishi mumkin (qo'shishda esa ko'pi bilan bitta tuzatish).

9. Ko'p uchraydigan xatolar

9.1 Burishdan keyin balandlikni yangilamaslik

Burishda ikkita tugunning bolalari o'zgaradi. Ularning height maydoni eski bo'lib qolsa, keyingi tekshiruvlar noto'g'ri qaror qiladi — daraxt sekin-asta qiyshayadi, xato xabari esa chiqmaydi. Tuzatish: avval pastga tushgan tugunni (x), keyin tepaga chiqqanini (y) yangilang. Tartib muhim: y ning balandligi x ga bog'liq.

9.2 Burishdan keyin otaga yangi ildizni bermaslik

rotateLeft(n) yangi ildizni qaytaradi. rotateLeft(n); deb natijani tashlab yuborsangiz, ota hali eski tugunni ko'rsatadi va daraxtning bir qismi "yo'qoladi". Tuzatish: n.right = rotateRight(n.right), return rotateLeft(n).

9.3 Egri holatda bitta burish

[30, 10, 20] da faqat o'ngga burish — egrini boshqa tomonga o'tkazadi, xolos. Tuzatish: avval bolaning og'ir tomonini tekshiring (height(n.left.left) < height(n.left.right)).

9.4 "Indeks — sehr"

Indeks B-tree, demak qidiruv O(log n). Lekin indeksning ham narxi bor: har INSERT da daraxt yangilanadi, va u diskda joy egallaydi. Tuzatish: indeksni faqat tez-tez qidiriladigan ustunlarga qo'ying — buni 26-qismda o'lchab ko'ramiz.

10. Mashqlar

1-mashq (oson): Burishni qo'lda bajaring

AVL daraxtga [50, 40, 30] ketma-ket qo'shildi. Qaysi tugunda qoida buziladi, qaysi burish kerak va natijada daraxt qanday ko'rinadi? Keyin [50, 30, 40] uchun ham shunday qiling.

2-mashq (o'rta): Indeks qancha o'qish talab qiladi

«Bahor» tarmog'ida 50 million buyurtma bor. Indeks sahifasiga 300 ta kalit sig'adi (301 bola). Darsdagi levels funksiyasi bilan hisoblang: B-tree nechta qavat bo'ladi? Shu buyurtmalarni AVL'da saqlasak-chi (taxminan 1,44 · log₂ n dan oshmaydi)? Ishora: Math.log2.

function levels(n, children) {
  let capacity = children - 1;
  let depth = 1;
  while (capacity < n) {
    capacity = capacity * children + (children - 1);
    depth++;
  }
  return depth;
}

console.log(levels(50_000_000, 301)); // 4
console.log(Math.ceil(1.44 * Math.log2(50_000_000))); // 37

3-mashq (qiyin): AVL testlari

kurs/mashqlar/14/39-avl/avl.test.mjs faylida darsdagi AVL kodini yozing va checkAVL(root) yordamchi funksiyasini qo'shing. U har tugunda farq ≤ 1 ekanini va saqlangan height to'g'riligini assert bilan tekshirsin va balandlikni qaytarsin. Testlar:

1. Chap-o'ng holat: [30, 10, 20] → ildiz 20, inorder [10, 20, 30].
2. O'ng-chap holat: [10, 30, 20] → ildiz 20.
3. 1 dan 100 000 gacha o'sish tartibida — checkAVL o'tadi, balandlik 17 va 1,44 · log₂ n dan oshmaydi.
4. Takrorlar qo'shilmaydi, inorder saralangan.

// kurs/mashqlar/14/39-avl/avl.test.mjs
import { test } from "node:test";
import assert from "node:assert/strict";

const height = (n) => (n === null ? 0 : n.height);
const update = (n) => {
  n.height = 1 + Math.max(height(n.left), height(n.right));
};

function rotateLeft(x) {
  const y = x.right;
  x.right = y.left;
  y.left = x;
  update(x);
  update(y);
  return y;
}

function rotateRight(y) {
  const x = y.left;
  y.left = x.right;
  x.right = y;
  update(y);
  update(x);
  return x;
}

function rebalance(n) {
  update(n);
  const diff = height(n.left) - height(n.right);
  if (diff > 1) {
    if (height(n.left.left) < height(n.left.right)) {
      n.left = rotateLeft(n.left);
    }
    return rotateRight(n);
  }
  if (diff < -1) {
    if (height(n.right.right) < height(n.right.left)) {
      n.right = rotateRight(n.right);
    }
    return rotateLeft(n);
  }
  return n;
}

function insert(n, value) {
  if (n === null) {
    return { value, left: null, right: null, height: 1 };
  }
  if (value < n.value) n.left = insert(n.left, value);
  else if (value > n.value) n.right = insert(n.right, value);
  return rebalance(n);
}

// Har tugunda farq ≤ 1 va saqlangan height to'g'rimi
function checkAVL(n) {
  if (n === null) return 0;
  const l = checkAVL(n.left);
  const r = checkAVL(n.right);
  assert.ok(Math.abs(l - r) <= 1, `${n.value} da farq ${l - r}`);
  assert.equal(n.height, 1 + Math.max(l, r));
  return n.height;
}

function build(values) {
  let root = null;
  for (const v of values) root = insert(root, v);
  return root;
}

function inorder(n, out = []) {
  if (n === null) return out;
  inorder(n.left, out);
  out.push(n.value);
  inorder(n.right, out);
  return out;
}

test("chap-o'ng holat: 30, 10, 20 → ildiz 20", () => {
  const root = build([30, 10, 20]);
  assert.equal(root.value, 20);
  assert.deepEqual(inorder(root), [10, 20, 30]);
});

test("o'ng-chap holat: 10, 30, 20 → ildiz 20", () => {
  assert.equal(build([10, 30, 20]).value, 20);
});

test("100 000 o'sish tartibida — balandlik 17", () => {
  const ids = Array.from({ length: 100000 }, (_, i) => i + 1);
  const root = build(ids);
  assert.equal(checkAVL(root), 17);
  assert.ok(root.height <= 1.44 * Math.log2(100000));
});

test("takror va inorder", () => {
  const root = build([5, 3, 8, 3, 5, 1]);
  assert.deepEqual(inorder(root), [1, 3, 5, 8]);
  checkAVL(root);
});

✔ chap-o'ng holat: 30, 10, 20 → ildiz 20 (1.509ms)
✔ o'ng-chap holat: 10, 30, 20 → ildiz 20 (0.1549ms)
✔ 100 000 o'sish tartibida — balandlik 17 (41.0965ms)
✔ takror va inorder (0.2421ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 127.3091

4-mashq: Amaliy tajriba — balans qatorlari

kurs/mashqlar/14/MURAKKABLIK.md ga qo'shing: AVL (qo'shish, qidirish), rotatsiya, B-tree qidiruvi (disk o'qishlari soni bilan). Oddiy BST qatoriga "o'sish tartibida — O(n)" izohini yozing.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Qo'shish / qidirish | AVL | O(log n) kafolat | O(n) |
| Shaklni tuzatish | rotatsiya | O(1) | O(1) |
| Diskda qidirish | B-tree, m bola | O(log_m n) o'qish | O(n) |
| Qo'shish (o'sish tartibida) | oddiy BST | O(n), jami O(n²) | O(n) |

git add 14/MURAKKABLIK.md 14/39-avl
git commit -m "14/39: AVL daraxt va B-tree hisobi"

11. Real ishda

• Backend dasturchi balanslangan daraxtni o'zi yozmaydi, lekin har kuni ishlatadi: har indeksli SQL so'rov — B-tree qidiruvi. "Nega bu so'rov sekin?" savoliga javob ko'pincha "indeks yo'q, baza butun jadvalni o'qiyapti".
• Indeks dizayni. Oraliq so'rovlari (BETWEEN, ORDER BY ... LIMIT) B-tree'da tez, chunki u tartibni saqlaydi. Hash indeks faqat tenglik uchun.
• Kutubxonalar. Saralangan to'plam kerak bo'lsa — tayyor, sinalgan kutubxona. O'z Red-Black daraxtingizni prodakshnga yozish — xato manbai.
• Intervyu. "AVL va Red-Black farqi?", "Nega ma'lumotlar bazasi binar daraxt emas, B-tree ishlatadi?" — tizim dizayni savollarining boshlanishi.

Xulosa

• Oddiy BST saralangan kirishda zanjirga aylanadi: 16 000 buyurtma — ≈ 510 ms, AVL'da — 3,2 ms.
• Rotatsiya O(1) da shaklni o'zgartiradi va BST tartibini saqlaydi. To'rt holat: ikkita oddiy va ikkita ikki karra burish.
• AVL — har tugunda balandlik farqi ≤ 1, balandlik ≤ 1,44 · log₂ n. Red-Black — yumshoqroq qoida, kamroq burish, ≤ 2 · log₂ n.
• B-tree — tugunda ko'p kalit, hamma barglar bir chuqurlikda; milliard kalitda 4–5 qavat. B+tree'da qiymatlar barglarda va barglar zanjirlangan.
• Ma'lumotlar bazasi indeksi — B-tree; JavaScript'da tayyor balanslangan daraxt yo'q.

Keyingi dars: Daraxt masalalari — "har tugun bolalaridan javob olib, o'zinikini qaytaradi" naqshi bilan balandlik, diametr, yo'l yig'indisi va eng yaqin umumiy ajdod.

Manbalar

• G. M. Adelson-Velsky, E. M. Landis, "An algorithm for the organization of information", 1962 — AVL daraxtning asl maqolasi.
• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 13-bob (Red-Black), 18-bob (B-tree).
• PostgreSQL hujjatlari: "Index Types — B-Tree", "Database Page Layout" (8 KB sahifa) — postgresql.org/docs
• MySQL hujjatlari: InnoDB "The Physical Structure of an InnoDB Index", innodb_page_size (16 KB) — dev.mysql.com/doc
• Rust hujjatlari: std::collections::BTreeMap — doc.rust-lang.org