[Subject home], [FAQ], [progress],   Bib', Alg's,  C , Java - L.A., Sunday, 28-Nov-2021 05:27:13 AEDT
Instructions: Topics discussed in these lecture notes are examinable unless otherwise indicated. You need to follow instructions, take more notes & draw diagrams especially as [indicated] or as done in lectures, work through examples, and do extra reading. Hyper-links not in [square brackets] are mainly for revision, for further reading, and for lecturers of the subject.

Tables:   Tries & PATRICIA:   Introduction

Have seen height balanced trees

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

[lecturer: consider doing a different example; class: take notes]
Empty Trie,   insert "an" :
------->[a|,b , ...,z ,/]
          |
          |
          |
          v
         [a ,...,n|,...z ,/]
                  |
                  |
                  |
                  v
                 [a ,...,z ,*]
NB. [....,/] no ending,   [....,*] word ends.
Trie,   insert "ant"
---->[a|,b , ...,z ,/]
       |
       |
       v
      [a ,...,n|,...z ,/]
               |
               |
               v
              [a ,...,t|...,z ,*]
                       |
                       |
                       v
                      [a ,...z ,*]
eventually . . .

Trie properties

©
L
.
A
l
l
i
s
o
n
Trie by lists,   an, ant, all.  
--->[/,a|, ]
        |
        |
        v
       [/,l|,-]------>[n|, ]
           |            |
           |            |
           |            v
           v           [*,t|, ]
          [l|, ]           |
            |              |
            |              v
            v             [*, ]
           [*, ]
`/' no ending;   `*' word ends here.

PATRICIA cures the Trie's space problem:

[lecturer: consider doing a different example; class: take notes!]

Empty PATRICIA, insert ababb.


----->ababb
insert ababa; search, find ababb, differs at ababa, position #5
------->[5]
        . .
      .     .
   a.         .b
  .             .
.                 .
ababa             ababb
Note, must store strings in leaves.

what about short strings?

insert ba; no "real" position #5, but 1st difference at ba///, v. a..., is at a "real" char
------------------>[1]
                  .   .
                a.     .b
                .       .
              [5]       ba
             .   .
           .      .
          .        .
        ababa     ababb

another short string?

insert aab; 1st position 'a', no real 5th position, 1st difference aab// at position 2, v. ab....
------------------>[1]
                  .   .
                a.     .b
                .       .
              [2]        ba
             .   . 
           a.     .b
           .       .
         aab       [5]
                  .   .
                 .     .
                .       .
              ababa    ababb
yet another short string
insert aba, find ababa (or ababb), 1st difference at position 4 aba// v. abab...
------------------>[1]
                  .   .
                a.     .b
                .       .
              [2]        ba
             .   .
           a.     .b
           .       .
         aab       [4]--->aba
                     .
                      .b
                       .
                       [5]
                      .   .
                     .     .
                  ababa   ababb
note that aba was a prefix of ababa (and ababb).
insert abaaab; search, find ababa (or ababb), 1st difference abaaab v. abab....
------------------>[1]
                  .   .
                a.     .b
                .       .
              [2]        ba
             .   .
           a.     .b
           .       .
         aab       [4]-->aba
                  .   .
                a.     .b
                .       .
           abaaab       [5]
                       .   .
                      .     .
                  ababa   ababb

Tables:   Tries & PATRICIA:   Summary

Prepare:

© L.Allison, Sunday, 28-Nov-2021 05:27:13 AEDT users.monash.edu.au/~lloyd/tilde/CSC2/CSE2304/Notes/11trie.shtml
Computer Science, Software Engineering, Science (Computer Science).