Tables:   Tries & PATRICIA:   Introduction

Have seen height balanced trees

• search, insert, delete O(log(n))-time

Now, there are special data structures for storing words where operations are O(|word|)-time,  not O( f( # of words)).

i.e. The search time depends on the length of the search-word not on the number of words in the structure.

• Trie (Fredkin 1960)

• PATRICIA (Morrison 1968) . . .

Trie

• an   | alphabet |-way   tree
  
  
• all "a....." words in same sub-tree . . .
  
  
  • all "aa...." words (e.g. aardvark) in same sub-sub-tree, etc. . . .
    
    
• all "z....." words in same sub-tree . . .

------->[a|,b , ...,z ,/]
          |
          |
          |
          v
         [a ,...,n|,...z ,/]
                  |
                  |
                  |
                  v
                 [a ,...,z ,*]

---->[a|,b , ...,z ,/]
       |
       |
       v
      [a ,...,n|,...z ,/]
               |
               |
               v
              [a ,...,t|...,z ,*]
                       |
                       |
                       v
                      [a ,...z ,*]

Trie properties

• max dept is length of longest word
  
  
• insertion, deletion, search O(|word|)-time
  
  
• but, much waste space with a simple implementation:
  
  
  • each node has   | alphabet |   pointers (+ end-of-word)
  • deep nodes typically have mostly null pointers.
    
    
• Can reduce space problem by turning each node into a linked list, at the price of some time . . .

--->[/,a|, ]
        |
        |
        v
       [/,l|,-]------>[n|, ]
           |            |
           |            |
           |            v
           v           [*,t|, ]
          [l|, ]           |
            |              |
            |              v
            v             [*, ]
           [*, ]

PATRICIA cures the Trie's space problem:

• No nodes have single children,
  
  
• only have nodes where letters differ,
  
  
• nodes are labelled by character position.
  
  
• Rule: higher splits must be on earlier character positions.
  
  
• Easiest if   |alphabet| = 2  
  
  
• and can always make |alphabet| = 2,   by [___________________?]

Empty PATRICIA, insert ababb.

----->ababb

------->[5]
        . .
      .     .
   a.         .b
  .             .
.                 .
ababa             ababb

what about short strings?

------------------>[1]
                  .   .
                a.     .b
                .       .
              [5]       ba
             .   .
           .      .
          .        .
        ababa     ababb

another short string?

------------------>[1]
                  .   .
                a.     .b
                .       .
              [2]        ba
             .   . 
           a.     .b
           .       .
         aab       [5]
                  .   .
                 .     .
                .       .
              ababa    ababb

------------------>[1]
                  .   .
                a.     .b
                .       .
              [2]        ba
             .   .
           a.     .b
           .       .
         aab       [4]--->aba
                     .
                      .b
                       .
                       [5]
                      .   .
                     .     .
                  ababa   ababb

------------------>[1]
                  .   .
                a.     .b
                .       .
              [2]        ba
             .   .
           a.     .b
           .       .
         aab       [4]-->aba
                  .   .
                a.     .b
                .       .
           abaaab       [5]
                       .   .
                      .     .
                  ababa   ababb

Tables:   Tries & PATRICIA:   Summary

• Trie and PATRICIA, O(|word|)-time operations
  
  
• PATRICIA, more efficient use of space for natural language
  
  
• Trie can still be useful, e.g. for DNA substrings in some applications

Prepare:

• 2-3-, 2-3-4-trees, B-trees, . . .