KamusNgoding
Pemula Data-structures 5 menit baca

Tutorial Tree (Pohon) dalam Struktur Data untuk Pemula

#tree #binary tree #data structure #pemula #struktur data
📚

Baca dulu sebelum ini:

Tutorial Tree (Pohon) dalam Struktur Data untuk Pemula

Pendahuluan

Bayangkan kamu sedang membuka aplikasi file manager di laptopmu. Ada folder Documents, di dalamnya ada subfolder Kerja, dan di dalam Kerja ada file-file Word. Struktur bertingkat seperti ini bukan kebetulan — inilah Tree (Pohon), salah satu struktur data paling penting yang dipakai hampir di semua aplikasi modern.

Tree adalah struktur data hierarkis yang terdiri dari node-node yang saling terhubung. Berbeda dengan array atau linked list yang bersifat linear (satu baris), tree bercabang seperti pohon nyata — ada satu akar (root) di atas, dan cabang-cabang yang menjalar ke bawah.

Jika kamu sudah familiar dengan konsep dasar seperti yang dibahas di Mengenal Big O Notation: Cara Mengukur Efisiensi Algoritma, kamu akan lebih mudah memahami mengapa tree sangat efisien untuk operasi pencarian dan pengurutan data.

Konsep Dasar dan Terminologi Tree

Sebelum masuk ke kode, kita perlu memahami kosakata dasar tree:

IstilahPenjelasan
RootNode paling atas, titik awal tree
NodeSetiap elemen dalam tree
ParentNode yang memiliki cabang ke bawah
ChildNode yang terhubung ke parent-nya di atasnya
LeafNode yang tidak punya child (ujung cabang)
EdgeGaris penghubung antar node
HeightJarak terpanjang dari root ke leaf
DepthJarak dari root ke sebuah node tertentu
SubtreeBagian tree yang berdiri sendiri

Visualisasi sederhana:

        A          ← Root (depth 0)
       / \
      B   C        ← Child dari A (depth 1)
     / \   \
    D   E   F      ← Leaf (depth 2, height = 2)

Dalam contoh di atas:

  • A adalah root dan parent dari B dan C
  • B adalah child dari A, sekaligus parent dari D dan E
  • D, E, dan F adalah leaf karena tidak punya child

Mengenal Jenis-Jenis Tree

1. General Tree

Tree yang tidak punya batasan jumlah child per node. Contoh: struktur folder di komputer.

2. Binary Tree

Setiap node memiliki maksimal 2 child — biasa disebut child kiri (left) dan child kanan (right). Ini yang paling sering dipakai dan dipelajari.

3. Binary Search Tree (BST)

Versi khusus Binary Tree dengan aturan:

  • Semua nilai di kiri selalu lebih kecil dari parent
  • Semua nilai di kanan selalu lebih besar dari parent

Aturan ini membuat pencarian data sangat cepat — O(log n) dalam kondisi terbaik.

4. Balanced Tree (AVL Tree, Red-Black Tree)

Tree yang menjaga keseimbangan tinggi kiri dan kanan agar operasi tetap efisien meski datanya banyak.

Untuk artikel ini, kita akan fokus pada Binary Tree dan Binary Search Tree karena paling fundamental.

Operasi Dasar dan Implementasi Sederhana

Mari kita implementasikan Binary Search Tree dari nol menggunakan Python.

Mendefinisikan Node

class Node:
    def __init__(self, nilai):
        self.nilai = nilai      # menyimpan nilai/data pada node
        self.kiri = None        # anak kiri, awalnya belum ada
        self.kanan = None       # anak kanan, awalnya belum ada


# membuat beberapa node
akar = Node(10)
akar.kiri = Node(5)
akar.kanan = Node(15)

# menampilkan isi node
print("Nilai akar:", akar.nilai)
print("Anak kiri:", akar.kiri.nilai)
print("Anak kanan:", akar.kanan.nilai)

# Output yang diharapkan:
# > Nilai akar: 10
# > Anak kiri: 5
# > Anak kanan: 15

Mendefinisikan Binary Search Tree

class Node:
    def __init__(self, nilai):
        # Setiap node menyimpan satu nilai
        self.nilai = nilai
        # Anak kiri untuk nilai yang lebih kecil
        self.kiri = None
        # Anak kanan untuk nilai yang lebih besar atau sama
        self.kanan = None


class BinarySearchTree:
    def __init__(self):
        # Awalnya tree kosong
        self.root = None

    def sisipkan(self, nilai):
        # Jika root belum ada, buat node pertama
        if self.root is None:
            self.root = Node(nilai)
        else:
            self._sisipkan_rekursif(self.root, nilai)

    def _sisipkan_rekursif(self, node, nilai):
        # Jika nilai lebih kecil, masuk ke sisi kiri
        if nilai < node.nilai:
            if node.kiri is None:
                node.kiri = Node(nilai)
            else:
                self._sisipkan_rekursif(node.kiri, nilai)
        else:
            # Jika nilai lebih besar atau sama, masuk ke sisi kanan
            if node.kanan is None:
                node.kanan = Node(nilai)
            else:
                self._sisipkan_rekursif(node.kanan, nilai)

    def cari(self, nilai):
        # Mulai pencarian dari root
        return self._cari_rekursif(self.root, nilai)

    def _cari_rekursif(self, node, nilai):
        # Jika node kosong, berarti nilai tidak ditemukan
        if node is None:
            return False

        # Jika nilai cocok, berarti ditemukan
        if node.nilai == nilai:
            return True

        # Cari ke kiri jika nilai lebih kecil
        if nilai < node.nilai:
            return self._cari_rekursif(node.kiri, nilai)

        # Cari ke kanan jika nilai lebih besar
        return self._cari_rekursif(node.kanan, nilai)


# Contoh penggunaan
bst = BinarySearchTree()

# Menambahkan beberapa nilai ke tree
bst.sisipkan(10)
bst.sisipkan(5)
bst.sisipkan(15)
bst.sisipkan(3)
bst.sisipkan(7)

# Mencari nilai dalam tree
print("Cari 7:", bst.cari(7))
print("Cari 12:", bst.cari(12))

# Output yang diharapkan:
# > Cari 7: True
# > Cari 12: False

Tree Traversal — Cara Mengunjungi Semua Node

Ada tiga cara traversal utama:

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


class BinaryTree:
    # In-order: kiri -> root -> kanan
    def in_order(self, node, hasil=None):
        if hasil is None:
            hasil = []  # Membuat list baru agar tidak berbagi data antar pemanggilan

        if node:
            self.in_order(node.kiri, hasil)   # Kunjungi subtree kiri
            hasil.append(node.nilai)          # Simpan nilai node saat ini
            self.in_order(node.kanan, hasil)  # Kunjungi subtree kanan

        return hasil

    # Pre-order: root -> kiri -> kanan
    def pre_order(self, node, hasil=None):
        if hasil is None:
            hasil = []

        if node:
            hasil.append(node.nilai)          # Simpan root lebih dulu
            self.pre_order(node.kiri, hasil)  # Lalu subtree kiri
            self.pre_order(node.kanan, hasil) # Terakhir subtree kanan

        return hasil

    # Post-order: kiri -> kanan -> root
    def post_order(self, node, hasil=None):
        if hasil is None:
            hasil = []

        if node:
            self.post_order(node.kiri, hasil)   # Kunjungi subtree kiri
            self.post_order(node.kanan, hasil)  # Kunjungi subtree kanan
            hasil.append(node.nilai)            # Simpan root di akhir

        return hasil


# Membuat tree sederhana
#        2
#       / \
#      1   3
root = Node(2)
root.kiri = Node(1)
root.kanan = Node(3)

tree = BinaryTree()

# Menampilkan hasil traversal
print("In-order :", tree.in_order(root))
print("Pre-order:", tree.pre_order(root))
print("Post-order:", tree.post_order(root))

# Output yang diharapkan:
# > In-order : [1, 2, 3]
# > Pre-order: [2, 1, 3]
# > Post-order: [1, 3, 2]

Contoh Penggunaan Lengkap

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


class BinarySearchTree:
    def __init__(self):
        self.root = None

    def sisipkan(self, data):
        # Jika tree masih kosong, data pertama jadi root
        if self.root is None:
            self.root = Node(data)
        else:
            self._sisipkan_rekursif(self.root, data)

    def _sisipkan_rekursif(self, node, data):
        # Nilai lebih kecil masuk ke kiri
        if data < node.data:
            if node.kiri is None:
                node.kiri = Node(data)
            else:
                self._sisipkan_rekursif(node.kiri, data)
        # Nilai lebih besar atau sama masuk ke kanan
        else:
            if node.kanan is None:
                node.kanan = Node(data)
            else:
                self._sisipkan_rekursif(node.kanan, data)

    def in_order(self, node, hasil):
        # Kiri -> Root -> Kanan
        if node is not None:
            self.in_order(node.kiri, hasil)
            hasil.append(node.data)
            self.in_order(node.kanan, hasil)
        return hasil

    def pre_order(self, node, hasil):
        # Root -> Kiri -> Kanan
        if node is not None:
            hasil.append(node.data)
            self.pre_order(node.kiri, hasil)
            self.pre_order(node.kanan, hasil)
        return hasil

    def cari(self, data):
        # Mulai pencarian dari root
        return self._cari_rekursif(self.root, data)

    def _cari_rekursif(self, node, data):
        # Jika node tidak ada, data tidak ditemukan
        if node is None:
            return False

        # Jika data sama, berarti ditemukan
        if node.data == data:
            return True

        # Cari ke kiri jika data lebih kecil
        if data < node.data:
            return self._cari_rekursif(node.kiri, data)

        # Cari ke kanan jika data lebih besar
        return self._cari_rekursif(node.kanan, data)


# Buat tree dan isi data
bst = BinarySearchTree()
for angka in [50, 30, 70, 20, 40, 60, 80]:
    bst.sisipkan(angka)

# Struktur yang terbentuk:
#        50
#       /  \
#      30   70
#     / \  / \
#    20 40 60 80

# Traversal in-order menghasilkan data terurut
print("In-order:", bst.in_order(bst.root, []))

# Traversal pre-order membaca root lebih dulu
print("Pre-order:", bst.pre_order(bst.root, []))

# Pencarian data di dalam tree
print("Cari 40:", bst.cari(40))
print("Cari 99:", bst.cari(99))

# Output yang diharapkan:
# > In-order: [20, 30, 40, 50, 60, 70, 80]
# > Pre-order: [50, 30, 20, 40, 70, 60, 80]
# > Cari 40: True
# > Cari 99: False

Perhatikan hasil in-order traversal yang menghasilkan data terurut secara otomatis. Inilah kekuatan BST — data selalu dalam kondisi “siap sort” tanpa perlu algoritma sorting tambahan.

Contoh Kasus Nyata

1. Sistem Navigasi Kategori Produk

Bayangkan kamu ingin membangun e-commerce seperti Tokopedia atau Shopee. Kategori produk mereka berbentuk tree:

Elektronik
├── Smartphone
│   ├── Android
│   └── iOS
├── Laptop
│   ├── Gaming
│   └── Ultrabook
└── Aksesoris
    ├── Charger
    └── Headset
class KategoriProduk:
    def __init__(self, nama):
        # Menyimpan nama kategori
        self.nama = nama
        # Menyimpan daftar sub-kategori
        self.sub_kategoris = []

    def tambah_sub_kategori(self, sub_kategori):
        self.sub_kategoris.append(sub_kategori)

    def cetak_kategoris(self, level=0):
        print('  ' * level + self.nama)
        for sub_kategori in self.sub_kategoris:
            sub_kategori.cetak_kategoris(level + 1)


# Membuat struktur kategori
elektronik = KategoriProduk("Elektronik")
smartphone = KategoriProduk("Smartphone")
android = KategoriProduk("Android")
ios = KategoriProduk("iOS")
laptop = KategoriProduk("Laptop")
gaming = KategoriProduk("Gaming")
ultrabook = KategoriProduk("Ultrabook")
aksesoris = KategoriProduk("Aksesoris")
charger = KategoriProduk("Charger")
headset = KategoriProduk("Headset")

smartphone.tambah_sub_kategori(android)
smartphone.tambah_sub_kategori(ios)
laptop.tambah_sub_kategori(gaming)
laptop.tambah_sub_kategori(ultrabook)
aksesoris.tambah_sub_kategori(charger)
aksesoris.tambah_sub_kategori(headset)

elektronik.tambah_sub_kategori(smartphone)
elektronik.tambah_sub_kategori(laptop)
elektronik.tambah_sub_kategori(aksesoris)

elektronik.cetak_kategoris()

# Output yang diharapkan:
# > Elektronik
# >   Smartphone
# >     Android
# >     iOS
# >   Laptop
# >     Gaming
# >     Ultrabook
# >   Aksesoris
# >     Charger
# >     Headset

2. Autocomplete dengan Trie

Trie adalah bentuk pohon yang sering digunakan untuk implementasi autocomplete, seperti fitur search suggestion yang kamu temukan di mesin pencari atau aplikasi chat.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False


class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def search_prefix(self, prefix):
        node = self.root
        for char in prefix:
            if char not in node.children:
                return None
            node = node.children[char]
        return node

    def autocomplete(self, prefix):
        results = []
        prefix_node = self.search_prefix(prefix)
        if not prefix_node:
            return results
        self._find_words_from_node(prefix_node, prefix, results)
        return results

    def _find_words_from_node(self, node, prefix, results):
        if node.is_end_of_word:
            results.append(prefix)
        for char, child in node.children.items():
            self._find_words_from_node(child, prefix + char, results)


# Contoh penggunaan
trie = Trie()
words = ["apple", "app", "apricot", "banana", "bandana"]
for word in words:
    trie.insert(word)

print(trie.autocomplete("app"))   # Output: ['app', 'apple']
print(trie.autocomplete("ban"))   # Output: ['banana', 'bandana']
print(trie.autocomplete("xyz"))   # Output: []

Pertanyaan yang Sering Diajukan

Apa perbedaan Tree dan Graph dalam struktur data?

Tree adalah jenis khusus dari Graph dengan aturan ketat: tidak ada siklus (cycle), setiap node hanya punya satu parent (kecuali root), dan selalu ada tepat satu jalur antara dua node. Graph lebih bebas — bisa punya siklus dan satu node bisa terhubung ke banyak node lain tanpa hierarki yang jelas. Singkatnya, semua tree adalah graph, tapi tidak semua graph adalah tree.

Mengapa Binary Search Tree lebih efisien dari pencarian linear?

Pada pencarian linear (seperti di array), kita harus memeriksa setiap elemen satu per satu — kompleksitasnya O(n). Pada BST yang seimbang, setiap perbandingan memotong separuh dari kemungkinan — kompleksitasnya O(log n). Untuk 1 juta data, linear butuh hingga 1.000.000 langkah, sedangkan BST hanya butuh sekitar 20 langkah.

Bagaimana cara memilih jenis traversal yang tepat?

Pilih berdasarkan kebutuhanmu: gunakan in-order jika kamu ingin data terurut dari kecil ke besar (cocok untuk sorting). Gunakan pre-order jika kamu ingin menyalin atau menyerialkan tree (root diproses duluan). Gunakan post-order jika kamu ingin menghapus tree dari bawah ke atas, atau menghitung nilai ekspresi matematika bertingkat.

Apa itu Balanced Tree dan kenapa penting?

Balanced tree adalah tree yang menjaga agar tinggi kiri dan kanan tidak terlalu berbeda. Jika BST tidak seimbang — misalnya semua data dimasukkan secara urut (1, 2, 3, 4, 5) — maka tree akan menjadi seperti linked list dengan tinggi O(n), dan semua keuntungan BST hilang. Balanced tree seperti AVL Tree atau Red-Black Tree otomatis menyeimbangkan diri setelah setiap operasi.

Kapan sebaiknya saya menggunakan Tree dibanding Hash Table?

Gunakan Tree jika kamu perlu data yang terurut, pencarian range (misalnya: cari semua nilai antara 10 dan 50), atau operasi in-order traversal. Untuk perbandingan lengkap keduanya, baca Apa itu Hash Table: Penjelasan Lengkap untuk Pemula. Hash Table lebih cepat untuk pencarian tepat (exact lookup) dengan O(1) rata-rata, tapi tidak mendukung pengurutan. Keduanya punya keunggulan masing-masing tergantung kasusnya.

Kesimpulan

Tree adalah struktur data hierarkis yang sangat powerful untuk merepresentasikan data bertingkat. Poin penting yang perlu kamu ingat:

  • Root adalah satu-satunya node tanpa parent; leaf adalah node tanpa child
  • Binary Search Tree (BST) mengatur data agar kiri < parent < kanan, membuat pencarian efisien O(log n)
  • In-order traversal menghasilkan data terurut secara otomatis
  • Aplikasi nyata: sistem file, kategori produk, autocomplete, ekspresi matematika, dan masih banyak lagi

Tree mungkin terlihat kompleks di awal, tapi begitu kamu memahami prinsip rekursinya — setiap subtree adalah tree itu sendiri — semuanya akan terasa lebih natural. Mulailah dengan mengimplementasikan BST sederhana, lalu eksplorasi varian lainnya seperti AVL Tree atau Heap.

Selamat belajar, dan terus berlatih!

Artikel Terkait

data-structures Apa itu Hash Table? Penjelasan Lengkap untuk Pemula data-structures Binary Search Tree vs AVL Tree: Perbedaan dan Kapan Menggunakannya data-structures Memahami Graph (Graf) dalam Struktur Data