Prompt utilisé pour régénérer cette page :
Page: Patricia Trie - Interactive PATRICIA Algorithm Visualization
Title: "Patricia Trie"
Description: "Interactive demonstration of the PATRICIA algorithm (Practical Algorithm to Retrieve Information Coded in Alphanumeric)"
Icon: tree
Tags: algorithm, data-structure, trie, search
Category: computer-science
Front matter: js: default (no scss key — no custom SCSS file)
HTML structure in index.md:
<section class="patricia-container container visual">
<svg id="patricia-svg" width="100%" height="400"></svg>
</section>
<section class="patricia-stats section">
<div id="patricia-stats"></div>
</section>
Widget files:
_controls.right.md (weight: 100, title: "Controls", _build: render: never, list: never):
##### Input
- <input type="text" id="patricia-input" placeholder="Enter word..." class="input">
- Button group: {{< button id="btn-insert" color="green" label="Insert" >}}, {{< button id="btn-search" color="blue" label="Search" >}}, {{< button id="btn-prefix" color="aqua" label="Prefix" >}}, {{< button id="btn-delete" color="red" label="Delete" >}}
##### Words
- <div id="patricia-words"></div>
##### Suggestions
- <div id="patricia-suggestions"></div>
_options.right.md (weight: 200, title: "Options", _build: render: never, list: never):
##### Speed
- <input type="range" id="patricia-speed" min="1" max="10" value="5" class="slider">
##### Examples
- Button group vertical: btn-example-words (Common Words), btn-example-names (Names), btn-example-code (Code Methods) — all color="grey" size="small"
##### Actions
- {{< button id="btn-clear" color="orange" label="Clear All" >}}
default.js (IIFE, no external imports, ~953 lines):
CONFIG: nodeRadius=20, levelHeight=80, siblingSpacing=40, animationSpeed=500
CONFIG.colors: node=var(--color-blue), nodeEnd=var(--color-green), edge=var(--color-grey-500), edgeLabelBg=var(--background-color-surface), edgeLabel=var(--text-color-primary), nodeText=var(--text-color-inverted, #fff), highlight=var(--color-yellow), found=var(--color-green), notFound=var(--color-red)
PatriciaNode class:
- constructor(prefix=''): this.prefix, this.children (Map), this.isEnd=false, this.id (random 9-char string)
PatriciaTrie class:
- constructor(): root = new PatriciaNode(''), wordCount=0, nodeCount=1
- commonPrefixLength(a, b): Returns length of common prefix between two strings
- insert(word): Returns animation steps array. Traverses matching prefixes, creates new leaf for unmatched remainder, splits nodes on partial prefix match. Steps: start, highlight, compare, create, split, markEnd, descend, end
- search(word): Returns {found, steps}. Traverses matching prefixes, checks isEnd. Steps: start, highlight, descend, found/notFound/mismatch/notEnd
- startsWith(prefix): Navigate to prefix end, collect all words recursively via collectWords()
- collectWords(node, prefix, words): Recursive word collection from node
- getAllWords(): Returns sorted word list via collectWords from root
- clear(): Resets root, wordCount=0, nodeCount=1
- delete(word): Calls deleteHelper recursively. Removes word end, merges single-child non-end nodes, cleans empty branches. Returns boolean
- deleteHelper(node, word, depth): Returns {deleted, shouldRemove}. Handles node merging when single child + not end + not root
Layout functions:
calculateLayout(node, x, y, positions, level=0): Recursive tree layout. Children centered under parent. Returns {minX, maxX}
getSubtreeWidth(node): Returns pixel width of subtree. Leaf = nodeRadius*2, internal = sum of children widths + siblingSpacing gaps
render(highlightNodes=Map()): Calculates layout positions, computes SVG viewBox from bounds (padding 50px), builds SVG content string:
- Edges: <line> from parent to child, edge labels on midpoint with monospace <text> on background <rect>
- Nodes: <circle> with fill (blue for internal, green for word end), optional highlight stroke (4px, color from highlightNodes map)
- Root node labeled "ROOT" in white text
- Calls updateStats()
- escapeHtml(str): Replaces &, <, > for safe SVG text
updateStats(): Displays wordCount, nodeCount, compression ratio. Compression = (1 - patriciaNodes / (totalChars+1)) * 100
animate(steps): async function, isAnimating flag prevents concurrency. Iterates steps, applies highlights via render(highlights Map), sleeps(animationSpeed) between steps. Final render without highlights
Action handlers:
handleInsert(): Reads input, toLowerCase, calls trie.insert(), animate(steps), clears input, updates word list
handleSearch(): Reads input, trie.search(), animate(steps), logs result
handlePrefix(): Reads input, trie.startsWith(), displays matches as .tag spans in #patricia-suggestions
handleClear(): trie.clear(), render(), updateWordList()
handleDelete(): trie.delete(), render(), updateWordList()
updateWordList(): Gets sorted words, displays as .tag.color-blue spans in #patricia-words, or "<em>Empty</em>"
loadExample(type): Clears trie, inserts words array, render(), updateWordList()
- words: test, testing, tested, tester, team, tea, to, ten, tennis
- names: alice, alex, albert, bob, bobby, charlie, carol
- code: get, getUser, getUserById, getUsers, set, setUser, delete, deleteUser
handleSpeedChange(speed): animationSpeed = 1100 - speed*100 (higher slider = faster)
init(): Gets SVG and stats elements, creates PatriciaTrie, binds buttons (insert/search/prefix/delete/clear), Enter key on input triggers insert, speed slider, example buttons, loads 'words' example by default
Auto-init: readyState check
Page entièrement générée et maintenue par IA, sans intervention humaine.