Binary Search Tree (BST): qidirish, qo'shish va o'chirish JavaScript'da

Qisqacha: Binary search tree (BST) — har tugunning chap shoxida undan kichik, o'ng shoxida undan katta qiymatlar turadigan binar daraxt. Qidirishda har qadamda bitta shox tashlanadi, shuning uchun qidirish, qo'shish va o'chirish daraxt balandligiga teng vaqt oladi — O(h). Tasodifiy tartibda kelgan ma'lumotda h ≈ log n, lekin saralangan ma'lumotda daraxt ro'yxatga aylanib, h = n bo'ladi. Inorder yurish BST qiymatlarini o'sish tartibida beradi.

Bu darsda

• BST qoidasini aniq ayta olasiz va daraxt BST ekanini to'g'ri tekshira olasiz.
• Qidirish, qo'shish va o'chirishni (uchala holati bilan) yoza olasiz.
• Nega inorder BST'da saralangan ro'yxat berishini tushuntira olasiz.
• BST'ni saralangan va saralanmagan massiv bilan o'lchab solishtirasiz va uning zaif joyini ko'rasiz.

Oldin bilishingiz kerak: Daraxt bo'ylab yurish: DFS va BFS, Binary search asoslari, Klasslar.

1. Nega bu kerak?

«Bahor»da kun davomida buyurtmalar kelib turadi, ba'zilari bekor qilinadi. Kassa dasturi to'rt ishni tez qilishi kerak:

1. Buyurtma raqami ro'yxatda bormi?
2. Yangi raqamni qo'shish.
3. Bekor qilinganini o'chirish.
4. Kun oxirida hammasini tartib bilan chiqarish.

Sardor ikkita tanish yechimni sinadi. Saralanmagan massivda qo'shish tez (push), lekin qidirish — hammasini ko'rish, O(n). Saralangan massivda qidirish tez — ikkiga bo'lib qidirish, O(log n). Lekin qo'shish va o'chirish sekin: yangi raqamni o'rtaga qo'yish uchun undan keyingi hamma elementni bir katak suradi, O(n).

Bitta tuzilma kerak: ham saralangan massivdek tez qidirsin, ham elementni surmasdan qo'shsin. Bugungi javob — binary search tree. U ikkiga bo'lib qidirish g'oyasini daraxt shakliga keltiradi: "o'rtadagi element" — tugun, "chap yarmi" va "o'ng yarmi" — uning shoxlari.

«Bahor» tilida tasavvur qiling. Sardor kassa yonidagi buyurtma qog'ozlarini ikki qutiga ajratadi. O'rtaga 50-raqamli qog'ozni qo'yadi: undan kichik raqamlar — chap qutiga, kattalari — o'ng qutiga. Har quti ichida ham xuddi shunday: bitta "o'rtadagi" qog'oz va yana ikki kichik quti. Endi 45-buyurtmani izlash uchun o'ng qutini umuman ochmaydi — 45 baribir chapda.

2. BST qoidasi

Binary search tree (BST — ikkilik qidiruv daraxti) — binar daraxt, unda har bir tugun uchun:

• chap shoxdagi hamma qiymatlar undan kichik;
• o'ng shoxdagi hamma qiymatlar undan katta.

"Hamma" so'ziga e'tibor bering — faqat bevosita bolalar emas, butun shox. Darsdagi daraxt — 10 ta buyurtma raqami:

               50
           /        \
         30          70
        /  \        /  \
      20    40    60    80
           /  \     \
         35    45    65

Tekshirib ko'ring: 50 ning chap shoxida 30, 20, 40, 35, 45 — hammasi 50 dan kichik. 40 ning chap shoxida 35 — kichik, o'ngida 45 — katta. Qoida har tugunda bajariladi.

Bitta tanlov qilishimiz kerak: takroriy qiymat nima bo'ladi? Buyurtma raqamlari takrorlanmaydi, shuning uchun bizning BST takrorni qo'shmaydi — Set kabi. Boshqa tanlovlar ham bor: tugunda hisoblagich saqlash yoki tengini doim o'ngga qo'yish. Asosiysi — bitta qoidani tanlab, hamma joyda unga amal qilish.

3. Qidirish

Izlangan qiymatni ildiz bilan solishtiramiz. Teng — topildi. Kichik — javob faqat chap shoxda bo'lishi mumkin, o'ng shoxni butunlay tashlaymiz. Katta — aksincha. Keyin xuddi shu savolni bolada beramiz. Bo'sh joyga (null) yetsak — qiymat yo'q.

Avval qog'ozda qidiramiz:

• 45: 50 dan kichik — chapga, 30 ga; 30 dan katta — o'ngga, 40 ga; 40 dan katta — o'ngga, 45 ga. Topildi.
• 55: 50 dan katta — o'ngga, 70 ga; 70 dan kichik — chapga, 60 ga; 60 dan kichik — chapga, lekin u yerda null. Yo'q.

Kuzating — vizual xuddi shu ikki qidiruvni ko'rsatadi. Kulrang — tashlangan yo'l:

45 uchun to'rtta, 55 uchun uchta solishtirish. 10 ta raqamdan. Kodda while sikli bor, rekursiya yo'q — chuqur daraxtda ham stek to'lmaydi (o'tgan darsdagi saboq).

Shartli operator qatoriga qarang: value < current.value ? current.left : current.right. Bu "kichik bo'lsa chapga, aks holda o'ngga" degani (Shartli (ternary) operator).

Xuddi shu qidiruvni rekursiya bilan ham yozish mumkin. U BST ta'rifini so'zma-so'z takrorlaydi: "bo'sh daraxtda yo'q; ildizda bo'lsa — bor; aks holda kerakli shoxda qidir":

const node = (value, left = null, right = null) =>
  ({ value, left, right });
const root = node(50,
  node(30, node(20), node(40, node(35), node(45))),
  node(70, node(60, null, node(65)), node(80)));

function contains(current, value) {
  if (current === null) return false; // bo'sh joyga yetdik
  if (value === current.value) return true;
  if (value < current.value) return contains(current.left, value);
  return contains(current.right, value);
}

console.log(contains(root, 35), contains(root, 36)); // true false

Ikkala variant bir xil ishlaydi va bir xil tezlikda. Farq — xotirada: rekursiv variant har qadamda stekda bitta joy oladi, O(h). Muvozanatli daraxtda h kichik va bu sezilmaydi. Cho'zilgan daraxtda esa stek to'lishi mumkin. Shuning uchun asosiy kodimizda while variantini ishlatamiz.

Tekshirib ko'ring: Shu daraxtda 64 ni qidirsak, qaysi tugunlarga qaraladi va natija nima?

4. Qo'shish

4.1 Qidirgandek tushamiz

Yangi qiymat qayerga tushishi kerak? Xuddi qidirgandek pastga tushamiz. Qiymat yo'q bo'lgani uchun oxirida null ga yetamiz — aynan shu bo'sh joy yangi tugunning o'rni. Masalan, 55 ning yo'lini qidiruvdan bilamiz: 50 → 70 → 60, keyin 60 ning chapi bo'sh. Demak, 55 o'sha yerga — 60 ning chap bolasi bo'lib tushadi. Kuzating:

Yangi tugun doim barg bo'lib qo'shiladi. Mavjud tugunlar joyidan qo'zg'almaydi — massivdagi kabi surish yo'q. Ish — bitta yo'l bo'ylab tushish, O(h).

Kodda current[side] yozuviga qarang: side — "left" yoki "right" satri. Kvadrat qavs bilan xususiyatni nomi bo'yicha olamiz (Obyekt xususiyatlariga murojaat). Shu hiyla tufayli chap va o'ng uchun ikki xil kod yozmadik.

4.2 Tartib shaklni belgilaydi

Bir xil raqamlar boshqa tartibda kelsa, daraxt boshqacha chiqadi. [50, 30, 70] — chiroyli, uch qavatli emas, ikki qavatli. [30, 50, 70] esa — 30, o'ngida 50, uning o'ngida 70: zanjir. Ildiz doim birinchi qo'shilgan qiymat bo'ladi. Bu kichik farq dars oxirida katta muammoga aylanadi.

Tekshirib ko'ring: Bo'sh BST'ga [40, 20, 60, 10, 30] ketma-ket qo'shildi. 30 kimning bolasi bo'ladi — chapmi, o'ngmi?

5. Inorder — saralangan ro'yxat

O'tgan darsda inorder yurish 20 30 40 50 60 70 80 ni berganini ko'rdik. Endi sababini tushunamiz. Inorder "chap shox, o'zi, o'ng shox" tartibida yuradi. BST'da chap shoxdagi hamma qiymat tugundan kichik, o'ngdagi hamma — katta. Demak, har tugun o'zidan kichiklarning hammasidan keyin va kattalarning hammasidan oldin yoziladi. Bu aynan o'sish tartibi.

Jasur akaning to'rtinchi vazifasi — "kun oxirida tartib bilan chiqarish" — shunchaki inorder, O(n). Saralash kerak emas.

Eng kichik va eng katta qiymatni topish ham oson. Eng kichigi — iloji boricha chapga tushganda oxirgi tugun. Eng kattasi — iloji boricha o'ngga. Ikkalasi ham O(h):

const node = (value, left = null, right = null) =>
  ({ value, left, right });
const root = node(50,
  node(30, node(20), node(40, node(35), node(45))),
  node(70, node(60, null, node(65)), node(80)));

function minValue(current) {
  while (current.left !== null) current = current.left;
  return current.value;
}

function maxValue(current) {
  while (current.right !== null) current = current.right;
  return current.value;
}

console.log(minValue(root), maxValue(root)); // 20 80
console.log(minValue(root.right)); // 60

Ikkinchi qatorga qarang: minValue(root.right) — 70 dan boshlangan shoxning eng kichigi, ya'ni 50 dan katta qiymatlarning eng kichigi. Bu son o'chirishda kerak bo'ladi.

5.1 Keyingi bo'sh vaqt

Malika qo'ng'iroq qildi: "Soat 19:00 da joy bormi? Bo'lmasa, undan keyingi eng yaqin vaqt-chi?" Bron qilish mumkin bo'lgan vaqtlar BST'da saqlanadi (daqiqada: 18:00 = 1080). Bizga berilgan qiymatdan katta yoki teng eng kichik qiymat kerak. Bu amal inglizcha ceiling ("ship") deb ataladi.

G'oya qidiruvga o'xshaydi. Tugun qiymati izlangandan katta bo'lsa — u nomzod. Uni eslab qolamiz va chapga boramiz: balki undan kichikroq, lekin baribir mos qiymat bordir. Tugun kichik bo'lsa — u mos emas, o'ngga boramiz:

const node = (value, left = null, right = null) =>
  ({ value, left, right });
// bron vaqtlari, daqiqada: 18:00 = 1080, 19:30 = 1170 ...
const slots = node(1170,
  node(1080, null, node(1110)),
  node(1260, node(1200), node(1320)));

function ceiling(current, value) {
  let best = null; // hozircha topilgan eng yaxshi nomzod
  while (current !== null) {
    if (current.value === value) return value;
    if (current.value > value) {
      best = current.value; // mos, lekin kichigi ham bo'lishi mumkin
      current = current.left;
    } else {
      current = current.right; // juda kichik — o'ngga
    }
  }
  return best;
}

console.log(ceiling(slots, 1140)); // 1170
console.log(ceiling(slots, 1200)); // 1200
console.log(ceiling(slots, 1330)); // null

19:00 (1140) bo'sh emas — eng yaqini 19:30 (1170). 20:00 (1200) bo'sh. 22:10 (1330) dan keyin vaqt yo'q — null. Funksiya bitta yo'l bo'ylab tushadi: O(h). Saralanmagan massivda buning uchun hamma vaqtni ko'rish kerak bo'lardi. Teskari amal — floor ("pol"): berilgan qiymatdan kichik yoki teng eng katta qiymat. Uni mashq sifatida o'zingiz yozib ko'ring: kod nometall aks kabi, chap va o'ng almashadi.

6. O'chirish: uch holat

O'chirish — BST'ning eng nozik amali. Avval tugunni topamiz (qidirgandek). Keyin uning nechta bolasi borligiga qarab, uch holatdan biri:

1. Barg (bola yo'q). Shunchaki olib tashlaymiz: otasidagi havola null bo'ladi.
2. Bitta bola. Tugun o'rniga uning yagona bolasi (butun shoxi bilan) ko'tariladi. Qoida buzilmaydi: shox ilgari ham shu otaning shu tomonida edi.
3. Ikki bola. Olib tashlasak, daraxt ikki bo'lakka ajraladi. O'rniga shunday qiymat kerakki, u chap shoxdagilardan katta, o'ngdagilardan kichik bo'lsin. Bunday qiymat bor — voris (successor): o'ng shoxning eng kichigi. Uning qiymatini tugunga yozamiz, keyin vorisni o'ng shoxdan o'chiramiz.

Voris qanday o'chiriladi? Unda chap bola yo'q — aks holda eng kichik bo'lmasdi. Demak, uni o'chirish 1- yoki 2-holat: oson.

Qog'ozda ikki bolali 30 ni o'chiramiz. Voris — 30 ning o'ng shoxidagi eng kichik qiymat: 40 dan chapga, 35 ga; 35 ning chapi yo'q. 35 ni 30 ning o'rniga yozamiz. Endi daraxtda ikkita 35 bor — pastdagisini 40 ning shoxidan o'chiramiz, u barg (1-holat). Kuzating:

Kodning tuzilishiga qarang. removeNode shoxning yangi ildizini qaytaradi, ota esa uni o'z havolasiga yozadi: current.left = removeNode(current.left, value). Barg o'chganda null qaytadi, bitta bolada — o'sha bola. Shu usul bilan "otani eslab qolish" kerak bo'lmaydi.

Voris o'rniga oldingi (predecessor) — chap shoxning eng kattasi — ham ishlatsa bo'ladi. Natija boshqa shakl, lekin baribir to'g'ri BST.

Tekshirib ko'ring: Darsdagi asl daraxtdan (o'chirishdan oldin) 50 ni — ildizni — o'chirsak, uning o'rniga qaysi qiymat keladi?

Endi o'zingiz to'ldiring. Bo'sh BST'ga [8, 3, 10, 9] qo'shildi. 8 ni o'chirsak, ildizga voris yoziladi va u bo'ladi.

7. BST'ni tekshirish

Kodimiz xato qilib, qoidani buzgan bo'lishi mumkin. Yoki daraxt boshqa joydan — fayl yoki serverdan keladi. U haqiqatan BST ekanini qanday tekshiramiz? Birinchi xayolga kelgan yechim — har tugunni bolalari bilan solishtirish. Bu xato:

const node = (value, left = null, right = null) =>
  ({ value, left, right });
// 60 — 30 ning o'ngida (to'g'ri), lekin 50 ning chap shoxida!
const broken = node(50, node(30, null, node(60)), node(70));

// ❌ faqat ota va bolani solishtiradi
function looksValid(current) {
  if (current === null) return true;
  if (current.left && current.left.value >= current.value) {
    return false;
  }
  if (current.right && current.right.value <= current.value) {
    return false;
  }
  return looksValid(current.left) && looksValid(current.right);
}

// ✅ har tugun uchun ruxsat etilgan oraliq: (min, max)
function isValidBST(current, min = -Infinity, max = Infinity) {
  if (current === null) return true;
  if (current.value <= min || current.value >= max) return false;
  return (
    isValidBST(current.left, min, current.value) &&
    isValidBST(current.right, current.value, max)
  );
}

console.log(looksValid(broken)); // true
console.log(isValidBST(broken)); // false

Birinchi funksiya aldandi: 60 o'z otasi (30) bilan to'g'ri munosabatda. Lekin u 50 ning chap shoxida — 50 dan kichik bo'lishi shart edi. 60 ni qidirsak, ildizda o'ngga ketamiz va uni hech qachon topmaymiz.

To'g'ri yechim har tugunga oraliq beradi. Ildiz uchun — cheksiz (-Infinity dan Infinity gacha). Chapga tushganda yuqori chegara ota qiymatiga torayadi, o'ngga tushganda — pastki chegara. 60 ga yetganda oraliq (30, 50) bo'ladi va 60 undan tashqarida.

Ikkinchi to'g'ri usul — inorder yurib, har qiymat oldingisidan katta ekanini tekshirish. Chunki BST ⇔ inorder qat'iy o'sadi.

8. Murakkablik va o'lchov

8.1 Hammasi O(h)

Qidirish, qo'shish, o'chirish, eng kichik va eng katta — hammasi ildizdan bitta yo'l bo'ylab tushadi. Vaqt — O(h), h — daraxt balandligi. Qo'shimcha xotira: while bilan — O(1); rekursiv removeNode — O(h) stek.

h qanchaga teng? Bu raqamlar qaysi tartibda kelganiga bog'liq. Tasodifiy tartibdagi buyurtma raqamlarini (urug'li generator) qo'shib, balandlikni o'lchadik. Jadvalda qavatlar soni berilgan — eng uzun yo'ldagi tugunlar. Bu Daraxt atamalari darsidagi balandlikdan (qirralar soni) bittaga ko'p:

Qavatlar soni log₂ n dan 2,5 baravar atrofida katta, lekin n bilan birga logarifmik o'sadi: n ming baravar oshdi, balandlik ikki baravar. Tugunlarning o'rtacha chuqurligi esa log₂ n ga yanada yaqin: million qiymatda 25. Matematik natija ham shunday: tasodifiy BST'ning kutilgan balandligi O(log n).

8.2 Uch yechimni o'lchaymiz

n ta tasodifiy raqamni qo'shib, keyin har birini qidirdik (n ta qo'shish + n ta qidirish):

Nisbatlarga qarang. BST: n ikki baravar — vaqt 2,2–2,6 baravar, bu n log n ga mos. Saralanmagan massiv: har safar aniq 4 baravar — includes bilan O(n²). Saralangan massiv: 3,5 → 4,5 → 5,7 baravar. Qo'shishda splice O(n), jami O(n²).

Kutilmagan natija ham bor. Sinfi "yomonroq" bo'lsa ham, saralangan massiv 40 000 da BST dan atigi 2,6 baravar sekin. splice elementlarni xotirada bir bo'lak qilib, juda tez suradi. BST esa har qadamda xotiraning boshqa joyidagi tugunga sakraydi. Kichik n da o'zgarmas ko'paytuvchi — bitta qadamning haqiqiy narxi — muhim. Lekin n o'sgan sari sinf g'olib chiqadi: 400 000 da farq 21 baravar.

8.3 Zaif joy: saralangan kirish

Endi raqamlarni o'sish tartibida qo'shamiz: 1, 2, 3, … Har yangi raqam oldingilarining hammasidan katta — doim o'ngga ketadi. Daraxt o'ng tomonga cho'zilgan zanjirga aylanadi: h = n.

O'sish tartibida n ikki baravar — vaqt to'rt baravar: O(n²). 40 000 ta raqam, faqat qo'shish — 1,8 soniya. Tasodifiy tartibda shuncha qo'shish va qidirish 28 ms oldi. Hayotda esa ma'lumot ko'pincha aynan tartib bilan keladi: buyurtma raqamlari, sanalar, id lar o'sib boradi. Bu muammoni Balanslangan daraxtlar va B-tree darsida hal qilamiz.

8.4 Qaysi tuzilmani tanlash kerak

BST — yagona to'g'ri javob emas. Sardor qaysi savolni ko'p berishiga qarab tanlaydi:

Set "bormi?" savoliga BST dan tezroq javob beradi — lekin "eng kichigi qaysi?", "40 dan keyingi raqam?" yoki "38 dan 62 gacha qaysilar?" savollariga javob bera olmaydi. Buning uchun hamma elementni ko'rish kerak, O(n). BST esa tartibni ichida saqlaydi va bu savollarga O(h) da javob beradi. Saralangan massiv ham tartibni saqlaydi, lekin har o'zgarishda elementlarni suradi.

Demak, BST'ning kuchli tomoni — tartib va o'zgarish birga kerak bo'lgan joy. Masalan, bronlar jadvali: bronlar kun bo'yi qo'shiladi va bekor qilinadi, mehmon esa "19:00 dan keyingi birinchi bo'sh vaqt" ni so'raydi.

Diqqat: "BST — O(log n)" degan gap faqat daraxt muvozanatli bo'lsa rost. Oddiy BST uchun to'g'ri javob: o'rtacha O(log n), eng yomon holatda O(n). Intervyuda shu farqni aytish kutiladi.

9. Chegaraviy holatlar

• Bo'sh daraxt. has — false, min — qiymat yo'q (undefined), delete — hech narsa o'zgarmaydi. minValue(null) esa yiqiladi — chaqirishdan oldin tekshiring.
• Ildizni o'chirish. this.root ning o'zi o'zgaradi — shuning uchun this.root = removeNode(this.root, value) deb yozamiz.
• Takrorlar. Bizning qoida — qo'shilmaydi. Hisoblagich kerak bo'lsa, tugunga count qo'shing.
• Manfiy sonlar va satrlar. < ular bilan ham ishlaydi. Satrlar kod birligi tartibida solishtiriladi: "Manti" < "lag'mon", chunki katta harflar oldin keladi (Taqqoslash operatorlari).
• Yo'q qiymatni o'chirish. Qidiruv null ga yetadi va hech narsa o'zgarmaydi.

10. Ko'p uchraydigan xatolar

10.1 Faqat bolalarni tekshirish

looksValid — BST tekshirishda eng mashhur xato. Tuzatish: oraliq (min, max) yoki inorderda qat'iy o'sish.

10.2 Ildizni o'chirganda this.root ni yangilamaslik

removeNode(this.root, 50) yangi ildizni qaytaradi, lekin uni hech qayerga yozmasangiz, this.root eski (o'chirilgan) tugunni ko'rsatib qoladi. Tuzatish: natijani doim otaga yoki this.root ga yozing.

10.3 Ikki bolali tugunda vorisni o'chirishni unutish

Qiymat ko'chirildi, lekin pastdagi voris qoldi — daraxtda ikkita bir xil qiymat. Tuzatish: current.right = removeNode(current.right, next.value).

10.4 "BST doim tez" deb o'ylash

Saralangan kirishda — zanjir va O(n). Tuzatish: ma'lumot tartibini o'ylang yoki muvozanatli daraxt ishlating.

11. Mashqlar

1-mashq (oson): Daraxtni chizing

Bo'sh BST'ga [35000, 28000, 30000, 5000, 42000, 12000] — taom narxlari — ketma-ket qo'shildi. Daraxtni chizing, balandligini ayting va inorder tartibini yozing.

          35000
         /     \
     28000     42000
     /    \
  5000   30000
     \
    12000

2-mashq (o'rta): Oraliqdagi buyurtmalar

rangeValues(root, low, high) funksiyasini yozing: low dan high gacha (ikkalasi ham kiradi) qiymatlarni o'sish tartibida qaytarsin. Ishora: inorder yuring, lekin shoxni foydasi bo'lmasa tashlang — agar current.value <= low bo'lsa, chap shoxda kerakli qiymat yo'q.

const node = (value, left = null, right = null) =>
  ({ value, left, right });
const root = node(50,
  node(30, node(20), node(40, node(35), node(45))),
  node(70, node(60, null, node(65)), node(80)));

function rangeValues(current, low, high, result = []) {
  if (current === null) return result;
  if (current.value > low) {
    rangeValues(current.left, low, high, result);
  }
  if (current.value >= low && current.value <= high) {
    result.push(current.value);
  }
  if (current.value < high) {
    rangeValues(current.right, low, high, result);
  }
  return result;
}

console.log(rangeValues(root, 38, 62)); // [ 40, 45, 50, 60 ]
console.log(rangeValues(root, 90, 99)); // []

3-mashq (qiyin): To'liq BST klassi va testlar

kurs/mashqlar/14/38-bst/bst.test.mjs faylida BST klassini yozing: insert, has, min, delete (o'chsa true, yo'q bo'lsa false), toArray (inorder) va size (tugunlar soni). O'chirishni yashirin metodda yozing — #remove (Private maydonlar). Testlar (node:test):

1. Bo'sh daraxt: has — false, min — undefined, delete — false.
2. Takror qo'shilmaydi, toArray saralangan, size to'g'ri.
3. Uch holat: ikki bolali 30 (o'rniga 35 keladi), barg 20, bitta bolali 60.
4. Ildizni o'chirish va yo'q qiymat.

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

class BST {
  constructor() {
    this.root = null;
    this.size = 0;
  }
  insert(value) {
    const fresh = { value, left: null, right: null };
    if (this.root === null) {
      this.root = fresh;
      this.size++;
      return;
    }
    let current = this.root;
    while (true) {
      if (value === current.value) return;
      const side = value < current.value ? "left" : "right";
      if (current[side] === null) {
        current[side] = fresh;
        this.size++;
        return;
      }
      current = current[side];
    }
  }
  has(value) {
    let current = this.root;
    while (current !== null) {
      if (value === current.value) return true;
      current =
        value < current.value ? current.left : current.right;
    }
    return false;
  }
  min() {
    if (this.root === null) return undefined;
    let current = this.root;
    while (current.left !== null) current = current.left;
    return current.value;
  }
  delete(value) {
    const before = this.size;
    this.root = this.#remove(this.root, value);
    return this.size < before; // o'chdimi
  }
  #remove(current, value) {
    if (current === null) return null;
    if (value < current.value) {
      current.left = this.#remove(current.left, value);
    } else if (value > current.value) {
      current.right = this.#remove(current.right, value);
    } else {
      if (current.left === null || current.right === null) {
        this.size--;
        return current.left ?? current.right;
      }
      let next = current.right;
      while (next.left !== null) next = next.left;
      current.value = next.value;
      current.right = this.#remove(current.right, next.value);
    }
    return current;
  }
  toArray() {
    const result = [];
    const walk = (n) => {
      if (n === null) return;
      walk(n.left);
      result.push(n.value);
      walk(n.right);
    };
    walk(this.root);
    return result;
  }
}

function make(values) {
  const tree = new BST();
  for (const v of values) tree.insert(v);
  return tree;
}

test("bo'sh daraxt", () => {
  const t = new BST();
  assert.equal(t.has(5), false);
  assert.equal(t.min(), undefined);
  assert.equal(t.delete(5), false);
});

test("inorder — saralangan, takror qo'shilmaydi", () => {
  const t = make([50, 30, 70, 30, 20, 80]);
  assert.deepEqual(t.toArray(), [20, 30, 50, 70, 80]);
  assert.equal(t.size, 5);
  assert.equal(t.min(), 20);
});

test("o'chirish: barg, bitta bola, ikki bola", () => {
  const t = make([50, 30, 70, 20, 40, 60, 80, 35, 45, 65]);
  assert.equal(t.delete(30), true); // ikki bola
  assert.equal(t.root.left.value, 35); // voris o'rnida
  assert.equal(t.delete(20), true); // barg
  assert.equal(t.delete(60), true); // bitta bola (65)
  assert.deepEqual(t.toArray(), [35, 40, 45, 50, 65, 70, 80]);
});

test("ildizni o'chirish va yo'q qiymat", () => {
  const t = make([50, 30, 70]);
  assert.equal(t.delete(50), true);
  assert.equal(t.root.value, 70);
  assert.equal(t.delete(99), false);
  assert.equal(t.size, 2);
});

✔ bo'sh daraxt (1.3849ms)
✔ inorder — saralangan, takror qo'shilmaydi (1.4832ms)
✔ o'chirish: barg, bitta bola, ikki bola (0.3465ms)
✔ ildizni o'chirish va yo'q qiymat (1.1447ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 130.4072

4-mashq: Amaliy tajriba — BST qatorlari

kurs/mashqlar/14/MURAKKABLIK.md ga qo'shing: BST (qidirish, qo'shish, o'chirish), saralangan massivga qo'shish, BST inorder. Vaqt ustunida o'rtacha va eng yomon holatni ajrating.

| Masala | Yechim | Vaqt | Xotira |
|---|---|---|---|
| Bormi / qo'shish / o'chirish | BST | O(log n) o'rt., O(n) eng yomon | O(n) |
| Qo'shish | saralangan massiv + splice | O(n) | O(n) |
| Bormi | saralangan massiv | O(log n) | O(1) |
| Tartib bilan chiqarish | BST inorder | O(n) | O(h) |
| Oraliq so'rovi | BST, shox tashlash | O(h + k) | O(h) |

git add 14/MURAKKABLIK.md 14/38-bst
git commit -m "14/38: BST klassi, o'chirishning uch holati"

12. Real ishda

• Saralangan to'plamlar. Java'da TreeMap, C++ da std::map, Rust'da BTreeMap — tartibni saqlaydigan lug'atlar daraxt asosida. JavaScript'da bunday tayyor tuzilma yo'q: Map va Set qo'shilish tartibini saqlaydi, qiymat tartibini emas.
• Ma'lumotlar bazasi indekslari. "Narxi 20 000 dan 40 000 gacha bo'lgan taomlar" kabi oraliq so'rovlar daraxt shaklidagi indeks bilan tez bajariladi. U yerda oddiy BST emas, B-tree ishlatiladi — keyingi darsda.
• Bron va jadval tizimlari. "Keyingi bo'sh vaqt", "eng yaqin narx", "shu summadan arzon eng qimmat taom" — ceiling va floor savollari. Kalendarlar, kinoteatr joylari va birja buyurtmalari kitobi (narx bo'yicha saralangan takliflar) aynan shunday tuzilmalarda saqlanadi.
• Kompilyatorlar va muharrirlar. Matn muharrirlari katta faylni qator oraliqlari daraxtida saqlaydi: "1 500-qator qayerda?" savoliga butun faylni ko'rmasdan javob beriladi.
• Intervyu. "BST'ni tekshiring", "k-chi eng kichik element", "ikki tugunning eng yaqin umumiy ajdodi" — klassik savollar. Birinchisida looksValid tuzog'iga tushish juda ko'p uchraydi.

Xulosa

• BST: har tugunning chap shoxida hamma qiymatlar kichik, o'ngida — katta.
• Qidirish, qo'shish, o'chirish — bitta yo'l bo'ylab tushish, O(h). Yangi tugun doim barg bo'ladi.
• O'chirishning uch holati: barg — olib tashlash; bitta bola — bolani ko'tarish; ikki bola — voris (o'ng shoxning eng kichigi) bilan almashtirish.
• Inorder BST'da saralangan ro'yxat beradi; tekshirish — oraliq (min, max) bilan.
• O'lchov: tasodifiy tartibda balandlik logarifmik (million qiymatda 52 qavat); o'sish tartibida — zanjir, 40 000 ta qo'shish 1,8 soniya.

Keyingi dars: Balanslangan daraxtlar va B-tree — daraxt zanjirga aylanmasligi uchun rotatsiya, AVL va Red-Black g'oyasi, ma'lumotlar bazasi indeksidagi B-tree.

Manbalar

• Thomas H. Cormen va boshq., "Introduction to Algorithms", 4-nashr, MIT Press, 2022 — 12-bob (binary search trees, tasodifiy BST balandligi).
• LeetCode 98 "Validate Binary Search Tree", 450 "Delete Node in a BST" — leetcode.com (shartlari boshqacha, g'oyasi shu darsdagi).
• MDN: Private class fields (#), nullish coalescing (??) — developer.mozilla.org