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 boshla
  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 tashla (null qil)
  2) BITTA bola            node'ni o'sha bola bilan almashtir
  3) IKKI bola             o'ng subtree'ning MIN'i (yoki chap'ning MAX'i)
                            bilan almashtir, so'ng o'sha min'ni o'chir

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 yur (2.8: min)
    node.value = voris.value;                     // qiymatni almashtir
    node.right = ochir(node.right, voris.value);  // endi o'sha min'ni o'chir
  }
  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.

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 tashla
    }
    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 yur
  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]

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 tekshir (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)