Daraxt tuzilmasi: ildiz, tugun, barg, balandlik va binar daraxt

Qisqacha: Daraxt (tree) — ierarxik tuzilma: bitta ildiz (root), har tugunning bitta otasi va istalgancha bolasi bor, sikl yo'q. Bolasi yo'q tugun — barg (leaf). Tugunning chuqurligi (depth) — ildizdan unga qadar qirralar soni, daraxtning balandligi (height) — eng chuqur barg chuqurligi. Binar daraxt — har tugunda ko'pi bilan ikki bola: chap va o'ng. Daraxt bilan ishlashning asosiy usuli — rekursiya: "javob = tugunning o'zi + bolalarning javoblari". DOM, fayl tizimi, JSON va menyu kategoriyalari — hammasi daraxt.

Bu darsda

• Daraxt atamalarini (ildiz, tugun, qirra, barg, ota, bola, chuqurlik, balandlik, kichik daraxt) misolda ko'rsata olasiz.
• Daraxtni JavaScript obyektlari bilan ifodalaysiz: umumiy (children) va binar (left, right).
• Tugunlar soni, barglar va balandlikni rekursiv hisoblaysiz.
• To'la, to'liq, mukammal va zanjirsimon binar daraxtni ajratib, balandlik nega muhimligini o'lchaysiz.

Oldin bilishingiz kerak: Rekursiv fikrlash, DOM daraxti va tugun turlari, Linked list.

1. Nega bu kerak?

Hozirgacha 14-qismdagi tuzilmalar chiziqli edi: massiv, bog'langan ro'yxat, stek, navbat. Har elementning ko'pi bilan bitta "keyingisi" bor. Lekin «Bahor» menyusi boshqacha tuzilgan:

Menyu
├── Taomlar
│   ├── osh
│   ├── lag'mon
│   └── manti
└── Ichimliklar
    ├── ko'k choy
    └── Sharbatlar
        └── olma

"Taomlar" ning uchta "keyingisi" bor. Bunday pog'onali tuzilish — ierarxiya: umumiy narsa tepada, uning ichidagilar ostida. Uni bitta ro'yxatga yozsangiz, ierarxiya yo'qoladi: "olma — sharbatmi yoki taommi?" degan savolga javob berib bo'lmaydi. Bunday tuzilma — daraxt. Nomi rasmdan: bitta tanadan shoxlar, shoxlardan yana shoxchalar tarqaladi — faqat biz uni teskari, ildizini tepada chizamiz.

Jasur aka Sardordan menyu haqida oddiy savollar so'raydi: "Menyuda nechta nom bor?", "Qaysilari haqiqiy taom, qaysilari faqat bo'lim?", "Eng ichkaridagi nom necha pog'ona pastda?". Bu savollarga javob berish uchun avval daraxtning "tilini" o'rganamiz. Keyin har savolga bitta qisqa rekursiv funksiya yozamiz.

Siz daraxtni allaqachon ko'p ishlatgansiz. DOM daraxti — HTML elementlari daraxti. Kompyuterdagi papkalar — daraxt. Ichma-ich JSON — daraxt. 12-qismda ESLint ishlatgan AST (abstrakt sintaksis daraxti) ham daraxt. Bugun ularning umumiy tilini o'rganamiz. Keyingi darslarda shu til bilan daraxt bo'ylab yurish, qidiruv daraxti va heap quriladi.

2. Atamalar

2.1 Tugun, qirra, ildiz

Rasmga qarab birma-bir:

• Tugun (node) — daraxtning bitta elementi: "Menyu", "osh", "Sharbatlar". DOM'dagi tugun bilan bir xil ma'no.
• Qirra (edge) — ikki tugunni bog'laydigan chiziq: "Taomlar — osh". n ta tugunli daraxtda aniq n − 1 ta qirra bor: ildizdan boshqa har tugun otasiga bitta qirra bilan ulangan.
• Ildiz (root) — eng yuqoridagi, otasi yo'q tugun: "Menyu". Daraxtda u faqat bitta.
• Ota (parent) va bola (child) — qirra bilan bog'langan ikki tugun: "Taomlar" — "osh" ning otasi, "osh" — "Taomlar" ning bolasi. Har tugunning (ildizdan tashqari) aniq bitta otasi bor.
• Aka-uka (siblings) — otasi bir xil tugunlar: "osh", "lag'mon", "manti".
• Barg (leaf) — bolasi yo'q tugun: "osh", "lag'mon", "manti", "ko'k choy", "olma". Bolasi bor tugun — ichki tugun (internal node).

Ota, bola va aka-uka atamalarini DOM darsidan eslaysiz — ma'nosi aynan shu.

2.2 Yo'l, chuqurlik, balandlik

• Yo'l (path) — qirralar bo'ylab bir tugundan boshqasiga ketma-ketlik: "Menyu → Ichimliklar → Sharbatlar → olma". Daraxtda ikki tugun orasida yo'l faqat bitta.
• Chuqurlik (depth) — ildizdan tugungacha qirralar soni. "Menyu" — 0, "Taomlar" — 1, "osh" — 2, "olma" — 3. Bir xil chuqurlikdagi tugunlar — bitta qavat (level): binoning qavatlari kabi, ildiz — eng yuqori qavat.
• Balandlik (height) — tugundan eng uzoq bargigacha qirralar soni. Barg balandligi — 0. Daraxtning balandligi = ildizning balandligi = eng chuqur barg chuqurligi. Bizning menyuda — 3.

Chuqurlik va balandlikni farqlash uchun binoni eslang. Chuqurlik — "tepadan necha qavat pastga tushdim?". Balandlik — "mendan pastda yana necha qavat bor?".

Nega balandlik shunchalik muhim? Keyingi darslardagi ko'p amallar ildizdan bargga bitta yo'l bo'ylab tushadi. Har qadamda bitta qavat pastga. Demak, amal vaqti daraxt balandligiga teng. Past daraxtda — tez, baland daraxtda — sekin. Buni dars oxirida o'lchab ko'ramiz.

Diqqat: Ba'zi kitoblar balandlikni tugunlar (qavatlar) soni bilan sanaydi: unda bitta tugunli daraxt balandligi 1, bo'sh daraxt — 0. Bu kursning asosiy kelishuvi — qirralar soni: bitta tugun — 0, bo'sh daraxt — −1. Ikkalasi bittaga farq qiladi: qavatlar soni = balandlik + 1. Ba'zi darslarda (AVL daraxt, diametr) qavatlar bilan sanash qulayroq — u yerda buni alohida aytamiz. Masala shartini o'qiganda qaysi kelishuv ishlatilganini tekshiring.

2.3 Kichik daraxt va rekursiya

Tugunning avlodlari — uning bolalari, bolalarining bolalari va shu tarzda eng pastgacha. Teskarisi — ajdodlar: otasi, otasining otasi va shu tarzda ildizgacha. "olma" ning ajdodlari — "Sharbatlar", "Ichimliklar", "Menyu".

Kichik daraxt (subtree) — biror tugun va uning hamma avlodlari. "Ichimliklar" kichik daraxti: "Ichimliklar", "ko'k choy", "Sharbatlar", "olma". Muhim kuzatuv: kichik daraxt ham daraxt — o'z ildizi bilan.

Bu kuzatuv daraxt bilan ishlashning kalitini beradi. "Menyu daraxtining balandligi qancha?" degan savol kichikroq savollarga bo'linadi: "Taomlar daraxtining balandligi?", "Ichimliklar daraxtining balandligi?" — keyin eng kattasiga 1 qo'shamiz. Bu — Rekursiv fikrlash darsidagi ishonch sakrashi: bolalar o'z javobini to'g'ri beradi deb ishonamiz.

«Bahor»da bu shunday ko'rinardi. Jasur aka menyudagi nomlarni o'zi sanamaydi. U ikki bo'lim mas'uliga savol beradi. "Taomlar" mas'uli: "Menda 4 ta: bo'lim nomi va 3 ta taom". "Ichimliklar" mas'uli ham o'z bo'limini xuddi shunday sanab, 4 deydi. Jasur aka "Menyu" ning o'zini ham qo'shadi: 1 + 4 + 4 = 9. Har mas'ul ham ichidagilarni xuddi shu yo'l bilan sanagan. Rekursiv funksiya aynan shunday ishlaydi.

Tekshirib ko'ring: Menyu daraxtida nechta tugun, nechta qirra va nechta barg bor? "Sharbatlar" ning chuqurligi va balandligi qancha?

3. Daraxt JavaScript'da

3.1 Umumiy daraxt: children massivi

Har tugun — obyekt: nomi (name) va bolalari ro'yxati (children). Barg — bolalar ro'yxati bo'sh ([]) tugun. Ichma-ich obyekt va massivni siz JSON darsidan bilasiz — daraxt aynan shunday yoziladi.

Kodni yozishdan oldin uchta savolga qog'ozda javob beraylik. Har birida avval eng pastdagi barglardan boshlaymiz:

• Nechta tugun? Har barg — 1. "Sharbatlar" — o'zi va "olma": 2. "Ichimliklar" — 1 + 1 + 2 = 4. "Taomlar" — 1 + 3 = 4. "Menyu" — 1 + 4 + 4 = 9.
• Qaysilari barg? Bolasi yo'q tugunlar: osh, lag'mon, manti, ko'k choy, olma.
• Balandlik? Barg — 0. "Taomlar" — eng baland bolasi 0, demak 0 + 1 = 1. "Sharbatlar" — 1. "Ichimliklar" — bolalari 0 va 1, kattasi 1, demak 2. "Menyu" — bolalari 1 va 2, demak 3.

Endi xuddi shu hisobni kodga aylantiramiz:

// «Bahor» menyusi — daraxt: har tugunda nom va bolalar ro'yxati
const menu = {
  name: "Menyu",
  children: [
    {
      name: "Taomlar",
      children: [
        { name: "osh", children: [] },
        { name: "lag'mon", children: [] },
        { name: "manti", children: [] },
      ],
    },
    {
      name: "Ichimliklar",
      children: [
        { name: "ko'k choy", children: [] },
        {
          name: "Sharbatlar",
          children: [{ name: "olma", children: [] }],
        },
      ],
    },
  ],
};

function countNodes(node) {
  let total = 1; // tugunning o'zi
  for (const child of node.children) total += countNodes(child);
  return total;
}

function leaves(node) {
  if (node.children.length === 0) return [node.name]; // barg
  return node.children.flatMap(leaves);
}

function height(node) {
  let best = -1; // bolasi yo'q bo'lsa: -1 + 1 = 0
  for (const child of node.children) {
    best = Math.max(best, height(child));
  }
  return best + 1;
}

console.log(countNodes(menu));
console.log(leaves(menu));
console.log(height(menu));

Konsolda:

9
[ 'osh', "lag'mon", 'manti', "ko'k choy", 'olma' ]
3

Uchala funksiya bir xil shaklda:

1. Tugunning o'zi uchun ish (1, [node.name], + 1).
2. Har bola uchun o'zini chaqirish.
3. Natijalarni birlashtirish (yig'ish, yoyish, eng kattasini olish).

flatMap(leaves) — har boladan barglar ro'yxatini olib, bitta ro'yxatga yoyadi (flat va flatMap). Node apostrofli satrni qo'shtirnoqda ko'rsatadi ("lag'mon") — qiymat bir xil.

height dagi best = -1 ga e'tibor bering. Barg uchun sikl bir marta ham aylanmaydi va best −1 bo'lib qoladi. Natija −1 + 1 = 0 — aynan barg balandligi. Shu bitta qiymat tufayli barg uchun alohida if yozmadik.

3.2 Balandlikni qadamma-qadam kuzatamiz

height ni kuzating. Stekda qaysi chaqiruvlar ochiq ekaniga va tugun yonida paydo bo'ladigan h= belgisiga qarang:

Har tugun bir marta ko'rildi: avval pastga tushdik, keyin javoblar yuqoriga ko'tarildi. Barglar 0 qaytaradi, har ota esa bolalarining eng kattasiga 1 qo'shadi. n ta tugunli daraxtda — O(n) vaqt. Stekda bir vaqtda ko'pi bilan "ildizdan joriy tugungacha" bo'lgan chaqiruvlar turadi. Ularning soni daraxt balandligi bilan bir tartibda. Balandlikni h harfi bilan belgilaymiz, shuning uchun stek xotirasi — O(h).

3.3 Chuqurlikni topish

Jasur akaning yana bir savoli: "olma" menyuning necha pog'ona ichkarisida? Bu — chuqurlik. U teskari yo'nalishda sanaladi: ildizdan pastga. Har pastga tushganda hisoblagichni bittaga oshirib, uni bolaga parametr qilib beramiz.

Qog'ozda: "Menyu" dan 0 bilan boshlaymiz. "Taomlar" (1) ichida olma yo'q — u "topilmadi" (−1) deb qaytadi. "Ichimliklar" (1) → "ko'k choy" (2) — yo'q → "Sharbatlar" (2) → "olma" (3) — topildi. 3 soni yuqoriga, ildizgacha uzatiladi:

function depthOf(node, name, depth = 0) {
  if (node.name === name) return depth;
  for (const child of node.children) {
    const d = depthOf(child, name, depth + 1);
    if (d !== -1) return d; // topildi — yuqoriga uzatamiz
  }
  return -1; // bu kichik daraxtda yo'q
}

console.log(depthOf(menu, "olma")); // 3
console.log(depthOf(menu, "Taomlar")); // 1
console.log(depthOf(menu, "somsa")); // -1

height javobni pastdan yuqoriga yig'adi (bolalardan otaga). depthOf ma'lumotni yuqoridan pastga uzatadi (otadan bolaga, parametr orqali). Daraxt masalalarining ko'pi shu ikki yo'nalishdan biri.

3.4 Tekis ro'yxatdan daraxt qurish

Real ilovada daraxt ko'pincha tayyor ichma-ich obyekt bo'lib kelmaydi. Ma'lumotlar bazasida menyu kategoriyalari jadval sifatida saqlanadi: har qatorda o'z id si va otasining parentId si. Ildizning otasi yo'q — null. Frontend bu tekis ro'yxatdan daraxt yasashi kerak.

Sodda yo'l — har tugun uchun butun ro'yxatdan bolalarini qidirish: n ta tugun × n ta qator = O(n²). Yaxshisi — Map bilan ikki o'tish (Hash map bilan hisoblash):

// bazadan kelgan tekis ro'yxat: har qatorda o'z id va ota id
const rows = [
  { id: 1, parentId: null, name: "Menyu" },
  { id: 2, parentId: 1, name: "Taomlar" },
  { id: 3, parentId: 1, name: "Ichimliklar" },
  { id: 4, parentId: 2, name: "osh" },
  { id: 5, parentId: 3, name: "ko'k choy" },
  { id: 6, parentId: 2, name: "manti" },
];

function buildTree(rows) {
  const byId = new Map();
  for (const row of rows) {
    byId.set(row.id, { name: row.name, children: [] });
  }
  let root = null;
  for (const row of rows) {
    const node = byId.get(row.id);
    if (row.parentId === null) root = node; // otasi yo'q — ildiz
    else byId.get(row.parentId).children.push(node);
  }
  return root;
}

const tree = buildTree(rows);
console.log(tree.children.map((c) => c.name));
console.log(tree.children[0].children.map((c) => c.name));

Konsolda:

[ 'Taomlar', 'Ichimliklar' ]
[ 'osh', 'manti' ]

Qog'ozda kuzatamiz. Birinchi o'tishdan keyin Map da oltita bolasiz tugun bor: 1 → "Menyu", 2 → "Taomlar", 3 → "Ichimliklar" va qolgan uchta taom. Ikkinchi o'tishda: "Menyu" ning parentId si null — u ildiz. "Taomlar" ning otasi 1 — uni "Menyu" ning children iga qo'shamiz. "osh" ning otasi 2 — "Taomlar" ga. Oxirida "Taomlar" da ikki bola: osh va manti.

Birinchi o'tish har qator uchun bo'sh tugun yaratadi va uni id bo'yicha Map ga qo'yadi. Ikkinchi o'tish har tugunni otasining children iga ulaydi — otani Map dan O(1) da topamiz. Jami O(n). Qatorlar qaysi tartibda kelishi muhim emas: bola otasidan oldin kelsa ham ishlaydi, chunki hamma tugun birinchi o'tishda yaratilgan.

Bu jadvaldagi parentId — "ota havolasi". Bizning obyektlarda esa aksincha, otada bolalar ro'yxati bor. Ikkala yo'nalish ham bitta daraxtni ifodalaydi; qaysi biri qulay — savolga bog'liq. "Bu kategoriyaning bolalari kim?" — children. "Bu taom qaysi bo'limda?" — parentId.

4. Binar daraxt

4.1 Ko'pi bilan ikki bola

Jasur aka kirish eshigi yoniga kichik ekran qo'ymoqchi: ikkilanib turgan mehmonga taom tanlashda yordam bersin. Sardor uni savollar daraxti qilib chizdi. Har savolga faqat ikki javob bor: chapga — "ha", o'ngga — "yo'q":

          go'shtlimi?
          /         \
    guruchlimi?   ko'k choy
      /     \
    osh   lag'mon

Har savol tugunida aniq ikki yo'l bor, javob tugunlari esa barg. Bunday daraxtda "nechta bola?" degan savol yo'q: bola ko'pi bilan ikkita va ularning nomi doim bir xil — chap va o'ng.

Binar daraxt (binary tree) — har tugunda ko'pi bilan ikkita bola: chap (left) va o'ng (right). Bola yo'q bo'lsa — null. Nega bu qulay? children massivi o'rniga ikkita aniq maydon: sikl kerak emas, "chapga yoki o'ngga" degan tanlov esa ko'p algoritmlarning asosi. Kelasi darslardagi ko'p tuzilmalar — Binary Search Tree, Heap — aynan binar daraxt.

Bog'langan ro'yxatni eslang: tugunda value va next. Binar daraxt tuguni — value, left, right. Ya'ni bog'langan ro'yxat — har tugunda faqat bitta bola bo'lgan "daraxt".

Tugun yasash uchun kichik yordamchi funksiya yozamiz. U keyingi darslarda ham shu ko'rinishda qatnashadi:

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

const leaf = node(5);
console.log(leaf); // { value: 5, left: null, right: null }

node(5) — bargni yasaydi: left va right uchun default qiymat null. node(28, chap, o'ng) — ikki bolali tugun. Arrow funksiya obyekt qaytarganda uni ({ … }) qavsga olish kerak — aks holda { funksiya tanasi deb o'qiladi (arrow funksiyalar).

Endi narxlar daraxtini quramiz (ming so'mda) va tugunlarni sanaymiz. Qavslar ichi daraxt shaklini takrorlaydi: node(28, node(12, …), node(35, …)) — 28 ning chapida 12, o'ngida 35. Avval qog'ozda: 5 va 18 — barg, har biri 1. 12 — o'zi + 1 + 1 = 3. 40 — 1. 35 — o'zi + 0 (chapi bo'sh) + 1 = 2. 28 — o'zi + 3 + 2 = 6. Endi kod xuddi shu yo'ldan yurishini kuzating:

countNodes ning asos holati — null: bo'sh daraxtda 0 ta tugun. Bu umumiy daraxtdagidan qisqaroq: "bola bormi?" deb tekshirmaymiz, null bilan ham chaqirib, uni asos holatda ushlaymiz.

4.2 Balandlik, barglar

Xuddi shu narxlar daraxtida balandlik va barglarni topamiz. Qog'ozda: barglar — 5, 18 va 40, ya'ni 3 ta. Eng uzun yo'l — 28 → 12 → 5 (yoki 28 → 35 → 40): 2 ta qirra, demak balandlik 2. Kod ham "o'zi + chap + o'ng" shaklida, faqat yig'ish o'rniga kattasini olamiz:

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

function height(t) {
  if (t === null) return -1; // bo'sh daraxt
  return 1 + Math.max(height(t.left), height(t.right));
}

function countLeaves(t) {
  if (t === null) return 0;
  if (t.left === null && t.right === null) return 1; // barg
  return countLeaves(t.left) + countLeaves(t.right);
}

const root = node(28,
  node(12, node(5), node(18)),
  node(35, null, node(40)));
console.log(height(root), countLeaves(root)); // 2 3
console.log(height(node(7)), height(null)); // 0 -1

Bo'sh daraxt balandligi −1 bo'lgani juda qulay: barg uchun 1 + Math.max(-1, -1) = 0 — alohida shart kerak emas. countLeaves da esa barg sharti kerak: ikkala bola ham null bo'lsa — bu barg, 1 qaytaramiz. Aks holda chap va o'ng shoxdagi barglarni qo'shamiz.

5. Binar daraxt turlari

5.1 To'la, to'liq, mukammal

Uch tur ko'p chalkashtiriladi, chunki nomlari o'xshash. «Bahor» zalidagi stollarni tasavvur qiling: har stolga 0 yoki 2 ta stul qo'yiladi. Bitta stulli stol yo'q — bu "to'la" qoidasiga o'xshaydi. Zalni chapdan o'ngga, qatorma-qator bo'shliqsiz to'ldirish — "to'liq". Hamma qator oxirigacha band — "mukammal". Endi daraxt tilida, bitta jadvalda:

   to'la             to'liq            mukammal
     A                 A                  A
    / \              /   \              /   \
   B   C            B     C            B     C
      / \          / \   /            / \   / \
     D   E        D   E F            D   E F   G

Rasmlarni qoidalar bilan solishtiring. Birinchisi to'la, lekin to'liq emas: B da bola yo'q, C da esa bor — oxirgi qavat chapdan to'ldirilmagan. Ikkinchisi to'liq, lekin to'la emas: C ning faqat bitta bolasi (F) bor. Uchinchisida ikkala qoida ham bajarilgan.

Mukammal daraxt ham to'la, ham to'liq. To'liq daraxt — Heap ning shakli: u massivda bo'shliqsiz saqlanadi.

5.2 Tugunlar va balandlik

Mukammal daraxtda har qavat oldingisidan ikki baravar ko'p tugun saqlaydi: 1, 2, 4, 8… h balandlikdagi mukammal daraxtda jami 2^(h+1) − 1 ta tugun. Tekshiring: h = 2 da 1 + 2 + 4 = 7, formula bo'yicha 2³ − 1 = 8 − 1 = 7. Yana bitta qavat qo'shilsa, 8 ta tugun keladi: 7 + 8 = 15 = 2⁴ − 1.

Teskarisi: n ta tugunni sig'dirish uchun balandlik taxminan log₂ n bo'lsa yetadi. log₂ n — "n ni necha marta ikkiga bo'lsak, 1 qoladi" degan son. Million tugun — taxminan 20 qavat (balandlik 19). Bu yana o'sha logarifm — ikkiga bo'lib qidirish dagidek.

Endi teskari chekka holat. Har tugunda faqat bitta bola bo'lsa, daraxt zanjirga (bog'langan ro'yxatga) aylanadi: n ta tugun — n − 1 balandlik. Bunday daraxt buzilgan (degenerate) yoki zanjirsimon deyiladi. Ikkala shaklni bir xil n bilan quramiz va balandligini solishtiramiz. balanced(1, n) 1 dan n gacha sonlarni oladi va o'rtadagisini tugun qiladi. Chap yarmidan chap shoxni, o'ng yarmidan o'ng shoxni xuddi shu yo'l bilan yasaydi. chain(n) esa har yangi tugunga oldingi zanjirni o'ng bola qilib beradi:

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

function height(t) {
  if (t === null) return -1; // bo'sh daraxt
  return 1 + Math.max(height(t.left), height(t.right));
}

// muvozanatli: har tugun oraliqni teng ikkiga bo'ladi
function balanced(lo, hi) {
  if (lo > hi) return null;
  const mid = Math.floor((lo + hi) / 2);
  return node(mid, balanced(lo, mid - 1), balanced(mid + 1, hi));
}

// zanjir: har tugunning faqat o'ng bolasi bor
function chain(n) {
  let root = null;
  for (let v = n; v >= 1; v--) root = node(v, null, root);
  return root;
}

for (const n of [7, 1000, 1_000_000]) {
  console.log(`n=${n}: muvozanatli h=${height(balanced(1, n))}`);
}
console.log(`n=1000: zanjir h=${height(chain(1000))}`);

Konsolda:

n=7: muvozanatli h=2
n=1000: muvozanatli h=9
n=1000000: muvozanatli h=19
n=1000: zanjir h=999

Bir xil 1 000 ta tugun: muvozanatli daraxtda balandlik 9, zanjirda — 999. Keyingi darslarda ko'ramiz: qidiruv daraxtida qidiruv vaqti balandlikka teng. Muvozanatli daraxtda — O(log n), zanjirda — O(n). Shuning uchun daraxtni muvozanatda saqlash (Balanslangan daraxtlar) butun bir mavzu.

Tekshirib ko'ring: Balandligi 3 bo'lgan mukammal binar daraxtda nechta tugun va nechta barg bor?

6. O'lchov: n ikki baravar oshsa

Nazariya "O(n)" deydi. Haqiqatan shundaymi? countNodes ni muvozanatli binar daraxtda Performansni o'lchash darsidagi usul bilan o'lchadik. Har n alohida jarayonda ishga tushdi, avval funksiya "isitildi", keyin 7 o'lchovning medianasi olindi. Daraxt o'lchovdan oldin qurildi — vaqtga faqat sanash kiradi:

n 8 baravar — vaqt 8,4 baravar: chiziqli. Birinchi qadamdagi ×1,6 — kichik daraxtning protsessor keshiga to'liq sig'ishidan; katta daraxtlarda tugunlar xotirada sochilib yotadi va har murojaat biroz qimmatroq. Daraxtda har tugun alohida obyekt — massivdagi kabi ketma-ket emas (Massiv xotirada).

7. Chegaraviy holatlar

Ikkinchi qatorga qarang: bitta tugunli daraxtda ildiz bir vaqtda barg ham. Testlarda bu holatni albatta sinang.

8. Ko'p uchraydigan xatolar

8.1 Zanjirsimon daraxtda rekursiya

Rekursiya chuqurligi daraxt balandligiga teng. Muvozanatli daraxtda bu 20–30 — muammo yo'q. Zanjirda esa n:

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

function height(t) {
  if (t === null) return -1;
  return 1 + Math.max(height(t.left), height(t.right));
}

let root = null;
// zanjir: 100 000 tugun
for (let v = 100000; v >= 1; v--) root = node(v, null, root);
console.log(height(root));

Konsolda:

RangeError: Maximum call stack size exceeded

Bizda (Node 24) 8 000 tugunli zanjir ishladi, 10 000 tasi — yo'q. Aniq chegara funksiyaga bog'liq: har chaqiruv stekda qancha joy olishiga va V8 funksiyani optimallashtirgan-optimallashtirmaganiga qarab. Keyingi darsdagi sumTree taxminan 11 000–13 800 chuqurlikda yiqiladi. Bitta raqamga tayanmang — tartibi o'n minglar. Tuzatish: chuqur daraxtlar uchun rekursiyani stek bilan iterativ yurishga almashtirish (Daraxt bo'ylab yurish: DFS va BFS) yoki daraxtni muvozanatda saqlash.

8.2 null ni tekshirmaslik

t.left.value — agar t.left null bo'lsa: TypeError: Cannot read properties of null (reading 'value'). Tuzatish: asos holatni null uchun yozing va funksiyani null bilan ham chaqirishga ruxsat bering — kod qisqaradi.

8.3 Balandlik kelishuvini aralashtirish

Bir joyda barg balandligi 0, boshqa joyda 1 — natijalar bittaga siljiydi. Tuzatish: bo'sh daraxt −1, barg 0 — butun loyihada bitta kelishuv.

8.4 Sikl bor "daraxt"

Ikki tugun bir-biriga bola sifatida havola qilsa, bu daraxt emas — graf. Rekursiv countNodes cheksiz aylanadi va stek to'ladi. JSON'da sikl bo'lishi mumkin emas, lekin obyektlarda — mumkin (aylanma havola). Sikllarni grafik darslarida (Graf atamalari) ko'ramiz.

9. Mashqlar

1-mashq (oson): Atamalarni toping

Fayl tizimi: loyiha/ ichida src/ va README.md; src/ ichida index.js va utils/; utils/ ichida format.js. Daraxtning balandligi qancha?

2-mashq (o'rta): Menyudagi eng chuqur taom

Darsdagi menu daraxti uchun deepestPath(node) funksiyasini yozing: ildizdan eng chuqur bargigacha yo'lni nomlar massivi sifatida qaytarsin. Ishora: har bola uchun yo'lni so'rang va eng uzunini oling, keyin oldiga o'zingizni qo'shing.

const menu = {
  name: "Menyu",
  children: [
    {
      name: "Taomlar",
      children: [
        { name: "osh", children: [] },
        { name: "manti", children: [] },
      ],
    },
    {
      name: "Ichimliklar",
      children: [
        {
          name: "Sharbatlar",
          children: [{ name: "olma", children: [] }],
        },
      ],
    },
  ],
};

function deepestPath(node) {
  let best = [];
  for (const child of node.children) {
    const path = deepestPath(child);
    if (path.length > best.length) best = path;
  }
  return [node.name, ...best];
}

console.log(deepestPath(menu).join(" → "));
// Menyu → Ichimliklar → Sharbatlar → olma

3-mashq (qiyin): Binar daraxt funksiyalari va testlar

kurs/mashqlar/14/36-daraxt/daraxt.test.mjs faylida binar daraxt uchun countNodes, height, countLeaves, isFull (to'la: har tugunda 0 yoki 2 bola) va isPerfect (mukammal: n = 2^(h+1) − 1) ni yozing. Testlar (node:test):

1. Bo'sh daraxt va bitta tugun.
2. 7 tugunli mukammal daraxt: balandlik 2, barglar 4, to'la va mukammal.
3. Bitta bolasi yo'q daraxt: to'la ham, mukammal ham emas.
4. To'la binar daraxtda barglar = ichki tugunlar + 1.

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

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

function countNodes(t) {
  if (t === null) return 0;
  return 1 + countNodes(t.left) + countNodes(t.right);
}

function height(t) {
  if (t === null) return -1; // bo'sh daraxt
  return 1 + Math.max(height(t.left), height(t.right));
}

function countLeaves(t) {
  if (t === null) return 0;
  if (t.left === null && t.right === null) return 1;
  return countLeaves(t.left) + countLeaves(t.right);
}

// to'la (full): har tugunda 0 yoki 2 bola
function isFull(t) {
  if (t === null) return true;
  if ((t.left === null) !== (t.right === null)) return false;
  return isFull(t.left) && isFull(t.right);
}

// mukammal (perfect): n = 2^(h+1) − 1
function isPerfect(t) {
  return countNodes(t) === 2 ** (height(t) + 1) - 1;
}

// narxlar (ming so'm)
const perfect = node(28, node(12, node(5), node(18)),
  node(35, node(30), node(40)));
const lopsided = node(28, node(12, node(5), node(18)),
  node(35, null, node(40)));

test("chegaraviy: bo'sh daraxt va bitta tugun", () => {
  assert.equal(countNodes(null), 0);
  assert.equal(height(null), -1);
  assert.equal(height(node(7)), 0);
  assert.equal(countLeaves(node(7)), 1);
  assert.ok(isPerfect(node(7)));
});

test("mukammal daraxt: 7 tugun, balandlik 2, 4 barg", () => {
  assert.equal(countNodes(perfect), 7);
  assert.equal(height(perfect), 2);
  assert.equal(countLeaves(perfect), 4);
  assert.ok(isFull(perfect) && isPerfect(perfect));
});

test("bitta bolasi yo'q: to'la ham, mukammal ham emas", () => {
  assert.equal(countNodes(lopsided), 6);
  assert.equal(countLeaves(lopsided), 3);
  assert.equal(isFull(lopsided), false);
  assert.equal(isPerfect(lopsided), false);
});

test("to'la binar daraxtda barglar = ichki tugunlar + 1", () => {
  const full = node(1, node(2), node(3, node(4), node(5)));
  assert.ok(isFull(full));
  const leafCount = countLeaves(full);
  assert.equal(leafCount, countNodes(full) - leafCount + 1);
});

✔ chegaraviy: bo'sh daraxt va bitta tugun (0.777ms)
✔ mukammal daraxt: 7 tugun, balandlik 2, 4 barg (0.1746ms)
✔ bitta bolasi yo'q: to'la ham, mukammal ham emas (0.1129ms)
✔ to'la binar daraxtda barglar = ichki tugunlar + 1 (0.0997ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 83.6408

4-mashq: Amaliy tajriba — jadvalga uch qator

kurs/mashqlar/14/MURAKKABLIK.md ga daraxt amallarini qo'shing: tugunlarni sanash, balandlik, chuqurlikni topish. Vaqt va xotira (stek) ustunlarini h (balandlik) bilan yozing.

| Masala | Yechim | Vaqt | Xotira | Izoh |
|---|---|---|---|---|
| Daraxt tugunlarini sanash | rekursiya: 1 + bolalar | O(n) | O(h) stek | h — balandlik |
| Daraxt balandligi | 1 + max(bolalar) | O(n) | O(h) stek | zanjirda h = n − 1 |
| Tugun chuqurligi | parametr bilan pastga | O(n) | O(h) stek | topilsa — erta qaytish |

git add 14/MURAKKABLIK.md 14/36-daraxt
git commit -m "14/36: daraxt atamalari va binar daraxt"

10. Real ishda

• Frontend. DOM — daraxt; React komponentlari ham daraxt hosil qiladi (kursda keyin o'rganamiz). Ichma-ich izohlar (Telegram'dagi javoblar zanjiri), menyular, kategoriyalar — hammasi children massivli daraxt sifatida keladi va rekursiv komponent bilan chiziladi.
• Backend va ma'lumotlar. Fayl tizimi, JSON hujjatlar, ma'lumotlar bazasi indekslari (B-tree) — daraxt. Tashkilot tuzilmasi (direktor → bo'lim → xodim) jadvalda parent_id ustuni bilan saqlanadi va daraxt sifatida o'qiladi.
• Asboblar. ESLint, Prettier, Babel kodni AST ga aylantirib, daraxt bo'ylab yuradi. Git commit'larni daraxt (aniqrog'i graf) sifatida saqlaydi.
• Intervyu. "Binar daraxtning balandligini toping" (LeetCode 104), "barglar sonini toping", "to'la va to'liq daraxt farqi nima?" — boshlang'ich savollar. Javobning shabloni bitta: asos holat null, keyin "o'zi + chap + o'ng".

Xulosa

• Daraxt — ildizli, siklsiz ierarxiya: n tugun, n − 1 qirra, har tugunning (ildizdan tashqari) bitta otasi.
• Chuqurlik — ildizdan tugungacha, balandlik — tugundan eng uzoq bargigacha (qirralar soni; bo'sh daraxt −1, barg 0).
• Daraxt funksiyalari rekursiv: tugunning o'zi + bolalarning javoblari. Vaqt O(n), stek O(h).
• Binar daraxt: left/right. To'la — 0 yoki 2 bola; to'liq — qatlamlar chapdan to'la; mukammal — 2^(h+1) − 1 tugun.
• Muvozanatli daraxtda h ≈ log₂ n, zanjirda h = n − 1 — va chuqur rekursiya stekni to'ldiradi.

Keyingi dars: Daraxt bo'ylab yurish: DFS va BFS — tugunlarni qaysi tartibda ko'rish (preorder, inorder, postorder, qatlam bo'yicha) va rekursiyasiz, stek hamda navbat bilan yurish.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — B ilova (daraxtlar).
• Donald Knuth, "The Art of Computer Programming", 1-jild, 2-bob — daraxtlar va atamalar.
• MDN: "Using the Document Object Model" — DOM daraxti — developer.mozilla.org