This chapter provides knowledge of tries. Data structures and algorithms in java provides an introduction to data structures and algorithms, including their design, analysis, and implementation. | Tries 3/25/14 16:11 Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014 Tries e mize i nimize © 2014 Goodrich, Tamassia, Goldwasser mi ze nimize nimize ze ze Tries 1 Preprocessing Strings ! Preprocessing the pattern speeds up pattern matching queries n After preprocessing the pattern, KMP’s algorithm performs pattern matching in time proportional to the text size ! If the text is large, immutable and searched for often (., works by Shakespeare), we may want to preprocess the text instead of the pattern ! A trie is a compact data structure for representing a set of strings, such as all the words in a text n A tries supports pattern matching queries in time proportional to the pattern size © 2014 Goodrich, Tamassia, Goldwasser Tries 2 1 Tries 3/25/14 16:11 Standard Tries ! The standard trie for a set of strings S is an ordered tree such that: n n n Each node but the root is labeled with a character The children of a node are alphabetically ordered The paths from the external nodes to the root yield the strings of S ! Example: standard trie for the set of strings S = { bear, bell, bid, bull, buy, sell, stock, stop } b e s i a l r d l u l e y l © 2014 Goodrich, Tamassia, Goldwasser t l o l c p k Tries 3 Analysis of Standard Tries ! A standard trie uses O(n) space and supports searches, insertions and deletions in time O(dm), where: n total size of the strings in S m size of the string parameter of the operation d size of the alphabet b e s i a l r d l © 2014 Goodrich, Tamassia, Goldwasser u l e y l t l o l Tries c k p 4 2 Tries 3/25/14 16:11 Word Matching with a Trie ! ! ! insert the words of s the text into trie 0 Each leaf is s associated w/ one 24 particular word leaf stores indices b where associated 47 word begins h (“see” starts at index 0 & 24, leaf 69 for “see” stores those
