Videos / DSA
Episode 18 of 22 · DSA, end to end
Tries: the tree where the path is the key Included with a plan
This video is included with a plan. The first three lessons of every track are free, with their boards and videos. A plan unlocks every lesson, board, video, lab and paper for one price.
View plans → Already a member? Sign in
Chapters
Words that share a beginning 0:00 One letter per edge 0:15 A word ends here 0:30 The node, in c plus plus 0:46 Where the name comes from 1:03 What a hash set cannot do 1:18 Insert walks and builds 1:35 Search is the same walk 1:50 Starts with, minus one line 2:06 Order length, not order n 2:22 Collecting everything below 2:36 Deleting, and pruning back 2:53 Twenty six mostly empty slots 3:08 How many nodes there are 3:25 Three ways to hold children 3:43 Chains that branch nowhere 4:00 Collapse the chain, radix tree 4:16 Splitting an edge on insert 4:34 Four letters into a search box 4:50 The top ten, not all of them 5:07 Or precompute and cache it 5:23 Spell check asks a harder thing 5:41 One edit distance row per node 5:58 Shared prefixes, shared work 6:14 An alphabet of two 6:31 Every path is thirty two deep 6:48 The greedy walk for maximum xor 7:04 Why greedy is provably right 7:20 Five billion pairs, or six million steps 7:36 A key is a sequence of symbols 7:55 Proofreading against a list 8:10 One trie for every pattern 8:25 The failure link 8:41 Building the links breadth first 8:57 The matches you would miss 9:13 Linear, whatever the pattern count 9:28 The path is the key 9:43 Tries: the tree where the path is the key. Down the edge of a paper dictionary there are thumb tabs, and every word behind a tab starts with the same letter. Now cut that idea finer. One tab per letter, then a tab inside th
Mark as watched Saved in this browser only.