Tree (Pohon)

---

🧭 1. Pengertian Tree

6

📖 Definisi

Tree adalah struktur data non-linear yang berbentuk hierarki (bertingkat), terdiri dari node-node yang saling terhubung melalui hubungan parent–child.

---

🧠 Narasi Konseptual

Bayangkan struktur organisasi perusahaan:

• Direktur → paling atas (root)
• Manajer → cabang di bawahnya
• Karyawan → berada di level terbawah

➡️ Tree merepresentasikan hubungan hierarkis seperti pohon keluarga atau organisasi.

---

🌳 2. Terminologi Dasar Tree

📊 Tabel Terminologi

Istilah	Penjelasan
Root	Node paling atas
Node	Elemen dalam tree
Parent	Node induk
Child	Node turunan
Leaf	Node tanpa anak
Edge	Penghubung antar node
Subtree	Bagian tree dari suatu node

---

🧠 Narasi

Setiap node dalam tree bisa menjadi “root kecil” untuk subtree-nya sendiri.

---

🧩 3. Struktur Tree

7

📖 Konsep

Tree terdiri dari:

• Root (akar utama)
• Cabang (node turunannya)
• Daun (leaf node)

---

🌲 4. Jenis-Jenis Tree

---

🔹 A. General Tree

8

📖 Konsep

Setiap node bisa memiliki lebih dari dua child.

---

🧠 Narasi

Seperti folder komputer:

• Satu folder bisa berisi banyak folder lain

---

🔹 B. Binary Tree

7

📖 Konsep

Setiap node maksimal memiliki dua anak (left & right).

---

🔹 C. Binary Search Tree (BST)

8

📖 Konsep

BST adalah binary tree dengan aturan:

• Kiri < root
• Kanan > root

---

🧠 Narasi

BST seperti rak buku:

• Kiri → buku lebih kecil
• Kanan → buku lebih besar

---

🔹 D. Balanced Tree

8

📖 Konsep

Tree dengan tinggi seimbang agar operasi lebih efisien.

---

🔁 5. Operasi pada Tree

📊 Tabel Operasi

Operasi	Deskripsi
Insertion	Menambah node
Deletion	Menghapus node
Searching	Mencari node
Traversal	Mengunjungi node

---

🔍 6. Tree Traversal (Penelusuran Tree)

---

🔹 A. Preorder (Root → Left → Right)

6

🧠 Narasi

Root dikunjungi terlebih dahulu.

---

🔹 B. Inorder (Left → Root → Right)

7

🧠 Narasi

Hasil BST dengan inorder akan terurut.

---

🔹 C. Postorder (Left → Right → Root)

5

🧠 Narasi

Root dikunjungi terakhir.

---

⚙️ 7. Kompleksitas Operasi Tree

📊 Tabel Kompleksitas

Operasi	BST Seimbang	BST Tidak Seimbang
Search	O(log n)	O(n)
Insert	O(log n)	O(n)
Delete	O(log n)	O(n)

---

🧠 8. Kelebihan Tree

📌 Narasi

Tree sangat penting karena:

• Menyimpan data secara hierarki
• Efisien untuk pencarian (BST)
• Digunakan dalam database dan indexing

---

⚠️ 9. Kekurangan Tree

📊 Tabel

Kekurangan	Penjelasan
Kompleks	Sulit diimplementasikan
Tidak linear	Lebih sulit dipahami
Tidak selalu seimbang	Bisa menurunkan performa

---

🧪 10. Studi Kasus Nyata

📌 File System

• Folder → parent node
• File → leaf node

---

📌 Database Indexing

• MySQL & PostgreSQL menggunakan B-Tree untuk mempercepat query

---

💻 11. Implementasi Sederhana BST (C++)

struct Node {
    int data;
    Node* left;
    Node* right;
};Node* createNode(int value){
    Node* newNode = new Node();
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

---

📚 12. Ringkasan Materi

• Tree adalah struktur data hierarki
• Memiliki root, parent, child, leaf
• Jenis utama: binary tree, BST, balanced tree
• Traversal: preorder, inorder, postorder
• Digunakan dalam sistem nyata seperti database dan file system

---

📝 13. Latihan / Diskusi

✏️ Soal Teori

1. Jelaskan pengertian tree
2. Apa itu BST?
3. Bedakan preorder, inorder, postorder

💻 Soal Praktikum

1. Buat struktur node tree
2. Implementasikan traversal inorder
3. Tambahkan node ke BST

---

🎯 Penutup

Tree adalah struktur data penting untuk representasi data hierarki dan pencarian efisien, serta menjadi dasar:

• Database indexing
• Artificial intelligence
• File system