Chapter 15: Advanced Data Structures

Vol 2: Algorithm Forest Adventure · Station 15

---

Metadata Card

Attribute	Value
Difficulty	(Advanced)
Prerequisites	Linked Lists, BST, Hash Tables
Keywords	Skip List Union-Find Trie Fibonacci Heap AC Automaton

---

Your Progress

You stand at the edge of the Algorithm Forest. Before you lies an entrance leading underground — the Computer Core. Master Chen's map is complete. The road ahead is yours to walk alone.

---

Breakthrough · Origins

Skip List: Linked List with Express Lanes

import random

class SkipNode:
    def __init__(self, val, level):
        self.val = val
        self.forward = [None] * (level + 1)

class SkipList:
    def __init__(self, max_level=16, p=0.5):
        self.MAX_LV = max_level
        self.p = p
        self.head = SkipNode(float('-inf'), max_level)
        self._level = 0

    def _random_level(self):
        lv = 0
        while random.random() < self.p and lv < self.MAX_LV:
            lv += 1
        return lv

    def search(self, target):
        cur = self.head
        for i in range(self._level, -1, -1):
            while cur.forward[i] and cur.forward[i].val < target:
                cur = cur.forward[i]
        cur = cur.forward[0]
        return cur is not None and cur.val == target

    def insert(self, val):
        update = [None] * (self.MAX_LV + 1)
        cur = self.head
        for i in range(self._level, -1, -1):
            while cur.forward[i] and cur.forward[i].val < val:
                cur = cur.forward[i]
            update[i] = cur
        lv = self._random_level()
        if lv > self._level:
            for i in range(self._level + 1, lv + 1):
                update[i] = self.head
            self._level = lv
        node = SkipNode(val, lv)
        for i in range(lv + 1):
            node.forward[i] = update[i].forward[i]
            update[i].forward[i] = node

Union-Find (Disjoint Set Union)

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True

    def connected(self, a, b):
        return self.find(a) == self.find(b)

Trie (Prefix Tree)

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

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

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

    def search(self, word):
        node = self._find(word)
        return node is not None and node.is_end

    def starts_with(self, prefix):
        return self._find(prefix) is not None

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

    def autocomplete(self, prefix):
        node = self._find(prefix)
        if node is None: return []
        result = []
        self._dfs(node, list(prefix), result)
        return result

    def _dfs(self, node, path, result):
        if node.is_end:
            result.append(''.join(path))
        for ch in sorted(node.children.keys()):
            path.append(ch)
            self._dfs(node.children[ch], path, result)
            path.pop()

---

Verification Checklist

• [ ] Can explain skip list's multi-level express lane concept
• [ ] Can hand-write Union-Find (both optimizations)
• [ ] Can implement Trie (insert, search, prefix match, autocomplete)
• [ ] Understands why Fibonacci heap is theoretically elegant but rarely used

---

Traveler's Notes

Structure	One-Line Spirit	Proudest Application
Skip List	Build express lanes for linked lists	Redis zset
Union-Find	I only care which set you belong to	Kruskal, Social Networks
Fibonacci Heap	All work deferred to "later"	Theoretical extreme
Trie	Shared prefixes don't need duplication	Search engines, routers

---

→ Next Stop Preview

Vol 3: Computer Systems — A Deep Dive

From data structures in memory to the electronics that make them run. CPU, caches, virtual memory, assembly — the real "inside" of the computer.

"You stand at the edge of the Algorithm Forest. Before you is an entrance to the underground — the Computer Core. Master Chen's maps are used up. The road ahead is yours to walk alone."