KAL
Menu

Pola rekursi pada pohon

Soal kedalaman, diameter, dan lintasan dengan pola rekursi pohon.

Daftar isi

Pola paling umum pada soal pohon membangun jawaban sebuah node dari jawaban kedua anaknya, lalu menggabungkannya dengan kontribusi node itu sendiri. Bentuk pikirannya persis postorder, dan modul rekursi sudah menyiapkan kepercayaan bahwa pemanggilan yang lebih kecil bekerja dengan benar. Topik ini menerapkan pola itu pada tiga soal klasik, yaitu kedalaman maksimum, diameter, dan pemeriksaan pohon seimbang, semuanya pada pohon contoh tetap dan ditutup dengan sekumpulan soal untuk dipraktikkan.

Pola jawaban dari anak#

Sebuah subtree adalah pohon utuh yang lebih kecil, sehingga jawaban untuk sebuah node dapat dirakit begitu jawaban untuk kedua subtree-nya diketahui. Kerangkanya selalu sama, yaitu kasus dasar untuk pohon kosong, dua pemanggilan rekursif untuk kedua anak, dan satu langkah penggabungan.

python 
# tidak-dijalankan
# templat umum pola postorder pada pohon
def solve(node):
    if node is None:
        return nilai_dasar            # kasus dasar, subtree kosong
    kiri = solve(node.kiri)           # percayai jawaban subtree kiri
    kanan = solve(node.kanan)         # percayai jawaban subtree kanan
    return gabungkan(node, kiri, kanan)

Nilai kiri dan kanan pada templat itu adalah jawaban yang sudah jadi, dan seluruh kecerdasan soal terkonsentrasi pada langkah penggabungan. Soal kedalaman menggabungkan dengan max lalu menambah satu, diameter menggabungkan dengan penjumlahan, dan pemeriksaan seimbang menggabungkan dengan pemeriksaan selisih. Mengenali soal baru sebagai instans templat ini memangkas waktu berpikir pada wawancara, karena yang tersisa hanya memutuskan apa yang dikembalikan dan bagaimana menggabungkannya. Tiga fungsi pada berkas berikut adalah tiga pengisi templat yang berbeda pada pohon contoh yang sama.

Tiga pola dalam satu berkas#

Berkas pola-rekursi.py memuat ketiga fungsi lengkap dengan pohon contoh tujuh node dan satu pohon rantai sebagai pembanding.

python pola-rekursi.py 
"""Tiga pola rekursi pohon: kedalaman maksimum, diameter, dan pemeriksaan seimbang."""

class Node:
    def __init__(self, nilai):
        self.nilai = nilai
        self.kiri = None
        self.kanan = None

def kedalaman_maks(akar):
    # kedalaman dihitung dalam jumlah node, pohon kosong bernilai 0
    if akar is None:
        return 0
    return 1 + max(kedalaman_maks(akar.kiri), kedalaman_maks(akar.kanan))

def diameter(akar):
    terbaik = 0

    def tinggi(node):
        nonlocal terbaik
        if node is None:
            return 0
        kiri = tinggi(node.kiri)
        kanan = tinggi(node.kanan)
        # jalur terbaik boleh melewati node mana pun, tidak wajib lewat akar
        terbaik = max(terbaik, kiri + kanan)
        return 1 + max(kiri, kanan)

    tinggi(akar)
    return terbaik

def seimbang(akar):
    # kembalikan tinggi subtree, atau -1 bila ketimpangan lebih dari satu
    def tinggi(node):
        if node is None:
            return 0
        kiri = tinggi(node.kiri)
        if kiri == -1:
            return -1          # subtree kiri sudah timpang, potong cabang
        kanan = tinggi(node.kanan)
        if kanan == -1:
            return -1
        if abs(kiri - kanan) > 1:
            return -1
        return 1 + max(kiri, kanan)
    return tinggi(akar) != -1

def bangun_pohon():
    # pohon contoh tetap
    n = {v: Node(v) for v in [50, 30, 70, 20, 40, 60, 80]}
    n[50].kiri, n[50].kanan = n[30], n[70]
    n[30].kiri, n[30].kanan = n[20], n[40]
    n[70].kiri, n[70].kanan = n[60], n[80]
    return n[50]

pohon = bangun_pohon()
print("kedalaman maksimum :", kedalaman_maks(pohon))
print("diameter           :", diameter(pohon))
print("seimbang           :", seimbang(pohon))

# pohon rantai: 1 ke kanan 2, lalu 3, lalu 4
rantai = Node(1)
rantai.kanan = Node(2)
rantai.kanan.kanan = Node(3)
rantai.kanan.kanan.kanan = Node(4)
print("kedalaman rantai   :", kedalaman_maks(rantai))
print("rantai seimbang    :", seimbang(rantai))
text Keluaran 
kedalaman maksimum : 3
diameter           : 4
seimbang           : True
kedalaman rantai   : 4
rantai seimbang    : False

Kedalaman maksimum dihitung dalam jumlah node, sehingga pohon kosong bernilai 0 dan pohon contoh bernilai 3 karena jalur 50, 30, 20 memuat tiga node. Konvensi ini mengikuti soal maximum depth pada judge daring, dan bila soal memintanya dalam sisi, cukup kurangi satu dari hasilnya. Pohon rantai memberikan kedalaman 4 karena seluruh node tersusun satu garis. Nilai True pada pohon contoh dan False pada rantai berasal dari fungsi yang sama tanpa parameter tambahan, dan dua nilai lainnya dibedah pada dua bagian berikutnya.

Diameter dengan pelacakan terbaik#

Diameter didefinisikan sebagai banyaknya sisi pada jalur terpanjang antara dua node, dan jalur itu tidak wajib melewati akar. Pada node mana pun, jalur terbaik yang berbelok di node tersebut memuat kaki kiri sepanjang tinggi subtree kiri dan kaki kanan sepanjang tinggi subtree kanan, sehingga kandidat jawaban di setiap node adalah kiri + kanan. Yang menjebak adalah nilai yang seharusnya dikembalikan ke induk, karena induk hanya dapat memanfaatkan satu kaki jalur, yaitu 1 + max(kiri, kanan), bukan jumlah keduanya.

Di sinilah variabel terbaik berperan. Variabel itu menyimpan kandidat terbaik dari seluruh node yang pernah dikunjungi, diperbarui dengan nonlocal agar hidup di luar fungsi tinggi, dan nilai akhirnya adalah diameter. Kombinasi kembalian fungsi untuk kebutuhan induk dan variabel pelacak untuk jawaban global muncul di banyak soal jalur, termasuk variasi yang menghitung jumlah nilai node. Diagram berikut menyorot jalur diameter 20, 30, 50, 70, 80 sepanjang empat sisi pada pohon contoh, dan pada pohon lain jalur semacam ini bisa sepenuhnya berada di bawah akar.

diameter = jalur terpanjang, tidak wajib melewati akar50307020406080jalur 20 → 30 → 50 → 70 → 80 memuat 4 sisi
Diameter pohon contoh berupa jalur 20, 30, 50, 70, 80 sepanjang empat sisi yang disorot merah

Pemeriksaan pohon seimbang#

Pohon disebut seimbang (balanced) bila selisih tinggi subtree kiri dan kanan tidak lebih dari satu pada setiap node, bukan hanya pada akar. Cara lambat memanggil fungsi tinggi terpisah untuk setiap node berbiaya O(n2)O(n^2) pada pohon rantai, karena tinggi yang sama dihitung berulang-ulang. Versi yang tepat menggabungkan dua tugas dalam satu fungsi, mengembalikan tinggi subtree bila seimbang, atau -1 segera setelah ketimpangan ditemukan. Nilai -1 bekerja sebagai sinyal gagal yang merambat naik. Setiap induk yang menerima -1 dari anaknya langsung meneruskan -1 tanpa menghitung apa pun lagi, sehingga cabang yang sudah gagal dipotong dari seluruh pekerjaan sisanya.

Fungsi seimbang pada pola-rekursi.py menutup pemeriksaan dengan perbandingan tinggi(akar) != -1, dan keluaran menunjukkan True untuk pohon contoh serta False untuk rantai empat node. Pada rantai itu, ketimpangan pertama ditemukan di node 2 yang selisih kakinya bernilai 2, lalu sisanya berhenti tanpa pekerjaan tambahan. Kombinasi kembalian ganda, yaitu data saat sehat dan sinyal saat gagal, layak dijadikan pola bawaan untuk soal yang menuntut pemeriksaan dini.

Soal untuk dipraktikkan#

Ketujuh soal berikut melatih pola pada topik ini, semuanya berada di daftar soal pohon yang lazim diminta dan dapat diselesaikan dengan templat pada bagian pertama.

Ringkasan#

  • Pola inti soal pohon merakit jawaban node dari jawaban kedua anak lalu menggabungkannya, bentuknya persis postorder.
  • Kedalaman maksimum dihitung 1 + max(kedalaman anak) dengan pohon kosong bernilai 0.
  • Diameter diperoleh dari kandidat kiri + kanan di setiap node yang dilacak variabel terpisah, sementara fungsi mengembalikan satu kaki saja.
  • Pemeriksaan seimbang mengembalikan tinggi atau -1 sehingga cabang yang sudah gagal tidak dihitung lagi.

Referensi#