</> Softromeda Edu

8-bo‘lim

Daraxtlar

Daraxt atamalari, ikkilik daraxt, uni aylanib chiqishning to'rt usuli va daraxtlar qayerda ishlatilishi.

🕑 9 daqiqa o‘qish 📄 649 so‘z 👁 8 marta ko‘rilgan
Ushbu bo‘lim mundarijasi
  1. Daraxt atamalari
  2. Ikkilik daraxt (Binary Tree)
  3. Ikkilik daraxt turlari
  4. Daraxtni aylanib chiqish
  5. Daraja bo'yicha aylanish (BFS)
  6. Foydali daraxt funksiyalari
  7. Daraxtni chiroyli chiqarish
  8. Daraxtlar qayerda ishlatiladi?
  9. Xulosa

Shu paytgacha ko'rgan tuzilmalarimiz chiziqli edi - elementlar bir qatorda joylashgan. Lekin ko'p ma'lumotlar tabiatan ierarxik: papkalar ichida papkalar, bo'limlar ichida bo'limlar, boshliq ostida xodimlar.

Daraxt atamalari #

A ildiz (root) otasi yo'q B C ichki tugunlar D E F barglar (leaf) - bolasi yo'q daraja 0 daraja 1 daraja 2 balandlik = 2
Daraxt ildizdan barglarga qarab o'sadi - tabiatdagidan teskari
AtamaMa'nosi
Ildiz (root)Eng yuqoridagi tugun, otasi yo'q
Ota (parent)Tepadagi bog'langan tugun
Bola (child)Pastdagi bog'langan tugun
Barg (leaf)Bolasi bo'lmagan tugun
Aka-uka (sibling)Bitta otaga tegishli tugunlar
Daraja (depth)Ildizdan tugungacha bo'lgan masofa
Balandlik (height)Ildizdan eng uzoq bargacha masofa
Qism daraxtHar qanday tugun va uning avlodlari
Daraxt - bu grafning maxsus turi

Daraxt - sikli yo'q va bog'langan graf. n ta tugunli daraxtda har doim aynan n - 1 ta qirra bo'ladi. Graflarni 11-bo'limda ko'ramiz.

Ikkilik daraxt (Binary Tree) #

Eng ko'p ishlatiladigan tur: har bir tugunning ko'pi bilan ikkita bolasi bo'ladi - chap va o'ng.

Python
class DaraxtTuguni:
    """Ikkilik daraxt tuguni."""

    def __init__(self, qiymat):
        self.qiymat = qiymat
        self.chap = None
        self.ong = None

    def __repr__(self):
        return f"Tugun({self.qiymat})"


#         A
#        / \
#       B   C
#      / \   \
#     D   E   F

ildiz = DaraxtTuguni("A")
ildiz.chap = DaraxtTuguni("B")
ildiz.ong = DaraxtTuguni("C")
ildiz.chap.chap = DaraxtTuguni("D")
ildiz.chap.ong = DaraxtTuguni("E")
ildiz.ong.ong = DaraxtTuguni("F")

print(ildiz, ildiz.chap, ildiz.chap.chap)
Natija
Tugun(A) Tugun(B) Tugun(D)

Ikkilik daraxt turlari #

TuriSharti
To'liq (full)Har bir tugunda 0 yoki 2 ta bola
Mukammal (perfect)Barcha barglar bir darajada, hamma ichki tugun to'la
Butun (complete)Oxirgisidan boshqa barcha daraja to'la, oxirgisi chapdan to'ladi
Muvozanatli (balanced)Chap va o'ng balandlik farqi 1 dan oshmaydi
Balandlik nima uchun muhim?

Daraxtdagi barcha amallar balandlikka bog'liq. Muvozanatli daraxtda balandlik log₂(n), ya'ni million tugun uchun atigi 20 daraja. Muvozanatsiz daraxt esa bog'langan ro'yxatga aylanib qoladi va balandlik n bo'ladi. Farq O(log n) va O(n) o'rtasida.

Daraxtni aylanib chiqish #

Chiziqli tuzilmada bitta yo'l bor - boshidan oxirigacha. Daraxtda esa to'rtta asosiy usul mavjud.

1 2 5 3 4 Preorder ota → chap → o'ng 4 2 5 1 3 Inorder chap → ota → o'ng 5 3 4 1 2 Postorder chap → o'ng → ota 1 2 3 4 5 Level order daraja bo'ylab
Raqamlar tugunlar qanday tartibda tashrif buyurilishini ko'rsatadi
Python
def preorder(tugun, natija=None):
    """Ota -> chap -> o'ng. Daraxt nusxasini yaratish uchun qulay."""
    if natija is None:
        natija = []
    if tugun is not None:
        natija.append(tugun.qiymat)
        preorder(tugun.chap, natija)
        preorder(tugun.ong, natija)
    return natija


def inorder(tugun, natija=None):
    """Chap -> ota -> o'ng. Qidiruv daraxtida tartiblangan ketma-ketlik beradi."""
    if natija is None:
        natija = []
    if tugun is not None:
        inorder(tugun.chap, natija)
        natija.append(tugun.qiymat)
        inorder(tugun.ong, natija)
    return natija


def postorder(tugun, natija=None):
    """Chap -> o'ng -> ota. Daraxtni o'chirish uchun qulay."""
    if natija is None:
        natija = []
    if tugun is not None:
        postorder(tugun.chap, natija)
        postorder(tugun.ong, natija)
        natija.append(tugun.qiymat)
    return natija


print("Preorder: ", preorder(ildiz))
print("Inorder:  ", inorder(ildiz))
print("Postorder:", postorder(ildiz))
Natija
Preorder:  ['A', 'B', 'D', 'E', 'C', 'F']
Inorder:   ['D', 'B', 'E', 'A', 'C', 'F']
Postorder: ['D', 'E', 'B', 'F', 'C', 'A']

Daraja bo'yicha aylanish (BFS) #

Bu yagona usul bo'lib, rekursiya emas, navbat ishlatadi:

Python
from collections import deque


def daraja_boyicha(ildiz):
    """Daraxtni yuqoridan pastga, chapdan o'ngga aylanadi."""
    if ildiz is None:
        return []

    natija = []
    navbat = deque([ildiz])

    while navbat:
        tugun = navbat.popleft()
        natija.append(tugun.qiymat)

        if tugun.chap:
            navbat.append(tugun.chap)
        if tugun.ong:
            navbat.append(tugun.ong)

    return natija


def darajalar_boyicha(ildiz):
    """Har bir darajani alohida ro'yxat qilib qaytaradi."""
    if ildiz is None:
        return []

    darajalar = []
    navbat = deque([ildiz])

    while navbat:
        daraja_hajmi = len(navbat)
        joriy_daraja = []

        for _ in range(daraja_hajmi):
            tugun = navbat.popleft()
            joriy_daraja.append(tugun.qiymat)
            if tugun.chap:
                navbat.append(tugun.chap)
            if tugun.ong:
                navbat.append(tugun.ong)

        darajalar.append(joriy_daraja)

    return darajalar


print("Daraja bo'yicha:", daraja_boyicha(ildiz))
for raqam, daraja in enumerate(darajalar_boyicha(ildiz)):
    print(f"  {raqam}-daraja: {daraja}")
Natija
Daraja bo'yicha: ['A', 'B', 'C', 'D', 'E', 'F']
  0-daraja: ['A']
  1-daraja: ['B', 'C']
  2-daraja: ['D', 'E', 'F']
Qaysi usulni qachon ishlatish kerak?
UsulQachon
PreorderDaraxt nusxasini olish, ifodani prefiks yozuvga o'girish
InorderQidiruv daraxtidan tartiblangan ro'yxat olish
PostorderDaraxtni o'chirish, papka hajmini hisoblash
Level orderEng qisqa yo'l, daraja bo'yicha tahlil

Foydali daraxt funksiyalari #

Python
def balandlik(tugun):
    """Daraxt balandligini qaytaradi. O(n)."""
    if tugun is None:
        return -1
    return 1 + max(balandlik(tugun.chap), balandlik(tugun.ong))


def tugunlar_soni(tugun):
    """Jami tugunlar soni. O(n)."""
    if tugun is None:
        return 0
    return 1 + tugunlar_soni(tugun.chap) + tugunlar_soni(tugun.ong)


def barglar_soni(tugun):
    """Barglar soni. O(n)."""
    if tugun is None:
        return 0
    if tugun.chap is None and tugun.ong is None:
        return 1
    return barglar_soni(tugun.chap) + barglar_soni(tugun.ong)


def muvozanatli_mi(tugun):
    """Daraxt muvozanatli ekanini tekshiradi."""
    def tekshir(t):
        if t is None:
            return 0, True
        chap_balandlik, chap_ok = tekshir(t.chap)
        ong_balandlik, ong_ok = tekshir(t.ong)
        joriy_ok = chap_ok and ong_ok and abs(chap_balandlik - ong_balandlik) <= 1
        return 1 + max(chap_balandlik, ong_balandlik), joriy_ok

    return tekshir(tugun)[1]


print(f"Balandlik:      {balandlik(ildiz)}")
print(f"Tugunlar soni:  {tugunlar_soni(ildiz)}")
print(f"Barglar soni:   {barglar_soni(ildiz)}")
print(f"Muvozanatlimi:  {muvozanatli_mi(ildiz)}")
Natija
Balandlik:      2
Tugunlar soni:  6
Barglar soni:   3
Muvozanatlimi:  True

Daraxtni chiroyli chiqarish #

Nosozlikni tuzatishda juda foydali:

Python
def daraxtni_chiz(tugun, prefiks="", chapmi=True):
    """Daraxtni terminalda ko'rsatadi."""
    if tugun is None:
        return

    daraxtni_chiz(tugun.ong, prefiks + ("|   " if chapmi else "    "), False)
    print(prefiks + ("+-- " if chapmi else "+-- ") + str(tugun.qiymat))
    daraxtni_chiz(tugun.chap, prefiks + ("    " if chapmi else "|   "), True)


daraxtni_chiz(ildiz)
Natija
    +-- F
+-- C
|   +-- E
    +-- A
    |   +-- B
        +-- D

Daraxtlar qayerda ishlatiladi? #

SohaQo'llanilishi
Fayl tizimiPapkalar ierarxiyasi
Veb-brauzerHTML DOM daraxti
Ma'lumotlar bazasiB-daraxt indekslari
KompilyatorlarAbstrakt sintaksis daraxti (AST)
Sun'iy intellektQaror daraxtlari, o'yin daraxtlari
SiqishHuffman kodlash daraxti
TarmoqMarshrutlash jadvallari
Bu saytning o'zi ham daraxt

Ushbu sahifaning HTML tuzilishi - daraxt. <html> ildiz, <body> uning bolasi, har bir <div> va <p> esa pastroq tugunlar. Brauzer sahifani ko'rsatishda aynan shu daraxtni aylanib chiqadi.

Amaliy topshiriq
  1. eng_katta_qiymat(tugun) funksiyasini yozing - daraxtdagi eng katta qiymatni toping.
  2. daraxtlar_bir_xilmi(a, b) - ikki daraxt bir xil ekanini tekshiring.
  3. oynadagi_aks(tugun) - daraxtning chap va o'ng tomonlarini almashtiring.
  4. Berilgan darajadagi tugunlar sonini qaytaruvchi funksiya yozing.
  5. preorder ni rekursiyasiz, stek yordamida qayta yozing.

Xulosa #

  • Daraxt - ierarxik ma'lumotlar uchun tuzilma: ildiz, ichki tugunlar va barglardan iborat.
  • Ikkilik daraxtda har bir tugunning ko'pi bilan ikkita bolasi bo'ladi.
  • Aylanib chiqishning to'rt usuli: preorder, inorder, postorder va daraja bo'yicha.
  • Dastlabki uchtasi rekursiya (stek), oxirgisi navbat ishlatadi.
  • Daraxtdagi amallar tezligi balandlikka bog'liq: muvozanatlida O(log n), muvozanatsizda O(n).

Keyingi bo'limda daraxtga tartib qo'shamiz va uni qidiruv vositasiga aylantiramiz.

Xatolik topdingizmi?

Imlo xatosi, ishlamaydigan kod yoki noto‘g‘ri ma‘lumotni ko‘rsangiz - bizga xabar bering. Har bir xabar administrator tomonidan ko‘rib chiqiladi.