Belajar Math - Trees, DAG & Recursive Structures
Tree (parent/child), binary tree, Binary Search Tree, DAG, dan topological sort adalah struktur data fundamental yang muncul dalam file system, DOM, AST parser, task scheduler, dan Huffman coding — dari konsep hingga traversal di Python.
#Pendahuluan
Setelah di episode 14 kita mempelajari graph theory — terminologi, representasi, dan traversals — pada episode ini kita mempelajari trees dan DAG: graf khusus yang sangat penting dalam computer science. Tree adalah graf yang tidak memiliki cycle; DAG (Directed Acyclic Graph) adalah graf directed tanpa cycle. Keduanya muncul di mana-mana: file system, DOM, AST, dependency resolution, dan scheduling.
Mengapa trees dan DAG penting? Karena tree adalah model hierarchical yang paling alami — file system, organisasi perusahaan, dan DOM semuanya tree. DAG memperluas ini ke dependency graphs dengan parallelism. Memahami trees dan DAG memberikan kemampuan untuk menyelesaikan masalah traversal, sorting, dan optimasi yang sangat umum dalam programming.
#Tree
#Definisi
Tree adalah graf yang:
- Connected: semua node bisa diakses dari node lain
- Acyclic: tidak ada cycle
- Ada root (opsional tapi umum): node khusus sebagai titik awal
#Terminologi
tree = {
"A": ["B", "C"],
"B": ["D", "E"],
"C": ["F", "G"],
"D": [], "E": [], "F": [], "G": [],
}
print("Tree structure:")
print(" A ← root (level 0)")
print(" / \\")
print(" B C ← children of A (level 1)")
print(" / \\ / \\")
print(" D E F G ← leaves (level 2)")
print()
print("Parent(A) = None, Parent(B) = A")
print("Children(A) = [B, C]")
print("Siblings(B) = [C]")
print("Leaf nodes: D, E, F, G (no children)")
print("Height: 2 (max depth)")#Binary Tree
Tree di mana setiap node punya maksimal 2 children (left dan right):
class TreeNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
# Bangun binary tree
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)
# Traversal
def inorder(node):
"""Left → Root → Right."""
if node is None:
return []
return inorder(node.left) + [node.value] + inorder(node.right)
def preorder(node):
"""Root → Left → Right."""
if node is None:
return []
return [node.value] + preorder(node.left) + preorder(node.right)
def postorder(node):
"""Left → Right → Root."""
if node is None:
return []
return postorder(node.left) + postorder(node.right) + [node.value]
print(f"Inorder: {inorder(root)}") # [4, 2, 5, 1, 6, 3, 7]
print(f"Preorder: {preorder(root)}") # [1, 2, 4, 5, 3, 6, 7]
print(f"Postorder: {postorder(root)}") # [4, 5, 2, 6, 7, 3, 1]#Binary Search Tree (BST)
Binary tree di mana:
- Left child ≤ parent ≤ right child
- Memungkinkan search O(log n) average
class BSTNode:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
def bst_insert(root, value):
if root is None:
return BSTNode(value)
if value < root.value:
root.left = bst_insert(root.left, value)
else:
root.right = bst_insert(root.right, value)
return root
def bst_search(root, value):
if root is None or root.value == value:
return root
if value < root.value:
return bst_search(root.left, value)
return bst_search(root.right, value)
# Bangun BST
values = [8, 3, 10, 1, 6, 14, 4, 7, 13]
bst_root = None
for v in values:
bst_root = bst_insert(bst_root, v)
# Inorder traversal = sorted order
print(f"Inorder (sorted): {inorder(bst_root)}")
# Search
found = bst_search(bst_root, 6)
print(f"Search 6: {'Found' if found else 'Not found'}")
found = bst_search(bst_root, 99)
print(f"Search 99: {'Found' if found else 'Not found'}")#DAG (Directed Acyclic Graph)
#Definisi
DAG adalah graf directed yang tidak memiliki cycle. Tree adalah spesialisasi DAG (dengan root dan parent-child yang strict).
#Topological Sort
Topological sort menghasilkan urutan linear di mana setiap node muncul sebelum semua nodes yang bergantung padanya:
from collections import defaultdict, deque
def topological_sort_kahn(graph):
"""Kahn's algorithm — topological sort."""
in_degree = defaultdict(int)
all_nodes = set()
for node, neighbors in graph.items():
all_nodes.add(node)
for neighbor in neighbors:
all_nodes.add(neighbor)
in_degree[neighbor] += 1
queue = deque([n for n in all_nodes if in_degree[n] == 0])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
if len(order) != len(all_nodes):
return None # Cycle detected
return order
# Build system dependencies
build_deps = {
"app": {"tests", "lint"},
"tests": {"compile"},
"lint": {"compile"},
"compile": {"install_deps"},
"install_deps": set(),
}
order = topological_sort_kahn(build_deps)
print(f"Build order: {' → '.join(order)}")#Task Scheduling dengan Parallelism
from collections import defaultdict, deque
def parallel_schedule(graph):
"""Schedule tasks level by level — tasks in same level can run parallel."""
in_degree = defaultdict(int)
all_nodes = set()
for node, neighbors in graph.items():
all_nodes.add(node)
for neighbor in neighbors:
all_nodes.add(neighbor)
in_degree[neighbor] += 1
levels = []
queue = deque([n for n in all_nodes if in_degree[n] == 0])
while queue:
level = list(queue)
levels.append(level)
next_queue = deque()
for node in level:
for neighbor in graph[node]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
next_queue.append(neighbor)
queue = next_queue
return levels
levels = parallel_schedule(build_deps)
for i, level in enumerate(levels):
print(f"Level {i} (parallel): {level}")#Huffman Coding Tree
Huffman tree adalah binary tree yang digunakan untuk lossless compression — karakter频繁 muncul lebih dekat ke root (bit lebih pendek):
import heapq
from collections import Counter
def huffman_codes(text):
"""Bangun Huffman codes dari text."""
freq = Counter(text)
# Buat leaf nodes
heap = [[count, [char, ""]] for char, count in freq.items()]
heapq.heapify(heap)
while len(heap) > 1:
lo = heapq.heappop(heap)
hi = heapq.heappop(heap)
for pair in lo[1:]:
pair[1] = '0' + pair[1]
for pair in hi[1:]:
pair[1] = '1' + pair[1]
merged = [lo[0] + hi[0]] + lo[1:] + hi[1:]
heapq.heappush(heap, merged)
return dict(heap[0][1:])
text = "belajar matematika untuk pemrograman"
codes = huffman_codes(text)
print("Huffman codes:")
for char, code in sorted(codes.items(), key=lambda x: len(x[1])):
freq = text.count(char)
print(f" '{char}' (freq={freq}): {code}")
# Hitung kompresi
original_bits = len(text) * 8 # ASCII
compressed_bits = sum(len(codes[c]) * text.count(c) for c in set(text))
print(f"\nOriginal: {original_bits} bits")
print(f"Compressed: {compressed_bits} bits")
print(f"Ratio: {compressed_bits/original_bits:.1%}")#Aplikasi: File System sebagai Tree
import os
def list_files(path, prefix="", max_depth=3, current_depth=0):
"""List files sebagai tree — DFS recursive."""
if current_depth >= max_depth:
return
entries = sorted(os.listdir(path))
dirs = [e for e in entries if os.path.isdir(os.path.join(path, e))]
files = [e for e in entries if os.path.isfile(os.path.join(path, e))]
for f in files[:5]: # Limit output
print(f"{prefix}├── {f}")
if len(files) > 5:
print(f"{prefix}└── ... ({len(files)-5} more)")
for i, d in enumerate(dirs[:3]):
is_last = i == len(dirs[:3]) - 1 and len(dirs) <= 3
connector = "└── " if is_last else "├── "
print(f"{prefix}{connector}{d}/")
extension = " " if is_last else "│ "
list_files(
os.path.join(path, d),
prefix + extension,
max_depth,
current_depth + 1
)
# list_files("/home/devnull/Documents")Note
BST memberikan O(log n) average untuk search, insert, dan delete — tetapi worst case O(n) jika tree tidak balanced. Untuk guaranteed O(log n), gunakan self-balancing tree seperti AVL atau Red-Black tree. Dalam praktik, library standard Python menggunakan sorted containers yang memanfaatkan balanced trees.
#Penutup
Inti yang harus dibawa pulang:
- Tree adalah graf connected dan acyclic; binary tree membatasi max 2 children.
- BST memungkinkan search O(log n) average — inorder traversal = sorted order.
- DAG adalah graf directed tanpa cycle — memungkinkan topological sort untuk scheduling.
- Topological sort (Kahn's algorithm) menghasilkan urutan linear di mana dependency selalu lebih dulu.
- Huffman tree menggunakan frequency untuk encoding — karakter频繁 dapat code lebih pendek.
- Tree muncul di file system, DOM, AST, dan dependency resolution.
Di episode 16 selanjutnya kita akan mempelajari vectors (vektor) — vektor 2D/3D, operasi penjumlahan, skalar, magnitude, normalisasi, dan bagaimana ini muncul dalam game physics, pathfinding, dan ML features. Kita keluar dari discrete math dan masuk ke linear algebra!