BST'mi?
Binar daraxt berilgan. U haqiqiy binar qidiruv daraxti ekanligini aniqlang.
BST xususiyati: har tugun uchun chap kenja daraxtidagi barcha qiymatlar ushbu tugundan qat'iy kichik, o'ng kenja daraxtidagi barcha qiymatlar esa qat'iy katta.
BST: BST emas:
[5] [5]
/ \ / \
[3] [7] [1] [4]
/ \ / \ / \
[1] [4][6] [8] [1] [6]
↑
6 > 5, lekin 5'ning chapida → xato
Ko'p uchraydigan xato
Noto'g'ri yondashuv: har tugun uchun faqat bevosita bolalar qiymati tekshiriladi.
BST emas (lekin sodda tekshiruv "BST" deydi):
[10]
/ \
[5] [15]
/ \
[1] [8] ← to'g'ri: 1 < 5, 8 < 10
\
[12] ← XATO: 12 > 10, lekin 10'ning chap kenja daraxtida
[5] ning o'ng bolasi [8] — 8 < 5 emas, 8 < 10 ham emas. Aslida 8 < 10 va 12 > 10 — 12 10'ning chap kenja daraxtida bo'lmasligi kerak. Bu daraxt BST emas, lekin har tugunning faqat bevosita bolasini tekshirsak, topilmaydi.
Shuning uchun to'g'ri yondashuv — har tugunga ruxsat etilgan qiymat oralig'ini uzatish.
To'g'ri yondashuv: min/max chegaralar
Har tugun uchun uning qiymati (min, max) oralig'ida bo'lishi kerak. Rekursiyada:
- Chap bolaga: max = joriy tugun qiymati.
- O'ng bolaga: min = joriy tugun qiymati.
FUNCTION IS_VALID_BST(node, min, max)
IF node = NULL
RETURN TRUE // bo'sh kenja daraxt to'g'ri
IF node.value ≤ min OR node.value ≥ max
RETURN FALSE // chegaradan tashqari
RETURN IS_VALID_BST(node.left, min, node.value) AND
IS_VALID_BST(node.right, node.value, max)
// Dastlabki chaqiruv:
IS_VALID_BST(root, -∞, +∞)
Ildiz uchun chegara yo'q — (-∞, +∞). Chuqurlikka tushgan sari chegara torayadi.
Bosqichma-bosqich dry run
IS_VALID_BST(10, -∞, +∞):
10 ∈ (-∞, +∞) ✓
IS_VALID_BST(5, -∞, 10): ← chap, max=10
5 ∈ (-∞, 10) ✓
IS_VALID_BST(1, -∞, 5): ← chap, max=5
1 ∈ (-∞, 5) ✓
IS_VALID_BST(NULL, -∞, 1) = TRUE
IS_VALID_BST(NULL, 1, 5) = TRUE
return TRUE
IS_VALID_BST(8, 5, 10): ← o'ng, min=5, max=10
8 ∈ (5, 10) ✓
IS_VALID_BST(NULL, 5, 8) = TRUE
IS_VALID_BST(12, 8, 10): ← o'ng, min=8, max=10
12 ≥ 10 → RETURN FALSE ← XATO TOPILDI
return FALSE (chunki o'ng sohadan FALSE keldi)
return FALSE
Javob: FALSE
[12] max=10 chegarasini buzdi — bu ota-bobolardan meros qolgan cheklov.
To'g'ri BST dry run
IS_VALID_BST(5, -∞, +∞):
5 ✓
IS_VALID_BST(3, -∞, 5):
3 ✓
IS_VALID_BST(1, -∞, 3): 1 ✓ → TRUE
IS_VALID_BST(4, 3, 5): 4 ✓ → TRUE
return TRUE
IS_VALID_BST(7, 5, +∞):
7 ✓
IS_VALID_BST(6, 5, 7): 6 ✓ → TRUE
IS_VALID_BST(8, 7, +∞): 8 ✓ → TRUE
return TRUE
return TRUE
Javob: TRUE
Alternativ yondashuv: inorder traversal
BST'ning muhim xususiyati: inorder traversal (chap → ildiz → o'ng) qiymatlarni o'sish tartibida beradi.
Agar inorder traversal natijasida qiymatlar qat'iy o'sish tartibida bo'lsa — daraxt BST.
FUNCTION IS_VALID_BST_INORDER(root)
prev = -∞
RETURN INORDER_CHECK(root, prev)
FUNCTION INORDER_CHECK(node, prev)
IF node = NULL
RETURN TRUE
// Chap kenja daraxt
IF NOT INORDER_CHECK(node.left, prev)
RETURN FALSE
// Ildiz tekshirish
IF node.value ≤ prev
RETURN FALSE
prev = node.value
// O'ng kenja daraxt
RETURN INORDER_CHECK(node.right, prev)
prev — inorder tartibda ko'rilgan oxirgi qiymat. Agar joriy qiymat prev dan katta bo'lmasa — BST emas.
Muammo: prev o'zgaruvchini rekursiya bo'ylab uzatish tilga qarab farq qiladi — reference yoki global o'zgaruvchi sifatida ishlatilishi kerak.
Ikkala yondashuvni solishtirish
| Xususiyat | Min/max chegaralar | Inorder traversal |
|---|---|---|
| Intuitivlik | BST ta'rifiga yaqin | Indirect — xususiyatdan foydalanadi |
| O'zgaruvchilar | Rekursiyada min/max | prev o'zgaruvchisi |
| Xato topish | Darhol tuxtatadi | Xato topilganda ham davom etishi mumkin |
| Vaqt | O(n) |
O(n) |
| Xotira | O(h) call stack |
O(h) call stack |
Ikkalasi ham O(n) vaqt va O(h) xotira. Min/max yondashuvi BST ta'rifiga bevosita to'g'ri keladi va muloqotda tushuntirish oson.
Vaqt va xotira murakkabligi
Barcha n tugun bir marta ko'riladi — O(n) vaqt. Rekursiv call stack balandlik bo'yicha O(h) xotira. Muvozanatlangan BST'da O(log n), muvozanatsizda O(n).
Edge case'lar
Bo'sh daraxt. root = NULL → TRUE. Bo'sh daraxt BST xususiyatini buzmaydigan maxsus holat.
Bitta tugunli daraxt. Chap va o'ng bolalari yo'q → har ikkisi NULL → TRUE. Bitta tugunli daraxt har doim BST.
Teng qiymatlar. BST ta'rifi qat'iy kichik/katta talab qiladi (< va >, ≤ va ≥ emas). [5, 5] daraxtida ikki 5 — BST emas, chunki o'ngda 5 > 5 emas. Shartga qarab: ba'zi implementatsiyalar takrorlarni qabul qiladi (teng ≤ bir tomonga), lekin klassik ta'rifda takrorlar yo'q.
MIN_INT / MAX_INT chegaralari. prev = -∞ va boshlang'ich min = -∞, max = +∞ qachon butun son ishlatilsa, INT_MIN va INT_MAX orqali ifodalanadi. Lekin tugun qiymati aynan INT_MIN yoki INT_MAX bo'lsa, chegara bilan taqqoslash noto'g'ri natija berishi mumkin. Chegaralar uchun alohida null/None flag yoki katta/kichik son ishlatish kerak.
Zanjir ko'rinishidagi daraxt. Tartiblangan qiymatlar bilan bir tomonlama zanjir — BST (balandlik O(n), lekin xususiyat bajariladi).
Note
node.value ≤ min va node.value ≥ max shartlarida tenglikni (=) kiritish muhim. Agar faqat < va > ishlatilsa, teng qiymatlar o'tkazib yuboriladi — BST ta'rifiga ko'ra teng qiymatlar bo'lmasligi kerak.
Xulosa
BST tekshirish masalasida eng keng tarqalgan xato — faqat bevosita bolalarni taqqoslash. Bu [5, 1, 4, null, null, 3, 6] kabi holatlarda ishlamaydi.
To'g'ri yondashuv: har tugunga (min, max) chegaralar uzatish. Ildizdan chuqurlikka tushar ekan, chegara torayadi — chap tomonda max yangilanadi, o'ng tomonda min. Agar birorta qiymat bu chegaradan chiqsa — BST emas.
Bu masalaning asosiy sabog'i: daraxt xususiyatini tekshirishda lokal (faqat bevosita bola) ko'rish yetarli emas — global (ota-bobolardan qolgan) chegaralar ham hisobga olinishi kerak.