Struktur Bercabang · Pelajaran 7 dari 10

Tree dan binary search tree

11 menit baca · BelajarCode

Tree (pohon) adalah struktur bercabang: satu simpul akar (root) di puncak, setiap simpul punya anak, dan simpul tanpa anak disebut daun (leaf). Struktur folder di komputer dan silsilah keluarga adalah contoh tree.

Binary search tree

Binary search tree (BST) adalah tree dengan paling banyak dua anak per simpul, dan aturan: semua nilai di subpohon kiri lebih kecil dari simpul, semua nilai di subpohon kanan lebih besar.

Bentuk BST setelah memasukkan 50, 30, 70, 20, 40, 60, 80

        50
       /  \
     30    70
    /  \  /  \
   20  40 60  80

Python

1class Simpul:2    def __init__(self, nilai):3        self.nilai = nilai4        self.kiri = None5        self.kanan = None678class BST:9    def __init__(self):10        self.akar = None1112    def masukkan(self, nilai):13        if self.akar is None:14            self.akar = Simpul(nilai)15            return16        sekarang = self.akar17        while True:18            if nilai < sekarang.nilai:19                if sekarang.kiri is None:20                    sekarang.kiri = Simpul(nilai)21                    return22                sekarang = sekarang.kiri23            else:24                if sekarang.kanan is None:25                    sekarang.kanan = Simpul(nilai)26                    return27                sekarang = sekarang.kanan2829    def cari(self, nilai):30        sekarang = self.akar31        langkah = 032        while sekarang is not None:33            langkah += 134            if nilai == sekarang.nilai:35                return True, langkah36            sekarang = sekarang.kiri if nilai < sekarang.nilai else sekarang.kanan37        return False, langkah3839    def inorder(self):40        hasil = []41        def jalan(s):42            if s is not None:43                jalan(s.kiri)44                hasil.append(s.nilai)45                jalan(s.kanan)46        jalan(self.akar)47        return hasil4849    def tinggi(self):50        def t(s):51            if s is None:52                return 053            return 1 + max(t(s.kiri), t(s.kanan))54        return t(self.akar)555657pohon = BST()58for x in [50, 30, 70, 20, 40, 60, 80]:59    pohon.masukkan(x)60print("Inorder:", pohon.inorder())61print("Cari 60:", pohon.cari(60))62print("Cari 65:", pohon.cari(65))63print("Tinggi:", pohon.tinggi())

Keluaran

Inorder: [20, 30, 40, 50, 60, 70, 80]
Cari 60: (True, 3)
Cari 65: (False, 3)
Tinggi: 3

Penelusuran inorder (kiri, simpul, kanan) selalu menghasilkan data terurut.
Pencarian membuang setengah pohon di setiap langkah, mirip pencarian biner. Untuk pohon yang seimbang, kompleksitasnya O(log n).

Pohon yang tidak seimbang

Jika data dimasukkan dalam keadaan sudah urut, BST berubah menjadi rantai panjang:

Python

1class Simpul:2    def __init__(self, nilai):3        self.nilai = nilai4        self.kiri = None5        self.kanan = None678def masukkan(akar, nilai):9    if akar is None:10        return Simpul(nilai)11    if nilai < akar.nilai:12        akar.kiri = masukkan(akar.kiri, nilai)13    else:14        akar.kanan = masukkan(akar.kanan, nilai)15    return akar161718def tinggi(s):19    return 0 if s is None else 1 + max(tinggi(s.kiri), tinggi(s.kanan))202122acak = None23for x in [50, 30, 70, 20, 40, 60, 80, 10, 90, 35]:24    acak = masukkan(acak, x)25urut = None26for x in range(1, 11):27    urut = masukkan(urut, x)28print("Tinggi BST dari data acak:", tinggi(acak))29print("Tinggi BST dari data urut:", tinggi(urut))

Keluaran

Tinggi BST dari data acak: 4
Tinggi BST dari data urut: 10

Pada kasus terburuk ini, pencarian menjadi O(n). Pohon seimbang seperti AVL tree dan red-black tree memutar simpul secara otomatis saat memasukkan data, sehingga tingginya selalu O(log n). Struktur seperti TreeMap di Java dibangun dari red-black tree.

Cek pemahaman

Pada BST, di mana letak nilai terkecil?

Di salah satu daun, tergantung urutan memasukkanDi simpul paling kanan, dengan terus bergerak ke kananSelalu di akar pohon, karena dimasukkan pertamaDi simpul paling kiri, dengan terus bergerak ke kiri

Latihan

Nilai terkecil dan banyak simpul

Tulis fungsi terkecil(akar) dan fungsi rekursif banyak_simpul(akar). Uji dengan BST dari data 50, 30, 70, 20, 40, 60, 80, 10.

Pembahasan

Python

1class Simpul:2    def __init__(self, nilai):3        self.nilai = nilai4        self.kiri = None5        self.kanan = None678def masukkan(akar, nilai):9    if akar is None:10        return Simpul(nilai)11    if nilai < akar.nilai:12        akar.kiri = masukkan(akar.kiri, nilai)13    else:14        akar.kanan = masukkan(akar.kanan, nilai)15    return akar161718def terkecil(akar):19    sekarang = akar20    while sekarang.kiri is not None:21        sekarang = sekarang.kiri22    return sekarang.nilai232425def banyak_simpul(akar):26    if akar is None:27        return 028    return 1 + banyak_simpul(akar.kiri) + banyak_simpul(akar.kanan)293031akar = None32for x in [50, 30, 70, 20, 40, 60, 80, 10]:33    akar = masukkan(akar, x)34print("Terkecil:", terkecil(akar))35print("Banyak simpul:", banyak_simpul(akar))

Keluaran

Terkecil: 10
Banyak simpul: 8

Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.

Tree dan binary search tree

Binary search tree

Pohon yang tidak seimbang

Nilai terkecil dan banyak simpul

Tandai pelajaran ini selesai