Struktur Data: Pohon
Posting ini adalah yang ketiga dari seri tentang struktur data. Topik yang dibahas dalam seri ini adalah 6 struktur data utama yang akan muncul dalam segala jenis wawancara rekayasa perangkat lunak:
Apa itu Pohon?
Pohon adalah struktur data non-linier yang mengatur data secara hierarki. Anda dapat menyamakannya dengan silsilah keluarga dengan banyak generasi; kakek-nenek, orang tua, anak-anak, dll. Pohon keluarga disusun secara hierarkis.
Struktur data pohon adalah kumpulan node. Node-node ini terhubung satu sama lain melalui tepi. Setiap node berisi nilai (data) dan mungkin memiliki atau tidak memiliki node anak. Di setiap pohon (yang tidak kosong), simpul pertama dari pohon tersebut disebut root.
Jika node akar ini terhubung ke satu atau lebih node, maka node tersebut adalah node induk dan node yang terhubung tersebut adalah anak-anaknya. Node yang tidak memiliki anak disebut daunatau simpul eksternal. Node yang bukan daun disebut node internal. Node internal memiliki setidaknya satu anak. Node dengan induk yang sama dikatakan sebagai saudara.
Pada pohon di atas:
- A adalah induk dari B dan C.
- B disebut anak dari A.
- B dan C adalah saudara kandung.
- E, F, H, I, dan J adalah daun.
kedalaman suatu simpul adalah jumlah tepi dari akar ke simpul tersebut. (Panjang jalan menuju akarnya). Pada pohon di atas, kedalaman node I adalah 3.
Tinggi sebuah node adalah jumlah tepi dari node hingga daun terdalam. (Panjang jalur terpanjang menuju sebuah daun). Ketinggian simpul B adalah 2.
Pohon Biner
Node pohon dapat mempunyai nol atau lebih anak. Pohon Biner adalah pohon yang simpul-simpulnya tidak boleh mempunyai lebih dari dua simpul anak. Setiap node dapat memiliki node kiri dan node kanan.
Node pohon biner biasanya berisi tiga bagian data:
- nilai simpul: Bilangan bulat, string, karakter, dll.
- Penunjuk ke anak kiri.
- Penunjuk ke anak kanan.
Pohon Penelusuran Biner
Pohon pencarian biner adalah pohon biner yang memenuhi properti pemesanan tertentu:
Pada subpohon mana pun, simpul kiri lebih kecil dari simpul akar, yang berarti lebih kecil dari seluruh simpul kanan.
Properti pengurutan ini membuat pencarian node tertentu menjadi sangat cepat karena Anda dapat mengetahui di mana mencarinya di dalam pohon tergantung pada nilai yang Anda cari.
Katakanlah kita mencari node yang berisi nilai 4:
Pertama kita lihat node root = 10. 4 kurang dari 10 sehingga simpulnya harus berada di sisi kiri.
Kami kemudian melihat anak kiri = 5. 4 kurang dari 5 sehingga simpulnya harus berada di sisi kiri.
Anak kiri adalah = 3. 4 lebih besar dari 3 sehingga simpulnya harus berada di sisi kanan.
Anak yang tepat adalah 4! Kita telah mencapai simpul yang kita cari. Dengan setiap langkah, kita mengabaikan separuh pohon.
Penyisipan di Pohon Pencarian Biner
Mari kembali ke contoh Pohon Pencarian Biner kita:
Katakanlah kita ingin menambahkan nilai 6.
- Kita melihat simpul akar = 10. 6 kurang dari 10 jadi kita lanjutkan ke anak kiri.
- Anak kiri berusia 5. 6 lebih besar dari 5 jadi kita pilih anak kanannya.
- Anak yang tepat adalah 9. 6 kurang dari 9 jadi kita lanjutkan ke anak kiri.
- Anak kiri adalah nol. Kita dapat menempatkan node kita di sana.
Dengan menggunakan metode penyisipan ini, terkadang kita dapat memiliki pohon yang tidak seimbang, bergantung pada cara kita menerima node untuk disisipkan dan cara kerja algoritme konstruksi pohon.
Dalam skenario terburuk, jika kita menerima node: 1 → 2 → 3 → 4, kita bisa mendapatkan pohon seperti ini:
Tidak ideal. Pohon ini terlihat seperti daftar tertaut. Pencarian dan penyisipan tidak lagi secepat pohon. Pohon pencarian biner seimbang dapat dicari dalam waktu O(log n), dimana n adalah jumlah node dalam pohon. Pohon yang tidak seimbang seperti di atas akan memakan waktu O(n) (waktu linier).
Traversal Pohon Pencarian Biner
Ada tiga cara kita dapat melintasi pohon:
- In-Order Traversal: Kunjungi node kiri terlebih dahulu, lalu root, lalu kanan. A → B → C.
- Pre-Order Traversal: Kunjungi root terlebih dahulu, lalu kunjungi node kiri, lalu kanan. B → A → C.
- Traversal Pasca Pesanan: Kunjungi node kiri terlebih dahulu, lalu node kanan, lalu root. A →C →B.
Di Pohon Pencarian Biner, kami biasanya ingin menggunakan traversal In-Order karena memungkinkan kami mencetak node secara berurutan.
Dua algoritma yang umum digunakan untuk traversal adalah Depth-First-Search (DFS) dan Breadth-First-Search (BFS). Dalam Pencarian Mendalam-Pertama, kita mulai dari akar dan menjelajah sejauh mungkin ke setiap cabang sebelum melakukan penelusuran mundur. Traversal In-Order, Pre-Order, dan Post-Order semuanya termasuk dalam DFS. Dalam Pencarian Luas-Pertama, kita mulai dari akar dan menjelajahi simpul-simpul tetangga sebelum turun ke tingkat berikutnya.
Menerapkan Pohon Pencarian Biner
Mari buat kelas Node:
Node kita memiliki tiga bagian: nilai, penunjuk kiri, dan penunjuk kanan. Pointer kami awalnya disetel ke null karena node kami belum memiliki anak.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
Insersi
Mari buat metode untuk Penyisipan:
Jika nilai yang ingin kita tambahkan kurang dari atau sama dengan nilai node saat ini, kita periksa apakah kiri. Jika anak kiri kosong, kita membuat node baru dengan nilai kita dan menambahkannya di sana. Jika tidak kosong, kita secara rekursif memanggil fungsi penyisipan di cabang kiri pohon kita.
Jika nilai yang ingin kita tambahkan lebih besar dari node saat ini, kita centang di sebelah kanan. Jika anak kanan kosong, kita membuat node baru dengan nilai kita dan menambahkannya di sana. Jika tidak kosong, kami secara rekursif memanggil fungsi penyisipan di cabang kanan pohon kami.
def insert(self, value):
if value <= self.value:
if self.left == None:
self.left = Node(value)
else:
self.left.insert(value)
else:
if self.right == None:
self.right = Node(value)
else:
self.right.insert(value)
Menemukan
Metode selanjutnya yang ingin kita tambahkan adalah find. Find juga beroperasi secara rekursif dan mirip dengan insert dalam beberapa hal. find akan mengambil nilai dan mengembalikan nilai true jika ditemukan dan false jika tidak.
Kita mulai dari akarnya. Jika nilai root sama dengan nilai yang kita cari, kita mengembalikan nilai true. Jika tidak, kita periksa apakah nilainya lebih kecil dari nilai node akar. Jika kurang, kita periksa apakah yang kiri kosong. Jika kiri kita kosong berarti pohon tersebut tidak mengandung nilai yang kita cari. Jika left menunjuk ke sebuah node, kita memanggil metode find secara rekursif untuk memeriksa nilainya di sisi kiri pohon.
Jika nilai yang kita cari lebih besar dari nilai pada node akar, kita periksa apakah node kanan kosong. Jika demikian, kami mengembalikan false karena pohon kami tidak mengandung nilai tersebut. Jika sisi kanan tidak kosong, kita memanggil metode find di sisi kanan pohon secara rekursif.
def find(self, value):
if value == self.value:
return True
elif value < self.value:
if self.left == None:
return False
else:
return self.left.find(value)
else:
if self.right == None:
return False
else:
return self.right.find(value)
Cetak (Pencarian Pertama Kedalaman)
Mari kita menulis metode pencetakan DFS In-Order untuk kelas Node kita. Seperti disebutkan di atas, In-Order mencetak node kiri, lalu root, lalu node kanan.
Dalam metode kami, pertama-tama kami memeriksa apakah sisi kiri pohon tidak kosong. Jika kita mempunyai sisi kiri, kita memanggil metode kita secara rekursif untuk sisi kiri pohon.
Ketika kita mencapai titik di mana sisi kiri sebuah node bernilai nol, kita mencetak nilai dari node tersebut. Kami kemudian kembali ke langkah untuk mencetak root. Selanjutnya, kita periksa apakah sisi kanan node tidak kosong. Jika ada node di sebelah kanan, kita memanggil metode kita secara rekursif pada node kanan tersebut.
def printInOrder(self):
if self.left != None:
self.left.printInOrder()
print(self.value)
if self.right != None:
self.right.printInOrder()
Dan itu saja untuk saat ini!
Jika Anda ingin mengetahui cara menerapkan metode Breadth First Search, biasanya metode ini dilakukan dengan menggunakan struktur data Antrian sebagai pembantu. Saya akan meliput Antrean di postingan berikutnya dari seri ini, jadi pantau terus!
Terima kasih sudah membaca!
