Struktur Data: Tree

Halo teman-teman! Gimana kabarnya nih? Semoga lebih baik dari kemarin ya. Senang dapat berjumpa lagi pada pembahasan terkait struktur data Tree.

Struktur data Tree merupakan struktur data non-linear yang tersususn secara hierarkis dan tersusun dari elemen-elemen bernama node. Setiap tree memiliki satu node utama/root dan node lain yang terhubung (child). Antar node dihubungkan dengan edge, dan tidak boleh membentuk siklus karena hanya memiliki satu jalur dari root ke setiap node. Tree efisien untuk menyimpan data yang saling berelasi dalam bentuk bertingkat.

Jenis-Jenis Tree:

1 . Binary Tree, merupakan struktur data pohon yang setiap node maksimal memiliki dua anak, left child dan right child. Biasanya digunakan untuk memroses data percabangan dua arah.

Istilah dalam binary tree:

• Root: node utama
• Leaf Node: node tanpa anak
• Internal Node: node dengan maksimal satu anak
• Heigt/Depth: panjang jalur root ke node terdalam
• Level: kedalaman node dari root
• Subtree: bagian tree dari node hingga keturunannya

Variasi Binary Tree:

• Full Binary Tree: node memiliki dua anak atau tidak memiliki
• Complete Binary Tree: level terisi penuh kecuali level terakhir yang diisi dari kiri ke kanan
• Perfect Binary Tree: semua node memiliki dua anak dan semua daun berlevel sama
• Skewed Binary Tree: tidak seimbang, anak hanya di kiri atau kanan (mirip likned list

Binary Tree memiliki kelebihan yaitu memungkinkan representasi data hierarkis yang efisien, cocok untuk transversal rekursif dengan tiga metode utama, dan lebih hemat memori. Kekurangannya sendiri adalah tidak menjamin efisiensi pencarian jika struktur tidak seimbang, tidak cocok untuk data yang perlu lebih dari dua anak per node, dan perlunya penyeimbangan ulang jika ingin performa optimal.

2. Binary Searc Tree(BST), bentuk khusus binary tree dengan aturan penempatan nilai semua nilai di anak kiri harus lebih kecil dari nilai di kode induk, dan nilai anak kanan harus lebih besar. Sehingga cara kerjanya bergantung pada urutan data yang dimasukkan, pencarian rata-rata O(log n) jika data acak dan seimbang lalu O(n) jika data urut naik atau turun.

Kelebihan dari BST adalah efisien untuk operasi pencarian, penyisipan, dan penghapusan, struktur transfersal inordernya menghasilkan data terurut, dan cocokk untuk aplikasi yang memerlukan pencarian cepat dan pengurutan. Kekurangan BST sendiri yakni tidak menjamin keseimbangan apabila data tidak merata yang menyebabkan performa menurun, perlu menambah algoritma balancing agar performa tetap optimal, dan penghapusan node dalam BST lebih kompleks dibanding penyisipan atau pencarian, terutama untuk node dua anak.

3. Transfersal pada Tree, proses untuk mengunjungi setiiap node dalam struktur pohon secara sistematis. Bertujuan untuk membaca, memproses, atau menapilkan isi tree sesuai urutan berdasarkan parent-child.

Tiga metode utamanya adalah:

• Preorder (Root-Left-Right), proses dari node akar, anak kiri lalu anak kanan.
• Inorder (Left-Root-Right), menghasilkan nilai dari terkecil ke besar dengan menelusuri anak kiri, node induk, kemudian anak kanan.
• Postorder (Left-Right-Root), subtree diproses awal, lalu node induknya.

Membuat Binary Tree Secara Manual

Untuk membuat Binary Tree secara manual langkah awal sebelum menyususnnya adalah membuat struktur dasar Node. Berikut contoh struktur tree-nya:

# Kelas Node
class Node:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None

# Membuat tree secara manual
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)

# Fungsi inorder tranversal
def inorder(root):
  if root:
    inorder(root.left)
    print(root.data)
    inorder(root.right)

print ("Hasil inorder tranversal dari binary tree:")
inorder(root)

# Output
Hasil inorder tranversal dari binary tree:
4
2
5
1
3

• Dasar Node berisi data juga pointer anak kiri ke kanan.
• Membuat tree secara manual dimulai dengan membuat root yang berfungsi sebagai akar pohon kemudian menambahakan anak-anaknya secara eksplisit.
• Fungsi inorder transversal berguna untuk menelusuri tree dari node terkiri, induk, lalu anak kanan.
• Output menunjukkan urutan node berdasar struktur tersebut.

Struktur binary tree

Membuat Binary Search Tree

Kali ini tree akan dibuat secara otomatis mengikuti aturan BST yakni data lebih kecil dari root akan diletakkan di kiri, dan data besar di kanan.

# Kelas Node
class Node:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None

# Kelas BinarySearchTree
class BinarySearchTree:
  def __init__(self):
    self.root = None
  # Fungsi insert
  def insert(self, root, data):
    if root is None:
      return Node(data)
    if data < root.data:
      root.left = self.insert(root.left, data)
    else:
      root.right = self.insert(root.right, data)
    return root

# Membuat instance BST
bst = BinarySearchTree()
root = None

# Data input
data_list = [50, 30, 70, 20, 40, 60, 80]

# Menyisipkan setiap nilai dari data_list ke dalam BST
for value in data_list:
  root = bst.insert(root, value)

• class BinarySearcgTree dan fungsi insert() menyisipkan data sesuai aturan BTS.
• Ketika node kosong, node baru akan dibuat.
• Ketika data lebih kecil dari nilai induk, data akan berada di kiri dan jika lebih besar, data akan dikanan.
• data_list digunakan untuk menguji fungsi penyisipan, dan tree akan terbentuk otomatis tanpa pengaturan manual.

Berikut hasil strukturnya:

Struktur pohon Bst yang terbentuk

Transversal pada BST

# inorder transversal
def inorder(node):
  if node:
    inorder(node.left)
    print(node.data, end='')
    inorder(node.right)

# preorder transversal
def preorder(node):
  if node:
    print(node.data, end='')
    preorder(node.left)
    preorder(node.right)

# postorder tranaversal
def postorder(node):
  if node:
    postorder(node.left)
    postorder(node.right)
    print(node.data, end='')

# Cetak
print("Inorder Transversal:")
inorder(root)
print("\nPreorder Transversal:")
preorder(root)
print("\nPostorder Transversal:")
postorder(root)

# Output
Inorder Transversal:
20304050607080
Preorder Transversal:
50302040706080
Postorder Transversal:
20403060807050

• Inorder menampilkan data dari terkecil ke terbesar.
• Preorder mencetak struktur tree dari root ke bawah.
• Postorder mencetak node setelah seluruh subtree selesai diproses.

Pencarian Nilai dalam BST

Pencarian elemen menggunakan metode rekursif.

# Fungsi search
def search(node, key):
  if node is None or node.data == key:
    return node
  if key < node.data:
    return search(node.left, key)
  return search(node.right, key)

# Uji pencarian
key = 60
result = search(root, key)
if result:
  print(f"{key} ditemukan dalam tree.")
else:
  print(f"{key} tidak ditemukan")

key = 25
result = search(root, key)
if result:
  print(f"{key} ditemukan dalam tree.")
else:
  print(f"{key} tidak ditemukan")

# Output
60 ditemukan dalam tree.
25 tidak ditemukan

• Fungsi search() digunakan untuk mencari elemen dalam BST.
• Algoritma akan membandigkan nilai target dengan nilai node saat ini. Jika sama akan dikembalikan, apabila lebih kecil akan dilanjutkan oencarian ke subtree kiri dan ke kanan apabila lebih besar. Kemudian akan dicetak apakah data ditemukan atau tidak.

TUGAS 1: Program Struktur Binary Tree Manual

Deskripsi: Buat program Python untuk membangun binary tree secara manual (bukan BST) berdasarkan data yang Anda olah dari nama dan NPM.

Ketentuan:

1. Node root adalah jumlah huruf pada nama lengkap Anda.
2. Anak kiri root: jumlah huruf vokal (a, i, u, e, o) pada nama Anda.
3. Anak kanan root: dua digit terakhir dari NPM Anda.
4. Tambahkan satu level lanjutan (anak dari anak) berdasarkan tanggal lahir Anda:

• Anak kiri dari node kiri: tanggal lahir (DD).
• Anak kanan dari node kanan: bulan lahir (MM).

5. Tampilkan tree dengan inorder traversal.

Output yang Diharapkan:

• Struktur tree ditampilkan menggunakan print traversal.
• Tambahkan komentar di atas program: “Struktur Tree berdasarkan identitas saya”.

Kode Program:

Penjelasan:

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

• Class Node berfungsi untuk merepresentasikan setiap simpul dalam binary tree.
• data akan menyimpan nilai node.
• left dan right menunjuk ke anak kiri dan anak kanan dengan default None.

def inorder(root):
    if root:
        inorder(root.left)
        print(root.data, end=' ')
        inorder(root.right)

• Inorder transversal berfungsi untuk mengunjungi anak kiri terlebih dahulu dan mencetak nilai kodenya kemudian mengunjungi anak kanan.
• Transversal ini berguna untuk menampilkan isi tree secara terurut berdasarkan struktur.

root = Node(14)

• Membuat node root dengan nilai 14 yang merupakan jumlah huruf dari nama lengkap.

root.left = Node(8)

• Membuat aak kiri dari root dengan nilai 8 yang merupakan jumlah huruf vokal pada nama.

root.right = Node(8)

• Membuat anak kanan root dengan nilai 8 yang merupakan perwakilan dari dua digit terakhir NPM yakni 08.

root.left.left = Node (12)

• Menambahakan cucu kiri dari anak kiri root dengan nilai 12 yang mewakili tanggal lahir.

root.right.right = Node(12)

• Menambahkan cucu kanan dari anak kanan root dengan nilai 12 yang mewakili bulan lahir.

print("Struktur Tree berdasarkan identitas saya")

• Menampilkan teks keterangan.

inorder(root)

• Menjalankan fungsi inorder() dari root untuk mencetak isi tree secara inorder.

Output:

Gambar diatas menunjukkan output yang didapatkan dari fungsi inorder.

TUGAS 2: Program Binary Search Tree (BST)

Deskripsi: Buat program Python untuk membentuk BST secara otomatis dari data numerik yang unik bagi Anda.

Ketentuan:

1. Buat daftar 7 angka dengan aturan berikut:

• Tiga digit terakhir NPM Anda.
• Tanggal lahir (DDMM, pisahkan menjadi dua angka: DD dan MM).
• ASCII dari huruf pertama dan kedua nama depan Anda.
• Tambahkan dua angka bebas (boleh favorit Anda).

2. Sisipkan semua angka tersebut ke dalam BST.

3. Tampilkan hasil traversal:

• Inorder
• Preorder
• Postorder

4. Tambahkan fitur pencarian:

• Cari angka dengan nilai dua digit terakhir NPM Anda.
• Cari angka yang tidak termasuk dalam list (buat sendiri angkanya).

Output yang Diharapkan:

• Hasil setiap traversal tercetak rapi.
• Hasil pencarian menunjukkan apakah data ditemukan atau tidak.
• Tambahkan komentar penjelasan pendek di setiap bagian kode.

Kode Program:

Penjelasan:

class BSTNode:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

• class BSTNode untuk merepresentasikan setiap node dalam BST.
• data berguna untuk menyimpan nilai dari node.
• left dan right digunakan untuk menunjuk anak kiri dan kanan dengan default None.

def insert(root, key):
    if root is None:
        return BSTNode(key)
    if key < root.data:
        root.left = insert(root.left, key)
    else:
        root.right = insert(root.right, key)
    return root

• Fungsi rekursif diatas digunakan untuk menyisipkan key ke dalam BST.
• if key > root.data akan dijalankan jika key lebih kecil kemudian nilai key akan dimasukkan ke kiri.
• else dijalankan jika key lebih besar atau sama kemudian nilai key akan dimasukkan ke kanan.
• Lalu root akan dikembalikan untuk mempertahankan struktur tree.

def inorder(node):
    if node:
        inorder(node.left)
        print(node.data, end=' ')
        inorder(node.right)

def preorder(node):
    if node:
        print(node.data, end=' ')
        preorder(node.left)
        preorder(node.right)

def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data, end=' ')

Fungsi di atas akan mencetak isi tree sesuai urutan transversal yang dimaksud. Digunakan untuk menampilkan urutan kunjungan node dari BST.

Berikut penjelasan untuk urutan pencetakannya:

• Inorder menampilkan data dari terkecil ke terbesar.
• Preorder mencetak struktur tree dari root ke bawah.
• Postorder mencetak node setelah seluruh subtree selesai diproses.

data_list = [8, 12, 12, 82, 65, 3]

bst_root = None
for item in data_list:
    bst_root = insert(bst_root, item)

• List berisi angka yang akan dimasukkan ke BST dengan urutan 2 digit NPM (08), tanggal lahir, bulan lahir, ASCII huruf nama, dan angka bebas.
• Kemudian angka disisipkan ke tree dengan fungsi insert.

print("Inorder Traversal:")
inorder(bst_root)
print("\nPreorder Traversal:")
preorder(bst_root)
print("\nPostorder Traversal:")
postorder(bst_root)

• Menampilkan hasil transversal dalam tiga format yaitu inorder, preorder dan postorder seperti fungsi yang telah dituliskan dalam kode.

Output:

Gambar menunjukkan bahwa kode program yang dijalankan telah sesuai dengan yang diharapkan.

Struktur data Tree, termasuk Binary Tree dan Binary Search Tree, digunakan untuk menyimpan dan mengelola data secara hierarkis. Binary Tree cocok untuk representasi struktur berjenjang, sedangkan Binary Search Tree memudahkan pencarian, penyisipan, dan penghapusan data secara efisien. Pemilihan jenis tree tergantung pada kebutuhan penyimpanan dan akses data dalam suatu aplikasi.

Github latihan:

[embed]praktikumsemester2_strukturdata/2410506008_Strukdat_Tree.ipynb at main ·… Contribute to Rahma-dwi-kartika-sari/praktikumsemester2_strukturdata development by creating an account on GitHub.github.com

Github tugas:

[embed]praktikumsemester2_strukturdata/2410506008_Tugas_Strukdat_Tree.ipynb at main ·… Contribute to Rahma-dwi-kartika-sari/praktikumsemester2_strukturdata development by creating an account on GitHub.github.com

REFERENSI:

Wardhani, O., & Alfath, I. (2024/2025). Modul Praktikum Struktur Data: Tree. Universitas Tidar.