TeachingAlgorithm Design and AnalysisSesi 5 — Data Structures: Stack, Queue, Tree & Binary Tree (incl. Space Complexity)
Week 3Lecture

Sesi 5 — Data Structures: Stack, Queue, Tree & Binary Tree (incl. Space Complexity)

Sesi 5 — Data Structures: Stack, Queue, Tree & Binary Tree (incl. Space Complexity)

COMP6049001 — Algorithm Design and Analysis

Daftar Isi

  1. Stack and Queue
  2. Space Complexity
  3. Tree Terminology and Traversals
  4. Binary Tree Properties and Operations
  5. Time vs. Space Trade-off

Kaitan dengan Sesi Sebelumnya

Sesi ini adalah penerapan dari alat analisis yang sudah dibangun di Sesi 1–4:

Konsep dari sesi sebelumnya Diterapkan di Sesi 5 sebagai
Notasi O, Ω, Θ (Sesi 4) Menyatakan kompleksitas operasi stack/queue/BST
Worst vs. average case (Sesi 3) BST height: O(log n) rata-rata vs. O(n) worst-case
Space complexity, in-place (Sesi 3 & 4) Dibahas jauh lebih detail: auxiliary vs. total space
Time-space tradeoff (Sesi 4, slide 22) Diperluas dengan tabel pemilihan struktur data

1. Stack and Queue

1.1 Stack — LIFO (Last In, First Out)

Stack adalah dynamic set dengan disiplin LIFO: elemen yang terakhir masuk adalah yang pertama keluar. Hanya ada satu titik akses, yaitu TOP.

Analogi: tumpukan piring — piring terakhir yang ditaruh di atas adalah yang pertama diambil.

Operasi Dasar

Operasi Arti
PUSH(S, x) Masukkan elemen x ke atas tumpukan
POP(S) Keluarkan dan kembalikan elemen paling atas
STACK-EMPTY(S) Kembalikan TRUE jika stack kosong
PEEK(S) Lihat elemen teratas tanpa mengeluarkannya

Implementasi Array (CLRS)

S.top = 0          // kondisi awal: stack kosong

PUSH(S, x)
1   S.top = S.top + 1
2   S[S.top] = x

POP(S)
1   if STACK-EMPTY(S)
2       error "underflow"
3   S.top = S.top - 1
4   return S[S.top + 1]

Kenapa semua operasi O(1)? Karena tidak ada loop sama sekali — setiap operasi cuma melakukan sejumlah tetap instruksi (increment/decrement counter, satu akses array). Tidak peduli stack berisi 10 atau 10 juta elemen, jumlah langkahnya sama.

Kompleksitas Stack

Operasi Time (worst-case) Auxiliary Space
PUSH O(1) —
POP O(1) —
PEEK O(1) —
STACK-EMPTY O(1) —
SEARCH (cari elemen tertentu) O(n) —
Total space — O(n)

Implementasi Linked-List

Setiap node menyimpan data + pointer ke node berikutnya. PUSH dan POP dilakukan di head.

Perbandingan dengan array:

Aspek Array Linked List
Time per operasi O(1) O(1)
Total space O(n) — n = kapasitas array O(k) — k = jumlah elemen saat ini
Kelemahan Kapasitas tetap; ruang terbuang jika tidak penuh Overhead pointer per node

Linked list tidak membuang ruang untuk slot kosong, tapi setiap node butuh memori ekstra untuk pointer.

Aplikasi Stack

  • Function call stack — bagaimana bahasa pemrograman melacak pemanggilan fungsi bersarang
  • Expression evaluation — konversi infix ke postfix, evaluasi ekspresi aritmatika
  • DFS (Depth-First Search) — traversal graph/tree secara mendalam
  • Undo operations — di text editor, Photoshop, dll
  • Balanced parentheses checking — validasi pasangan kurung dalam kode

1.2 Queue — FIFO (First In, First Out)

Queue adalah dynamic set dengan disiplin FIFO: elemen yang pertama masuk adalah yang pertama keluar. Ada dua titik akses: REAR (untuk memasukkan) dan FRONT (untuk mengeluarkan).

Analogi: antrean di kasir — yang datang duluan dilayani duluan.

Operasi Dasar

Operasi Arti
ENQUEUE(Q, x) / PUSH(x) Masukkan elemen x di REAR
DEQUEUE(Q) / POP() Keluarkan elemen di FRONT
QUEUE-EMPTY(Q) / EMPTY() Cek apakah queue kosong

Kompleksitas Queue

Operasi Time (worst-case) Catatan
ENQUEUE O(1) Tinggal tambah di REAR
DEQUEUE O(1) dengan circular array atau linked list
DEQUEUE O(n) dengan array biasa (non-circular) Karena semua elemen harus digeser satu posisi ke kiri
EMPTY O(1) Cukup bandingkan pointer FRONT dan REAR
Total space — O(n)

Poin penting untuk latihan: DEQUEUE adalah satu-satunya operasi yang kompleksitasnya bergantung pada implementasi. Dengan array biasa, setelah mengambil elemen depan, semua elemen sisanya harus digeser → O(n). Dengan circular array (indeks FRONT bergerak maju dan "membungkus" ke awal array saat mencapai ujung) atau linked list, tidak ada penggeseran → O(1).

Aplikasi Queue

  • BFS (Breadth-First Search) — traversal graph/tree per level
  • Job scheduling / print queue — antrean tugas yang dilayani sesuai urutan datang
  • Buffering — streaming data, keyboard buffer

1.3 Perbandingan Stack vs. Queue

Stack Queue
Disiplin LIFO FIFO
Titik akses 1 (TOP) 2 (FRONT & REAR)
Traversal yang memakainya DFS BFS
Operasi inti O(1) O(1)

2. Space Complexity

2.1 Auxiliary vs. Total Space

Ini pembedaan yang krusial dan sering tertukar:

Istilah Definisi
Auxiliary space Memori tambahan yang dipakai algoritma, di luar input itu sendiri
Total space Auxiliary space + ruang untuk menyimpan input

Dalam analisis algoritma, yang biasanya dilaporkan adalah auxiliary space — karena itulah "biaya memori" yang benar-benar ditimbulkan oleh algoritma. Ruang untuk input dianggap sudah ada sebelum algoritma dijalankan, jadi bukan "tanggung jawab" algoritma.

Contoh: Insertion Sort mengurutkan array berukuran n.

  • Total space = O(n) — karena arraynya sendiri butuh n slot
  • Auxiliary space = O(1) — karena Insertion Sort hanya butuh beberapa variabel sementara (key, i, j), berapapun besar n

Inilah yang dimaksud in-place di Sesi 3: algoritma yang auxiliary space-nya O(1).

2.2 Tabel Auxiliary Space Algoritma Umum

Algoritma Time Auxiliary Space Alasan
Insertion Sort O(n²) O(1) In-place — hanya geser elemen di array yang sama
Merge Sort O(n log n) O(n) Proses merge butuh array sementara
Binary Search (rekursif) O(log n) O(log n) Call stack sedalam log n
Binary Search (iteratif) O(log n) O(1) Tidak ada rekursi
Quick Sort O(n log n) avg O(log n) rekursif Call stack sedalam kedalaman rekursi
BFS pada graph O(V + E) O(V) Queue + array visited
DFS pada graph O(V + E) O(V) Stack (atau call stack) + array visited

Catatan: tabel di slide kuliah memuat beberapa angka yang tampaknya keliru ketik (Binary Search tertulis "O(n log n) avg" dan Quick Sort tertulis "O(log n)" di kolom Time). Angka yang benar sesuai CLRS adalah: Binary Search = O(log n) time, Quick Sort = O(n log n) expected / O(n²) worst-case time.

2.3 Stack Space untuk Rekursi

Ini konsep yang sering terlewat: setiap pemanggilan rekursif memakan ruang di call stack, karena komputer harus mengingat "di mana harus kembali" setelah fungsi selesai.

Aturan umum:

$$\text{Auxiliary space rekursi} = O(\text{kedalaman rekursi})$$

Jenis rekursi Kedalaman Auxiliary space Contoh
Balanced (membelah dua) log n O(log n) Merge Sort, Binary Search
Linear (mengurangi satu) n O(n) Fibonacci naif, DFS pada path graph

Implikasi praktis: rekursi linear pada input besar bisa menyebabkan stack overflow — program crash karena call stack penuh. Inilah alasan mengapa untuk input sangat besar, versi iteratif sering lebih aman daripada versi rekursif.

3. Tree Terminology and Traversals

3.1 Definisi Formal Rooted Tree

Rooted tree T adalah graph tak berarah yang connected, acyclic, dengan satu node ditetapkan sebagai root r.

Tiga syarat ini harus dipenuhi sekaligus:

  1. Connected — semua node terhubung, tidak ada yang terisolasi
  2. Acyclic — tidak ada siklus (tidak bisa berputar kembali ke node yang sama)
  3. Designated root — satu node dipilih sebagai "atas", ini yang menciptakan hierarki

Kalau salah satu syarat tidak terpenuhi:

  • Acyclic tapi tidak connected → forest (kumpulan beberapa tree terpisah)
  • Connected tapi ada cycle → graph biasa, bukan tree

Sifat yang mengikuti: tree dengan n node selalu punya tepat n − 1 edge.

3.2 Istilah Kunci

Gunakan tree contoh berikut untuk semua definisi:

          A          <- depth 0
        / | \
       B  C  D       <- depth 1
      / \      \
     E   F      G    <- depth 2
Istilah Definisi Contoh
Node (vertex) Setiap elemen tree A, B, C, D, E, F, G
Root Node paling atas, tanpa parent A
Parent / Child x parent dari y jika x satu level di atas y pada path y ke root A parent dari B, C, D
Leaf Node tanpa anak C, E, F, G
Internal node Node dengan minimal satu anak A, B, D
Depth of node x Panjang path dari root ke x depth(A)=0, depth(B)=1, depth(E)=2
Height of tree Depth maksimum di seluruh tree 2
Subtree rooted at x x beserta semua keturunannya Subtree di B = {B, E, F}

Depth vs. Height: Depth dihitung dari root ke bawah (setiap node punya depth sendiri). Height of tree adalah depth terbesar di seluruh tree (satu angka untuk seluruh tree).

3.3 Tree Traversals

Untuk binary tree (setiap node punya left dan right child), ada tiga cara standar menjelajah. Ketiganya adalah varian DFS — bedanya hanya pada kapan node induk dicetak relatif terhadap anak-anaknya.

Preorder (Root → Left → Right)

PREORDER(x)
1   if x ≠ NIL
2       print x.key
3       PREORDER(x.left)
4       PREORDER(x.right)

Kegunaan: menyalin/menduplikasi struktur tree, serialisasi tree.

Inorder (Left → Root → Right)

INORDER(x)
1   if x ≠ NIL
2       INORDER(x.left)
3       print x.key
4       INORDER(x.right)

Kegunaan: menghasilkan output terurut jika dijalankan pada Binary Search Tree. Ini sifat yang sangat penting dan akan sering dipakai.

Postorder (Left → Right → Root)

POSTORDER(x)
1   if x ≠ NIL
2       POSTORDER(x.left)
3       POSTORDER(x.right)
4       print x.key

Kegunaan: menghapus tree (anak dihapus sebelum induk), mengevaluasi expression tree.

Contoh Konkret

Untuk binary tree berikut:

        5
       / \
      3   7
     / \  / \
    1  4 6   8
Traversal Hasil
Preorder 5, 3, 1, 4, 7, 6, 8
Inorder 1, 3, 4, 5, 6, 7, 8 ← terurut!
Postorder 1, 4, 3, 6, 8, 7, 5

Kompleksitas Traversal

$$\text{Time} = O(n), \quad \text{Auxiliary Space} = O(h)$$

  • O(n) time — setiap node dikunjungi tepat sekali
  • O(h) space — h = height tree, karena call stack rekursi sedalam h. Untuk tree seimbang h = O(log n); untuk tree degenerate (menyerupai linked list) h = O(n)

4. Binary Tree Properties and Operations

4.1 Definisi dan Sifat Binary Tree

Binary tree adalah rooted tree di mana setiap node punya maksimal dua anak: left child dan right child.

Sifat-sifat penting:

Sifat Penjelasan
n node → n − 1 edge Berlaku untuk semua tree, termasuk binary tree
Full binary tree Setiap node punya 0 atau 2 anak (tidak ada yang punya 1 anak)
Complete binary tree Semua level terisi penuh kecuali level terakhir, yang terisi dari kiri ke kanan
Perfect binary tree Semua leaf berada di depth yang sama; punya tepat 2^(h+1) − 1 node
Height complete binary tree h = ⌊log₂ n⌋

Verifikasi rumus perfect binary tree: untuk h=2, rumus memberi 2³ − 1 = 7 node. Cocok dengan contoh tree 5-3-7-1-4-6-8 di atas (7 node, semua leaf di depth 2). ✓

Mengapa height complete binary tree = ⌊log₂ n⌋? Karena setiap level menampung dua kali lipat node level sebelumnya (1, 2, 4, 8, ...). Untuk menampung n node butuh sekitar log₂ n level. Inilah alasan struktur berbasis tree seimbang bisa mencapai O(log n).

4.2 Binary Search Tree (BST)

BST property: untuk setiap node x, semua key di subtree kiri x adalah ≤ x.key, dan semua key di subtree kanan x adalah ≥ x.key.

Sifat inilah yang memungkinkan pencarian efisien: pada setiap node, kita bisa membuang separuh kemungkinan hanya dengan satu perbandingan — mirip prinsip binary search pada array terurut.

Operasi BST

BST-SEARCH(x, k)
1   if x == NIL or k == x.key
2       return x
3   if k < x.key
4       return BST-SEARCH(x.left, k)
5   else
6       return BST-SEARCH(x.right, k)

Semua operasi utama BST berjalan dalam O(h), dengan h = height tree:

Operasi Time
SEARCH O(h)
INSERT O(h)
DELETE O(h)
MIN / MAX O(h)
SUCCESSOR O(h)

Mengapa O(h), bukan O(n)? Karena setiap langkah turun satu level dan membuang seluruh subtree di sisi lain. Jumlah langkah maksimum = tinggi tree.

Masalah Utama BST: Height Tidak Dijamin

Inilah poin paling penting tentang BST:

Kondisi Height Kompleksitas operasi
Input acak (random BST) O(log n) expected O(log n)
Input sudah terurut O(n) O(n) — degenerate!

Contoh degenerate: masukkan 1, 2, 3, 4, 5 ke BST kosong secara berurutan:

1
 \
  2
   \
    3
     \
      4
       \
        5

Hasilnya menyerupai linked list — setiap node cuma punya anak kanan. Height = n − 1, sehingga SEARCH jadi O(n), sama buruknya dengan linear search pada array biasa.

Ini contoh nyata dari prinsip worst-case analysis Sesi 3: struktur data yang "biasanya cepat" bisa sangat lambat pada input tertentu.

Solusi: Balanced BST

Untuk menjamin O(log n) di worst-case (bukan cuma rata-rata), gunakan BST yang menjaga keseimbangan:

  • Red-Black Tree (CLRS Ch. 13)
  • AVL Tree

Keduanya menerapkan balance invariant yang diperiksa dan diperbaiki (lewat rotasi) setiap kali ada insert/delete, sehingga height selalu dijaga di O(log n).

Catatan terminologi kursus ini: ketika materi menyebut "Balanced BST", yang dimaksud spesifik adalah Red-Black Tree atau AVL Tree — bukan sekadar BST yang kebetulan seimbang.

5. Time vs. Space Trade-off

5.1 Prinsip Umum

Algoritma sering bisa menukar waktu dengan ruang, atau sebaliknya:

Arah trade-off Contoh Efek
Kurangi waktu, bayar dengan ruang Memoization pada Fibonacci Dari O(2ⁿ) → O(n) time, dengan biaya O(n) space
Kurangi waktu, bayar dengan ruang Hash table O(n) space untuk O(1) average lookup, dibanding O(log n) pada BST
Kurangi ruang, bayar dengan waktu In-place sorting O(1) auxiliary space, tapi konstanta waktu lebih besar / implementasi lebih rumit
Kurangi ruang, bayar dengan waktu Recompute daripada cache Hemat memori, tapi kerja berulang

Contoh Fibonacci (terhubung ke Sesi 1 dan 4): versi rekursif naif berjalan dalam Θ(φⁿ) ≈ eksponensial karena menghitung ulang subproblem yang sama berkali-kali. Dengan menyimpan hasil perhitungan (memoization) dalam array berukuran O(n), running time turun drastis menjadi Θ(n). Ini juga menjadi jembatan ke topik Dynamic Programming di sesi-sesi mendatang.

5.2 Panduan Pemilihan Struktur Data

Kebutuhan Struktur Pilihan Alasan
Akses LIFO Stack Operasi O(1) di satu ujung
Akses FIFO Queue Operasi O(1) di dua ujung
Akses prioritas (max/min dulu) Heap (Sesi 6) O(log n) insert/extract, O(1) peek
Ordered dynamic set Balanced BST (Red-Black / AVL) O(log n) worst-case, dan inorder traversal menghasilkan urutan terurut
Lookup cepat by key Hash table O(1) average lookup
Data hierarkis Tree Struktur alami untuk relasi parent-child

Catatan: tabel di slide kuliah memuat dua baris "LIFO access" berturut-turut; baris kedua seharusnya "FIFO access → Queue".

Kapan pilih Balanced BST, kapan Hash table?

Balanced BST Hash table
Lookup O(log n) worst-case O(1) average, O(n) worst-case
Data terurut? Ya — inorder traversal memberi urutan Tidak
Range query (cari semua key antara a dan b) Efisien Tidak bisa langsung
MIN / MAX / SUCCESSOR O(log n) Harus scan seluruh tabel

Jika hanya butuh lookup cepat → hash table. Jika butuh data tetap terurut atau operasi berbasis urutan → balanced BST.

Referensi

Cormen, T.H., Leiserson, C.E., Rivest, R.L., & Stein, C. (2022). Introduction to Algorithms, 4th Edition. MIT Press.

  • Ch. 10.1 — Simple Array-Based Data Structures: Arrays, Matrices, Stacks, Queues (p. 248)
  • Ch. 10.3 — Representing Rooted Trees (p. 265)
  • Ch. 13 — Red-Black Trees (p. 308)

Skiena, S.S. (2020). The Algorithm Design Manual, 3rd Edition. Springer.

  • Ch. 3.1 — Contiguous vs. Linked Data Structures (p. 69)
  • Ch. 3.2 — Containers: Stacks and Queues (p. 75)
  • Ch. 3.4 — Binary Search Trees (p. 81)