3.6-bob: Tree va Binary Search Tree (BST)

3-QISM — Algoritm va ma'lumotlar tuzilmasi · 6-mavzu

1. Kirish va motivatsiya

Hozirgacha chiziqli tuzilmalarni ko'rdik: massiv 3.2-bob, linked list 3.3-bob, stack/queue 3.4-bob — elementlar bir qatorda. Lekin real dunyodagi ko'p ma'lumot ierarxik (daraxtsimon): oila daraxti, fayl tizimi (0.2: papka ichida papka), DOM (0.5: element ichida element), kompaniya tuzilmasi, kategoriyalar.

Tree (daraxt) — ierarxik, node'lardan iborat tuzilma (har node bir nechta "bola"ga ega). Binary Search Tree (BST) — maxsus, tartiblangan daraxt: u Hash Table (tez, lekin tartibsiz — 3.5) va Array (tartibli, lekin sekin qidiruv) o'rtasidagi muvozanat — O(log n) tartiblangan qidiruv beradi.

O'xshatish: daraxt — haqiqiy daraxt teskari (ildiz tepada, barglar pastda). Yoki kompaniya tuzilmasi: direktor (ildiz) → bo'lim boshliqlari (bolalar) → xodimlar (barglar). Har kim faqat bitta "boshliq"qa (ota) bo'ysunadi, lekin ko'p "qo'l ostidagi"ga (bolalar) ega.

Nega muhim?

• DOM (0.5, 2.16), fayl tizimi 0.2-bob, JSON (2.8) — hammasi daraxt.
• BST/balanced tree — DB indeks (6.3, 6.9: B-tree), tez tartiblangan qidiruv.
• Rekursiya 3.11-bob ning eng tabiiy qo'llanishi — daraxt yurish.
• Intervyu klassikasi (traversal, balans, LCA).

2. Nazariya — chuqur tushuntirish

2.1. Tree atamalari

            ┌────┐
            │ 10 │  ← root (ildiz — eng tepa, otasi yo'q)
            └─┬──┘
        ┌─────┴─────┐
      ┌─▼─┐       ┌─▼─┐
      │ 5 │       │ 15│  ← 10 ning "bolalari" (children)
      └─┬─┘       └───┘
    ┌───┴──┐
  ┌─▼─┐  ┌─▼─┐
  │ 3 │  │ 7 │   ← "barg" (leaf — bolasi yo'q)
  └───┘  └───┘

• Node (tugun) — qiymat + bolalarga ko'rsatkichlar (3.3: pointer g'oyasi).
• Root (ildiz) — eng tepadagi node (otasi yo'q).
• Parent / Child — ota / bola munosabati.
• Leaf (barg) — bolasi yo'q node.
• Depth/Height — chuqurlik / balandlik (darajalar soni).
• Subtree — istalgan node va uning ostidagi hammasi (kichik daraxt).

2.2. Binary Tree — har node ≤ 2 bola

Binary Tree — har node ko'pi bilan 2 ta bolaga ega: chap (left) va o'ng (right):

class TreeNode {
  constructor(value) {
    this.value = value;
    this.left = null;    // chap bola (3.3: ko'rsatkich)
    this.right = null;   // o'ng bola
  }
}

2.3. Binary Search Tree (BST) — tartib qoidasi

BST — maxsus binary tree, qat'iy tartib qoidasi bilan:

Har node uchun: chap subtree'dagi BARCHA qiymatlar kichikroq, o'ng subtree'dagilar kattaroq.

            ┌────┐
            │ 10 │
            └─┬──┘
        ┌─────┴─────┐
      ┌─▼─┐       ┌─▼─┐
      │ 5 │       │ 15│     5 < 10 < 15 (chap kichik, o'ng katta)
      └─┬─┘       └───┘
    ┌───┴──┐
  ┌─▼─┐  ┌─▼─┐
  │ 3 │  │ 7 │             3 < 5 < 7 (har darajada qoida saqlanadi)
  └───┘  └───┘

Aynan shu qoida tufayli qidiruv har qadamda yarmiga bo'linadi → O(log n) (3.1: binary search g'oyasi).

2.4. BST'da qidiruv — O(log n)

Qidirilgan qiymatni root bilan taqqoslab, chap yoki o'ngga yuriladi (yarmini tashlab):

  7 ni qidirish:  10 dan boshlanadi
  7 < 10 → CHAPga (5)
  7 > 5  → O'NGga (7)
  7 === 7 → topildi!  (3 qadam, butun o'ng yarim tashlandi)

function qidir(node, qiymat) {
  if (!node) return false;                  // yo'q
  if (qiymat === node.value) return true;   // topildi
  return qiymat < node.value
    ? qidir(node.left, qiymat)              // kichik → chap (rekursiya — 3.11)
    : qidir(node.right, qiymat);            // katta → o'ng
}
// Balanslangan daraxtda O(log n) — har qadam yarmini tashlaydi

2.5. BST'ga qo'shish (insert)

Xuddi qidiruvdek joyni topib, bo'sh null ga qo'yiladi:

function qosh(node, qiymat) {
  if (!node) return new TreeNode(qiymat);   // bo'sh joy — yangi node (base case)
  if (qiymat < node.value) node.left = qosh(node.left, qiymat);   // chapga
  else if (qiymat > node.value) node.right = qosh(node.right, qiymat); // o'ngga
  return node;   // o'zgargan daraxtni qaytar
}

2.5b. BST'dan o'chirish (delete) — uch holat

O'chirish — BST'ning eng nozik amali, chunki node'ni olib tashlagandan keyin tartib qoidasi 2.3-bob buzilmasligi kerak. Avval qidiruvdek 2.4-bob node topiladi, so'ng uch holatdan biri qo'llanadi:

  1) BARG (bolasi yo'q)   → shunchaki olib tashlash (null qilish)
  2) BITTA bola           → node'ni o'sha bola bilan almashtirish
  3) IKKI bola            → o'ng subtree'ning MIN'i (yoki chap'ning MAX'i)
                            bilan almashtirish, so'ng o'sha min'ni o'chirish

Uchinchi holat eng muhim: o'rinbosar sifatida o'ng subtree'ning eng kichigi olinadi (u node'dan kattaroq, lekin o'ng tomondagi qolgan hammasidan kichik — demak tartib saqlanadi). Bu o'rinbosar — in-order vorisi (in-order'da keyingi keladigan qiymat — 2.6):

function ochir(node, qiymat) {
  if (!node) return null;                        // topilmadi (base case)
  if (qiymat < node.value) node.left = ochir(node.left, qiymat);    // chapga
  else if (qiymat > node.value) node.right = ochir(node.right, qiymat); // o'ngga
  else {                                         // topildi — uch holat
    if (!node.left) return node.right;           // 1–2: chap yo'q → o'ng (yoki null)
    if (!node.right) return node.left;           // 1–2: o'ng yo'q → chap
    let voris = node.right;                       // 3: o'ng subtree'ning min'i
    while (voris.left) voris = voris.left;        // eng chapga yurish (2.8: min)
    node.value = voris.value;                     // qiymatni almashtirish
    node.right = ochir(node.right, voris.value);  // endi o'sha min'ni o'chirish
  }
  return node;   // o'zgargan daraxtni qaytar
}
// Balanslangan daraxtda O(log n) — qidiruv + min topish bir necha qadam

2.6. Tree traversal — yurish usullari

Daraxtni "yurish" (barcha node'larni ko'rish) ning asosiy usullari (rekursiya — 3.11):

DFS (Depth-First — chuqurlikka) — uch xil tartib:

  In-order (chap → o'zi → o'ng):  BST'da SARALANGAN tartib beradi! (3, 5, 7, 10, 15)
  Pre-order (o'zi → chap → o'ng): daraxtni nusxalash/saqlash
  Post-order (chap → o'ng → o'zi): daraxtni o'chirish/hisoblash

// In-order — BST'da saralangan natija (3.9 saralashga muqobil)
function inOrder(node, natija = []) {
  if (!node) return natija;
  inOrder(node.left, natija);    // avval chap (kichiklar)
  natija.push(node.value);        // keyin o'zi
  inOrder(node.right, natija);    // keyin o'ng (kattalar)
  return natija;
}
// BST uchun → [3, 5, 7, 10, 15] (saralangan!)

BFS (Breadth-First — kenglikka) — daraja-baraja (Queue bilan — 3.4):

function bfs(root) {
  if (!root) return [];
  const natija = [], queue = [root];   // Queue (3.4)
  let front = 0;
  while (front < queue.length) {
    const node = queue[front++];        // dequeue (O(1) — 3.4)
    natija.push(node.value);
    if (node.left) queue.push(node.left);    // bolalarni navbatga
    if (node.right) queue.push(node.right);
  }
  return natija;   // daraja bo'yicha [10, 5, 15, 3, 7]
}

2.7. Balans muammosi — O(log n) vs O(n)

BST'ning kuchi balansga bog'liq. Agar tartiblangan ma'lumot ketma-ket qo'shilsa, daraxt "egilgan" (linked list kabi) bo'lib qoladi → O(n)!

  1,2,3,4,5 ketma-ket qo'shilsa:        Balanslangan:
    1                                        3
     \                                     /   \
      2          ← bu LINKED LIST!        2     4
       \            qidiruv O(n)         /       \
        3                               1         5
         \
          4                            qidiruv O(log n)
           \
            5

Yechim — self-balancing tree: AVL tree, Red-Black tree — qo'shish/o'chirishda avtomatik balanslanadi (har doim O(log n) kafolat). Ular murakkab; g'oyani bilish kifoya. DB indekslar 6.9-bob — B-tree (balanslangan, disk uchun optimallashgan).

2.8. BST vs Hash Table vs Array (3.5 davomi)

Qachon BST: tez qidiruv + tartiblangan kerak (oraliq so'rov, min/max, saralangan yurish). Faqat qidiruv kerak bo'lsa — Hash Table 3.5-bob.

2.9. Senior Architect: Lowest Common Ancestor (LCA) va Ma'lumotlar bazalaridagi B-Tree arxitekturasi

Daraxtlar arxitekturasi real ishlab chiqarishda Git commitlari zanjiri, tashkiliy ierarxiyalar va relyatsion ma'lumotlar bazalarining yuragidir.

1. Lowest Common Ancestor (LCA — Eng yaqin umumiy ajdod)

Masala (LeetCode 235/236): Ikkita node (p va q) ning eng yaqin umumiy ota tugunini topish. Bu algoritm:

• Git da ikki tarmoq (branch) birlashayotganda git merge-base komandasi orqali umumiy ajdod commitini aniqlashda;
• Tashkilot tuzilmasida ikki xodimning eng yaqin umumiy boshlig'ini topishda;
• DOM daraxtida ikki elementni qamrab oluvchi eng yaqin konteynerni hisoblashda ishlatiladi.

BST da LCA (O(h) vaqt, O(1) xotira): BST tartib qoidasidan kelib chiqib, agar ikkala qiymat ham joriy tugundan kichik bo'lsa — ajdod chapda; ikkalasi ham katta bo'lsa — o'ngda. Agar ular ikki tomonga ajralsa (biri kichik, biri katta) — demak, joriy tugunning o'zi ularning eng yaqin umumiy ajdodidir!

function lowestCommonAncestorBST(root, p, q) {
  let cur = root;
  while (cur) {
    if (p.value < cur.value && q.value < cur.value) {
      cur = cur.left;
    } else if (p.value > cur.value && q.value > cur.value) {
      cur = cur.right;
    } else {
      // Biri chapda, biri o'ngda (yoki biri cur ga teng) — ajdod topildi!
      return cur;
    }
  }
  return null;
}

2. AVL vs Red-Black Tree vs B-Tree (Nega DB larda Binary Tree ishlatilmaydi?)

Muhandislar ko'pincha so'rashadi: "Agar Binary Search Tree $O(\log n)$ bersa, nega PostgreSQL yoki MySQL indekslar uchun BST ishlatmaydi?"

1. AVL va Red-Black Trees (In-Memory — RAM uchun):

   • AVL: Balandlik farqi $\le 1$ bo'lgan juda qat'iy balanslangan daraxt. Qidiruv maksimal tez, lekin qo'shish/o'chirishda ko'p aylantirish (rotations) talab etiladi.
   • Red-Black Tree: Ranglar (qizil/qora) qoidasi bilan biroz erkinroq balanslanadi. Yozish va o'chirish tezroq. Shuning uchun Linux yadrosi (kernel task scheduler, epoll), C++ std::map va Java TreeMap larda Red-Black daraxti asosiy hisoblanadi.

2. B-Tree va B+ Tree (Disk / SSD va Ma'lumotlar Bazalari uchun):

   • Diskdan o'qish (Disk I/O) RAM'ga qaraganda 100,000 marta sekinroq.
   • Binary Tree da har bir tugunda atigi 2 ta shox bor. Agar bazada 10 million qator bo'lsa, daraxt balandligi $\log_2(10,000,000) \approx 24$ qatlam bo'ladi. Ya'ni bitta qidiruv uchun diskka 24 marta murojaat qilish kerak bo'ladi (katta kechikish).
   • B-Tree yechimi — Keng shoxlanish (High Fan-out): B-Tree ning har bir tugunida 2 ta emas, balki 100 dan 1000 tagacha kalit saqlanadi (chunki bitta disk bloki 4KB/8KB/16KB bo'lib, unga yuzlab kalitlar bemalol sig'adi!). Balandlik $\log_{100}(10,000,000) \le 3$ yoki $4$ qatlamga tushadi! Natijada 10 millionlik ulkan jadvaldan indeks bo'yicha qidirish bor-yo'g'i 3-4 ta disk I/O amali bilan bir necha millisekundda amalga oshadi!

3. Sintaksis — tez ma'lumotnoma

class TreeNode { constructor(v) { this.value = v; this.left = null; this.right = null; } }

// BST amallar (rekursiya — 3.11)
qidir(node, v)   // O(log n) balanced
qosh(node, v)    // O(log n)
ochir(node, v)   // O(log n) — uch holat (2.5b)

// Traversal
inOrder    // chap-o'zi-o'ng → BST'da SARALANGAN
preOrder   // o'zi-chap-o'ng → nusxa
postOrder  // chap-o'ng-o'zi → o'chirish
bfs        // daraja-baraja (Queue — 3.4)

4. Batafsil kod namunalari

Misol 1 — To'liq BST (2.3–2.5)

class TreeNode {
  constructor(value) { this.value = value; this.left = null; this.right = null; }
}

class BST {
  constructor() { this.root = null; }

  insert(value) {                               // (2.5)
    const node = new TreeNode(value);
    if (!this.root) { this.root = node; return; }
    let cur = this.root;
    while (true) {
      if (value < cur.value) {
        if (!cur.left) { cur.left = node; return; }   // bo'sh joy topildi
        cur = cur.left;
      } else if (value > cur.value) {
        if (!cur.right) { cur.right = node; return; }
        cur = cur.right;
      } else return;   // dublikat — qo'shmaymiz
    }
  }

  has(value) {                                  // (2.4)
    let cur = this.root;
    while (cur) {
      if (value === cur.value) return true;
      cur = value < cur.value ? cur.left : cur.right;   // yarmini tashlash
    }
    return false;
  }
}

const bst = new BST();
[10, 5, 15, 3, 7].forEach(v => bst.insert(v));
console.log(bst.has(7));   // true — O(log n)
console.log(bst.has(8));   // false

Misol 2 — Traversal (in-order saralangan — 2.6)

function inOrder(node, r = []) {
  if (!node) return r;
  inOrder(node.left, r);    // chap (kichiklar)
  r.push(node.value);       // o'zi
  inOrder(node.right, r);   // o'ng (kattalar)
  return r;
}
console.log(inOrder(bst.root));   // [3, 5, 7, 10, 15] — SARALANGAN!
// BST + in-order = saralash (boshqa saralashsiz — 3.9)

Misol 3 — Daraxt balandligi va min/max (2.7, 2.8)

// Balandlik (rekursiya — 3.11)
function balandlik(node) {
  if (!node) return 0;
  return 1 + Math.max(balandlik(node.left), balandlik(node.right));
}

// Min — eng chapdagi (BST qoidasi — 2.3)
function min(node) {
  while (node.left) node = node.left;   // chapga yurish
  return node.value;
}
// Max — eng o'ngdagi
function max(node) {
  while (node.right) node = node.right;
  return node.value;
}
console.log(min(bst.root), max(bst.root));   // 3 15 — O(log n)

Misol 4 — BFS (daraja-baraja — 2.6, Queue 3.4)

function darajaBaraja(root) {
  if (!root) return [];
  const natija = [], queue = [root];
  let front = 0;
  while (front < queue.length) {
    const node = queue[front++];           // dequeue (3.4)
    natija.push(node.value);
    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
  return natija;
}
console.log(darajaBaraja(bst.root));   // [10, 5, 15, 3, 7]

Misol 5 — BST to'g'riligini tekshirish (isValidBST)

Eng keng tarqalgan xato — faqat node'ning bevosita bolalarini solishtirish. Aslida esa chap subtree'dagi barcha tugunlar ajdoddan kichik, o'ngdagilar esa katta bo'lishi shart. Shuning uchun min va max chegaralar bilan rekursiya yuritiladi:

function isValidBST(node, min = -Infinity, max = Infinity) {
  if (!node) return true;

  // Qat'iy BST chegarasini buzsa — noto'g'ri:
  if (node.value <= min || node.value >= max) {
    return false;
  }

  // Chap bola node.value'dan kichik, o'ng bola node.value'dan katta bo'lishi shart:
  return (
    isValidBST(node.left, min, node.value) &&
    isValidBST(node.right, node.value, max)
  );
}

// O(n) vaqt, O(h) call stack xotirasi

Misol 6 — BST'da eng yaqin umumiy ajdod (Lowest Common Ancestor — LCA)

Ikkita tugun p va q uchun eng yaqin umumiy ota tugunni topish. BST xossasidan foydalanamiz:

1. Agar ikkala qiymat ham joriy tugundan kichik bo'lsa — LCA chapda.
2. Agar ikkala qiymat ham katta bo'lsa — LCA o'ngda.
3. Agar yo'llar ajralsa (biri chapda, biri o'ngda) yoki ulardan biri joriy tugunga teng bo'lsa — aynan shu tugun LCA hisoblanadi!

function lowestCommonAncestor(root, p, q) {
  let cur = root;

  while (cur) {
    if (p < cur.value && q < cur.value) {
      cur = cur.left;
    } else if (p > cur.value && q > cur.value) {
      cur = cur.right;
    } else {
      return cur.value; // ajralish nuqtasi — eng yaqin umumiy ota
    }
  }

  return null;
}

// Masalan: 3 va 7 uchun umumiy ota: 5; 3 va 15 uchun: 10
// O(h) vaqt, O(1) qo'shimcha xotira!

5. To'g'ri va noto'g'ri holatlar

1) Tartiblangan ma'lumotni ketma-ket BST'ga qo'shish

// ❌ "egilgan" daraxt → O(n) (linked list kabi — 2.7)
[1, 2, 3, 4, 5].forEach(v => bst.insert(v));

// ✅ aralash tartibda yoki self-balancing tree (AVL/Red-Black — 2.7)
// yoki o'rtadan qo'shish: [3, 1, 5, 2, 4]

2) Tartibsiz qidiruv kerak bo'lganda BST

❌ Faqat "bormi?" kerak bo'lsa, tartib kerak emas — BST ortiqcha (O(log n))
✅ Hash Table/Set — O(1) (3.5)

3) null node'ni tekshirmaslik (traversal)

// ❌ barg ostida null.value → xato (2.4)
function bad(node) { return node.left.value; }

// ✅ avval tekshiring (base case — 3.11)
function good(node) { if (!node) return; ... }

4) In-order vs pre-order chalkashligi

❌ saralangan natija kutib pre-order ishlatish
✅ BST'da saralangan = IN-ORDER (chap-o'zi-o'ng — 2.6)

6. Keng tarqalgan xatolar va yechimlari

Xato 1 — Maximum call stack (traversal'da)

Sababi: chuqur daraxt + rekursiya, yoki base case yo'q (3.11, 2.4, 0.1). Yechimi: if (!node) return base case; juda chuqur bo'lsa iterativ (Stack — 3.4).

Xato 2 — BST qidiruvi sekin (O(n))

Sababi: daraxt balanssiz ("egilgan" — 2.7). Yechimi: balanslangan qo'shish; self-balancing tree (AVL/Red-Black).

Xato 3 — Cannot read properties of null

Sababi: null bola/node'ga murojaat (3-holat). Yechimi: har murojaatdan oldin node borligini tekshiring.

Xato 4 — Saralangan natija noto'g'ri tartibda

Sababi: noto'g'ri traversal turi (4-holat). Yechimi: saralangan uchun in-order; tartibni eslang 2.6-bob.

Xato 5 — Dublikat qo'shish

Sababi: BST'da bir xil qiymat ikki marta. Yechimi: qo'shishda === holatini hal qiling (o'tkazib yuboring yoki sanagich — Misol 1).

7. Integratsiya — bu mavzu stack'ning qayerida uchraydi

• DOM (0.5, 2.16): sahifa — daraxt; traversal (querySelector).
• Fayl tizimi 0.2-bob: papka ierarxiyasi — daraxt (3.2 loyiha).
• JSON 2.8-bob: ichma-ich obyekt — daraxt.
• DB indeks 6.9-bob: B-tree (balanslangan) — O(log n) qidiruv.
• Rekursiya 3.11-bob: traversal — rekursiyaning tabiiy qo'llanishi.
• Stack/Queue 3.4-bob: DFS — Stack, BFS — Queue.
• Hash Table 3.5-bob: muqobil (tez, lekin tartibsiz).

8. Eng yaxshi amaliyotlar (best practices)

• Tez qidiruv + tartiblangan → BST; faqat qidiruv → Hash Table (3.5, 2.8).
• Balansga e'tibor — tartiblangan ketma-ket qo'shmang; production'da self-balancing/B-tree 2.7-bob.
• In-order = saralangan (BST) — yodlang 2.6-bob.
• Base case (if (!node)) har traversal/rekursiyada 3.11-bob.
• DFS — rekursiya/Stack, BFS — Queue (2.6, 3.4).
• Chuqur daraxtda iterativ (Stack) — stack overflow'dan saqlaydi (6-bo'lim).
• JS'da tayyor BST yo'q — kunlik ishda Map/Set yetadi; BST ko'proq tushuncha/maxsus holat.
• Real ierarxiya (DOM, JSON, fayl) — daraxt sifatida ko'ring.

9. Amaliy loyiha: "Binary Search Tree va Daraxt Algoritmlari"

BST va traversal'ni amalda mustahkamlash.

Maqsad

Tree/BST tuzilmasi, tartib qoidasi va traversal usullarini qurib, daraxt algoritmlarini (balandlik, balans, min/max) qo'llash.

Talablar (requirements)

1. BST class: insert, has, delete (o'chirish — uch holat: barg, 1 bola, 2 bola — qiyinroq, 2.5b), min, max (Misol 1, 3).
2. Traversal: inOrder (saralangan), preOrder, postOrder, bfs (daraja-baraja — Misol 2, 4).
3. Balandlik: rekursiv height() (Misol 3, 3.11).
4. Balans tekshiruvi: isBalanced() — har node'da chap/o'ng balandlik farqi ≤ 1 2.7-bob.
5. isValidBST(): daraxt haqiqatan BST qoidasiga mosmi (min/max chegara bilan).
6. Saralash: istalgan massivni BST + in-order bilan saralang (Misol 2) — Big-O ni ayting 3.1-bob.
7. Lowest Common Ancestor (LCA): ikki node'ning eng yaqin umumiy otasi (bonus).
8. Chegaraviy holatlar: bo'sh daraxt, bitta node, egilgan daraxt (0.6, 2.7).

Maslahatlar (hint)

• Insert/has — qidiruv qoidasi (chap kichik, o'ng katta — 2.3).
• O'chirishda 2 bolali node: o'ng subtree'ning min'i (yoki chap'ning max'i) bilan almashtiring (uch holat — 2.5b).
• In-order = saralangan 2.6-bob; height — 1 + max(chap, o'ng) (Misol 3).
• isBalanced/isValidBST — rekursiv, har node tekshiriladi.
• Base case (if (!node)) har joyda (3.11, 6-bo'lim).

"Tayyor" mezonlari (acceptance criteria)

• BST insert/has/min/max ishlaydi.
• To'rt traversal (in/pre/post/bfs) to'g'ri tartib beradi.
• In-order saralangan natija beradi.
• height to'g'ri balandlik beradi.
• isBalanced/isValidBST to'g'ri aniqlaydi.
• Massivni BST orqali saralash ishlaydi.
• Bo'sh/bitta/egilgan daraxt qulamaydi.

Yechim kodi ataylab berilmagan — bu loyihani o'zingiz yozib ko'ring.

10. Xulosa va keyingi bobga ko'prik

Bu bobda ierarxik tuzilmani — Tree va BSTni o'rgandik:

• Tree — ierarxik node'lar (root, parent/child, leaf); DOM, fayl tizimi, JSON — daraxt.
• Binary Tree — har node ≤ 2 bola (left/right).
• BST — tartib qoidasi (chap < node < o'ng) → O(log n) qidiruv/qo'shish (balanslangan).
• Traversal: in-order (BST'da saralangan!), pre-order, post-order (DFS — rekursiya); BFS (daraja-baraja — Queue).
• Balans muhim: egilgan daraxt → O(n); self-balancing (AVL/Red-Black), DB B-tree 6.9-bob.
• BST — Hash Table (tez, tartibsiz — 3.5) va Array o'rtasidagi muvozanat.

Keyingi bob — 3.7-bob: Graph. Daraxt — maxsus graf (har node bitta otaga ega). Graph — umumiyroq: node'lar ixtiyoriy bog'langan (ijtimoiy tarmoq, xarita, internet — 0.4). BFS/DFS (bu bobda ko'rdik), eng qisqa yo'l — grafning kuchli algoritmlari.

Foydalanilgan rasmiy/ishonchli manbalar

• bigocheatsheet.com — BST/tree operatsiyalari murakkabligi
• Universal CS — binary tree, BST, traversal (DFS/BFS), self-balancing trees
• MDN Web Docs — DOM tree 0.5-bob, rekursiya (3.11 ga bog'liq)