Suffix Trie & Suffix Tree

Interactive visualizations for Chapter 1 of the Advanced Algorithms notes

Suffix Trie & Suffix Tree

Build and visualize the suffix trie and its compacted suffix tree for any input string.

viewof T_tree = Inputs.text({label: "T:", value: "cacao$", width: 300})
viewof tree_view = Inputs.radio(["Suffix Trie", "Suffix Tree"], {value: "Suffix Trie", label: "View:"})

Online Construction — Phase by Phase

Watch how the suffix trie grows character by character (Ukkonen’s online approach on the trie). At each phase, the algorithm appends a character and walks the boundary path, adding new transitions until it reaches a state that already has the corresponding edge.

Green nodes = new states created in this phase
Yellow nodes = boundary path states visited (but not new)
Blue nodes = existing states (unchanged)

viewof T_phase = Inputs.text({label: "T:", value: "cacao$", width: 300})

viewof step_phase = Inputs.range([0, phase_max_step], {step: 1, value: 0, label: "Phase:"})