Tarkibga o'tish

Binar daraxt va BST

Tasavvur qiling, lug'atdan so'z qidiryapsiz. Kitobni o'rtasidan ochasiz: "S" harfiga qarasangiz — kerakli so'z o'ng tomonda, "T" harfiga qarasangiz — chap tomonda bo'lishi kerakligini bilasiz. Har safar izlash maydonining yarmini kesib tashlaysiz. Bu qidiruv tartibi binar qidiruv daraxti mantig'iga asoslanadi.

Binar daraxt

Binar daraxt (binary tree) — har bir tugunning ko'pi bilan ikkita bolasi bo'lgan daraxt. Chap bola va o'ng bola ko'rinishida joylashadi.

        [8]
       /   \
     [3]   [10]
    / \      \
  [1] [6]   [14]
      / \
    [4] [7]

Binar daraxtda bolalar soni cheklangani uchun ko'pgina operatsiyalar rekursiv yoki iterativ ravishda aniq tuzilmada bajarilishi mumkin.

Binar daraxtlar orasida eng muhimi — binar qidiruv daraxti.

Binar qidiruv daraxti (BST)

Binar qidiruv daraxti (Binary Search Tree, BST) — quyidagi xususiyatni saqlagan binar daraxt:

Har tugun uchun: chap kenja daraxtidagi barcha qiymatlar ushbu tugundan kichik, o'ng kenja daraxtidagi barcha qiymatlar esa ushbu tugundan katta.

        [8]
       /   \
     [3]   [10]
    / \      \
  [1] [6]   [14]
      / \
    [4] [7]

8ni ko'raylik: chapda 3, 1, 6, 4, 7 — barchasi 8dan kichik. O'ngda 10, 14 — barchasi 8dan katta. Bu shart har tugun uchun alohida tekshiriladi, nafaqat ildiz uchun.

Bu xususiyat qidiruvni O(h) da bajarishga imkon beradi — har qadamda izlash maydoni taxminan yarimlaydi.

BST'da qidirish

Qidirish ildizdan boshlanadi. Har qadamda:

  • Joriy tugun qiymatiga teng bo'lsa — topildi.
  • Kichik bo'lsa — chap kenja daraxtga o'tish.
  • Katta bo'lsa — o'ng kenja daraxtga o'tish.
FUNCTION SEARCH(node, target)
    IF node = NULL
        RETURN TOPILMADI

    IF target = node.value
        RETURN node

    IF target < node.value
        RETURN SEARCH(node.left, target)
    ELSE
        RETURN SEARCH(node.right, target)

8 dan 7ni qidirish:

[8]:  7 < 8  → chap
[3]:  7 > 3  → o'ng
[6]:  7 > 6  → o'ng
[7]:  7 = 7  → topildi!

4 qadam — 7 ta tugunli daraxtda. Tartiblangan massivdagi binary searchga o'xshash mantiq.

Vaqt murakkabligi: O(h) — h daraxt balandligi. Muvozanatlangan BST'da h = O(log n). Muvozanatsiz (zanjir ko'rinishidagi) BST'da h = O(n).

BST'ga qo'shish

Yangi element uchun to'g'ri o'rinni qidiruvdek topamiz, keyin qo'shamiz.

FUNCTION INSERT(node, value)
    IF node = NULL
        RETURN yangi NODE(value)

    IF value < node.value
        node.left = INSERT(node.left, value)
    ELSE IF value > node.value
        node.right = INSERT(node.right, value)
    // teng bo'lsa — aksariyat BST dublikat qabul qilmaydi

    RETURN node

Bosqichma-bosqich dry run — yuqoridagi daraxtga 5 qo'shamiz:

[8]:  5 < 8  → chap
[3]:  5 > 3  → o'ng
[6]:  5 < 6  → chap
[4]:  5 > 4  → o'ng
NULL:  yangi node yaratiladi → 4 ning o'ng bolasi bo'ladi

Natija:
        [8]
       /   \
     [3]   [10]
    / \      \
  [1] [6]   [14]
      / \
    [4] [7]
      \
      [5]

Vaqt: O(h). Daraxt muvozanatlangan bo'lsa O(log n), zanjir bo'lsa O(n).

BST'dan o'chirish

O'chirish uchta holatni qamraydi.

Holat 1: Barg tugunni o'chirish

Bolasi yo'q — shunchaki olib tashlanadi.

[14]ni o'chirish:
  [10]'ning o'ng bola murojaati NULL ga o'rnatiladi.

Holat 2: Bitta bolali tugunni o'chirish

Tugun o'rniga uning yagona bolasi qo'yiladi.

[10]ni o'chirish ([14] bitta bolasi bor):
  [8]'ning o'ng bola murojaati [14] ga o'tkaziladi.

Holat 3: Ikkita bolali tugunni o'chirish

Bu murakkabroq. O'chirilayotgan tugunning o'rnini bosuvchi qiymat BST xususiyatini saqlab turishi kerak. Ikkita klassik tanlov:

  • In-order successor: o'ng kenja daraxtdagi eng kichik qiymat (ya'ni, o'ngga bir qadam, keyin iloji boricha chapga).
  • In-order predecessor: chap kenja daraxtdagi eng katta qiymat.
[6]ni o'chirish (bolalari [4] va [7]):
  In-order successor: [7] (o'ng kenja daraxtdagi minimum)
  [6] o'rniga [7] qo'yiladi, [7] asl joyidan o'chiriladi.

Natija:
        [8]
       /   \
     [3]   [10]
    / \      \
  [1] [7]   [14]
      /
    [4]

FUNCTION DELETE(node, value)
    IF node = NULL
        RETURN NULL

    IF value < node.value
        node.left = DELETE(node.left, value)
    ELSE IF value > node.value
        node.right = DELETE(node.right, value)
    ELSE
        // Tugun topildi
        IF node.left = NULL
            RETURN node.right
        IF node.right = NULL
            RETURN node.left

        // Ikkita bola — in-order successor topish
        successor = MINIMUM(node.right)
        node.value = successor.value
        node.right = DELETE(node.right, successor.value)

    RETURN node

FUNCTION MINIMUM(node)
    WHILE node.left ≠ NULL
        node = node.left
    RETURN node

BST'da minimum va maksimum

Minimum: daraxtning eng chap pastidagi element — chapga imkon qadar tushish.

FUNCTION MINIMUM(node)
    WHILE node.left ≠ NULL
        node = node.left
    RETURN node.value

Maksimum: eng o'ng pastidagi element.

FUNCTION MAXIMUM(node)
    WHILE node.right ≠ NULL
        node = node.right
    RETURN node.value

Ikkala amal ham O(h) vaqt oladi.

Muvozanatsiz BST muammosi

BST'ga elementlar ma'lum tartibda qo'shilsa, daraxt zanjirga aylanishi mumkin:

1, 2, 3, 4, 5 tartibida qo'shilsa:

[1]
  \
  [2]
    \
    [3]
      \
      [4]
        \
        [5]

Bu ro'yxatdan farqi yo'q — qidirish O(n). BST xususiyatini saqlaydi, lekin O(log n) afzalligini yo'qotadi.

Shuning uchun amaliy kutubxonalarda muvozanatlangan BST ishlatiladi: AVL daraxt (har tugun uchun balandlik farqi ±1) yoki qizil-qora daraxt. Ular har qo'shish va o'chirishdan keyin aylantirish (rotation) orqali muvozanatni tiklaydi va balandlikni O(log n) da ushlab turadi.

Aylantirish (rotation) namunasi:

Muvozanatsiz:          O'ng aylantirish:
   [3]                    [2]
  /                      / \
[2]                    [1] [3]
/
[1]

Rotation BST xususiyatini buzmaydi, faqat tugunlar joylashuvini o'zgartiradi.

Vaqt va xotira murakkabligi

Amal Muvozanatlangan BST Muvozanatsiz BST Sabab
Qidirish O(log n) O(n) Balandlik bo'yicha
Qo'shish O(log n) O(n) O'rin topib qo'shish
O'chirish O(log n) O(n) O'rin topib o'chirish
Minimum O(log n) O(n) Eng chap tugun
Maksimum O(log n) O(n) Eng o'ng tugun
In-order traversal O(n) O(n) Barcha tugunlar

Xotira: n tugun uchun O(n). Har tugun qiymat va ikki reference saqlaydi. Rekursiv amallar call stack uchun O(h) qo'shimcha xotira ishlatadi.

BST'da tartiblangan traversal

BST'ning diqqatga sazovor xususiyati: in-order traversal (chap → ildiz → o'ng) barcha qiymatlarni o'sish tartibida beradi.

        [8]
       /   \
     [3]   [10]
    / \      \
  [1] [6]   [14]
      / \
    [4] [7]

In-order: 1, 3, 4, 6, 7, 8, 10, 14  ← o'sish tartibi

Bu xususiyat "k-chi eng kichik element", "oraliqda nechta element?" kabi masalalarda ishlatiladi.

BST va hash table taqqoslash

Xususiyat BST (muvozanatlangan) Hash table
Qidirish O(log n) kutiladigan O(1)
Tartibli traversal Ha (O(n)) Yo'q
Diapazon so'rovi Ha Yo'q
Minimum/maksimum O(log n) O(n)
Eng yomon lookup O(log n) O(n)
Xotira Har tugun uchun overhead Bo'sh kapasitet

BST tartib, diapazon va min/max kerak bo'lganda hash table'dan ustun. Hash table oddiy lookup tezligida ustun.

Real qo'llanishlar

Ma'lumotlar bazasi indeksi

Ko'p relatsion ma'lumotlar bazalari B-tree (muvozanatlangan, ko'p bolali daraxt) asosidagi indeks ishlatadi. Bir xil mantiq: id = 1042 qidirish O(log n) da, id BETWEEN 100 AND 200 ham samarali.

Kompilyator

Dastur o'zgaruvchi va funksiyalarini symbol table'da saqlaydi. Muvozanatlangan BST yoki hash map har ikkalasi ham ishlatilishi mumkin; BST alifbo tartibida traversal kerak bo'lganda qulayroq.

Set va map kutubxonalari

Ko'p dasturlash tillarida tartiblangan set yoki map kichik ichki ma'lumot sifatida muvozanatlangan BST (red-black tree yoki AVL tree) ishlatadi. Bu O(log n) qo'shish, o'chirish va tartiblangan iteration kafolatini beradi.

Keng tarqalgan xatolar

Faqat ildizni tekshirib BST deyish. BST xususiyati har tugun uchun, nafaqat ildiz uchun tekshirilishi kerak. [10, 5, 15, 3, 7, 6, 20] daraxtida 6 noto'g'ri joyda: 10'ning chap kenja daraxtida 6 < 10 to'g'ri ko'rinadi, lekin u 5'ning o'ng kenja daraxtida bo'lishi kerak (6 > 5 — to'g'ri), lekin 10'ning chap kenja daraxtidagi barcha elementlar < 10 bo'lishi shart — bu ko'z aldamchisi.

Tekshirish uchun min/max chegaralar bilan rekursiya ishlatiladi — bu keyingi masalada ko'riladi.

In-order successor'ni topmasdan o'chirish. Ikkita bolali tugunni o'chirganda successor topilmasa, BST xususiyati buziladi.

Muvozanatsiz daraxtda O(log n) deb taxmin qilish. Kirish ma'lumotlari tartiblangan bo'lsa, daraxt zanjirga aylanishi mumkin. Muvozanat talab qilinadigan holatlarda muvozanatlangan daraxt implementatsiyasi tanlanadi.

Qachon BST ishlatish kerak?

  • Tartiblangan ma'lumotda tez qidirish kerak bo'lganda.
  • Min/max yoki k-chi eng kichik/katta element kerak bo'lganda.
  • Diapazon qidirish zarur bo'lganda.
  • In-order traversal bilan barcha elementlarni tartibda olish kerak bo'lganda.
  • Hash table'dagi eng yomon holat O(n) qabul qilinmaganda.

Qachon BST ishlatmaslik kerak?

  • Faqat lookup kerak bo'lsa — hash table kutiladigan O(1) beradi.
  • Tartib kerak bo'lmasa — hash map va hash set soddaroq.
  • Muvozanatni kafolatlay olmasangiz — muvozanatlangan BST implementatsiyasi (AVL, red-black) foydalanish kerak.
  • Disk asosidagi katta ma'lumot bo'lsa — B-tree xotira bilan samaraliroq ishlaydi.

Eng muhim xulosa

Binar daraxt — har tugunning ko'pi bilan ikkita bolasi bor daraxt. BST bu daraxtga tartib qo'shadi: chap < ildiz < o'ng, har tugun uchun. Bu xususiyat qidirish, qo'shish va o'chirishni O(h) da bajarish imkonini beradi.

Muvozanatlangan BST'da h = O(log n), bu barcha asosiy amallarni O(log n) qiladi. Muvozanatsiz BST'da h = O(n) bo'lishi mumkin — bu ro'yxat bilan teng.

BST'ni amalda to'g'ri ishlatish uchun ikki savol muhim:

  1. Daraxt muvozanatlangan ekaniga kafolat bormi?
  2. Tartib yoki diapazon kerakmi — agar kerak bo'lmasa, hash table tezroq?

Keyingi muhim mavzu — daraxtni turli tartibda aylanib chiqish (DFS, BFS) — BST'ni ham, umumiy daraxtni ham tekshirish va qayta ishlashning asosiy vositasi.