Tree

Kegiatan Belajar 1: Pengantar Tree

A. Definisi Tree

1. Konsep Tree

• Tree: struktur data yang terdiri atas node dan edge, menyerupai pohon di kehidupan nyata.
• Node: elemen data yang direpresentasikan sebagai lingkaran (analogi daun pada pohon nyata).
• Edge: garis penghubung antar node (analogi ranting pada pohon nyata).
• Jumlah node dan edge bersifat dinamis, tetapi root hanya satu.

2. Contoh Representasi Tree

• Tree perusahaan Electronics R'Us: root = Electronics R'Us, child = R&D, Sales, Purchasing, Manufacturing.
• Sales memiliki child Domestic dan International; Manufacturing memiliki child TV, CD, Tuner.
• International memiliki child Canada, S. America, Overseas; Overseas memiliki child Africa, Europe, Asia, Australia.

B. Terminologi Tree

1. Sepuluh Terminologi Utama

• Path: urutan node dari satu node ke node lain dalam tree (garis putus-putus).
• Root: node pada level 0, jumlahnya hanya satu. Koleksi node dan edge disebut tree jika hanya ada satu path dari root ke sembarang node.
• Parent: node di atas suatu node yang terhubung melalui satu edge. Contoh: A adalah parent dari C.
• Child: node di bawah suatu node yang terhubung melalui edge. Contoh: B dan C adalah child dari A.
• Leaf: node yang tidak memiliki child. Contoh: E, G, H, I, J.
• Subtree: setiap node yang memiliki child dapat disebut root dari subtree. Contoh: subtree {F, I, J}.
• Visiting: node telah dikunjungi jika kontrol program sampai pada node tersebut (untuk pengecekan/proses data).
• Traversing: mengunjungi seluruh node dengan urutan tertentu.
• Level: banyaknya generasi dari root. Root = level 0, child = level 1, grandchild = level 2, dst.
• Key: nilai kunci pada suatu node, digunakan untuk pencarian atau proses lainnya.

C. Representasi Terminologi Tree

1. Level pada Contoh Perusahaan

• Level 0: Electronics R'Us (root)
• Level 1: R&D, Sales, Purchasing, Manufacturing
• Level 2: Domestic, International, TV, CD, Tuner
• Level 3: Canada, S. America, Overseas
• Level 4: Africa, Europe, Asia, Australia

2. Parent, Child, dan Leaf

• Sales → parent {Domestic, International}; Manufacturing → parent {TV, CD, Tuner}.
• International → parent {Canada, S. America, Overseas}; Overseas → parent {Africa, Europe, Asia, Australia}.
• Leaf level 1: R&D, Purchasing. Level 2: Domestic, TV, CD, Tuner.
• Leaf level 3: Canada, S. America. Level 4: Africa, Europe, Asia, Australia.
• Sales = grandparent dari child International; Sales = great grandparent dari child Overseas.

3. Traversing untuk Pencarian

• Cari node Canada dengan key "Canada": visiting root Electronics R'Us → level 1 (R&D, Sales, Purchasing, Manufacturing) → level 2 (Domestic, International, TV, CD, Tuner) → level 3 (Canada — ditemukan).

D. Tipe Data Abstrak pada Tree

1. Posisi Objek

• getElement(): mengembalikan elemen yang disimpan pada posisi saat ini.

2. Accessor Method (Navigasi)

• root(): mengembalikan posisi root; null jika tree kosong.
• parent(p): mengembalikan posisi parent dari p; null jika p adalah root.
• children(p): mengembalikan rangkaian children pada posisi p.
• numChildren(p): mengembalikan jumlah children dari posisi p.

3. Query Method

• isInternal(p): true jika posisi p memiliki minimal satu child.
• isExternal(p): true jika posisi p tidak memiliki child.
• isRoot(p): true jika posisi p adalah root.

4. Method Umum Tree

• size(): jumlah elemen/node pada tree.
• isEmpty(): true jika tree kosong.
• iterator(): iterator dari seluruh elemen.
• positions(): koleksi iterator seluruh posisi node.

---

Kegiatan Belajar 2: Binary Tree

A. Definisi Binary Tree

1. Syarat Binary Tree

• Setiap node hanya boleh memiliki maksimal 2 child (child kiri dan child kanan).
• Node boleh memiliki hanya satu child (kiri saja atau kanan saja) — tetap disebut binary tree.
• Menurut Goodrich et al. (2014): binary tree adalah ordered tree dengan child kiri selalu dikunjungi/dimiliki terlebih dahulu.

2. Contoh Binary Tree

• Tree dengan root 53, child kiri 30 dan kanan 72.
• Node 30 → child kiri 14, kanan 39. Node 72 → child kiri 61, kanan 84.
• Node 14 → child 9 dan 23. Node 39 → child 34 dan 47. Node 84 → child 79.
• Semua node memiliki maksimal 2 child → memenuhi syarat binary tree.

B. Representasi Binary Tree dalam Decision Tree

1. Konsep Decision Tree

• Setiap node berisi pertanyaan dengan 2 jawaban: Yes dan No.
• Contoh: rekomendasi investasi.
  • Root: "Are you nervous?" → Yes: Saving Account; No: lanjut.
  • "Need money within 5 years?" → Yes: Money Market Fund; No: lanjut.
  • "Accept risks?" → Yes: Stock Portfolio; No: Diversified Portfolio.
• Decision tree cocok untuk menentukan kelayakan investor, kenaikan pangkat, penerima beasiswa, dll.

C. Representasi Binary Tree dalam Aritmatika

1. Langkah Membuat Binary Tree dari Ekspresi

• Ekspresi: ((((3+1)*3)/((9-5)+2))-((3*(7-4))+6))
• Langkah 1: Cari simbol penengah dari keseluruhan ekspresi → root = simbol -.
• Langkah 2: Bagi dua ruas, cari simbol penengah masing-masing → child kiri /, child kanan +.
• Langkah 3: Lanjutkan pembagian hingga level terdalam, setiap leaf berupa variabel/konstanta.
• Node internal berupa operator (+, -, *, /); leaf berupa angka/konstanta.

D. Representasi Binary Tree dengan Array

1. Aturan Penomoran Indeks Array

• Jika p adalah root → f(p) = 0.
• Jika p adalah child kiri dari q → f(p) = 2f(q) + 1.
• Jika p adalah child kanan dari q → f(p) = 2f(q) + 2.

2. Contoh Representasi Array

• Root (/) → 0; child kiri (*) → 1; child kanan (+) → 2.
• Level 2: (+) → 3, (4) → 4, (-) → 5, (2) → 6.
• Leaf tanpa child tetap diberi ruang null. Total: 15 indeks, 11 node aktif.

E. Tipe Data Abstrak Binary Tree

1. Accessor Method Binary Tree

• left(p): mengembalikan posisi child kiri dari p; null jika tidak ada.
• right(p): mengembalikan posisi child kanan dari p; null jika tidak ada.
• sibling(p): mengembalikan posisi node satu level dengan p; null jika tidak ada.

---

Kegiatan Belajar 3: Binary Search Tree

A. Definisi Binary Search Tree

1. Konsep Binary Search Tree (BST)

• Pencarian diawali dari key (kata kunci), dilakukan secara bertahap huruf per huruf.
• Karakteristik BST (Lafore, 2003):
  • Node child kiri memiliki key lebih kecil dari parent.
  • Node child kanan memiliki key sama atau lebih tinggi dari parent.

2. Aturan BST (Goodrich et al., 2014)

• Setiap posisi internal p menyimpan elemen e dari set S.
• Elemen pada subtree kiri dari p memiliki nilai < e(p).
• Elemen pada subtree kanan dari p memiliki nilai ≥ e(p).

B. Operasi pada Binary Search Tree

1. Insert (Penyisipan)

• Bandingkan data baru dengan root. Jika lebih kecil → subtree kiri; jika lebih besar/sama → subtree kanan.
• Ulangi hingga menemukan posisi kosong (leaf), lalu sisipkan node baru.

2. Delete (Penghapusan)

• Leaf: hapus langsung, parent tidak memiliki child lagi.
• Satu child: hubungkan parent langsung ke child dari node yang dihapus.
• Dua child: cari pengganti (successor) dari subtree kanan — node terkecil di subtree kanan.

3. Search (Pencarian)

• Bandingkan key dengan node saat ini.
• Jika key = node → ditemukan.
• Jika key < node → cari di subtree kiri.
• Jika key > node → cari di subtree kanan.
• Jika sampai leaf tidak ditemukan → key tidak ada dalam tree.

C. Tipe Data Abstrak Binary Search Tree

1. Method ADT BST

• find(k): mengembalikan posisi elemen dengan key k; null jika tidak ditemukan.
• insert(k, v): menyisipkan entri dengan key k dan value v.
• remove(k): menghapus entri dengan key k.
• size(): mengembalikan jumlah entri.
• isEmpty(): true jika BST kosong.
• iterator(): iterator atas seluruh entri.
• positions(): koleksi posisi seluruh entri.