Drzewa trie

https://en.wikipedia.org/wiki/Trie

WPROWADZENIE

Drzewo trie (ang. prefix tree) jest to drzewo poszukiwań przechowujące w węzłach fragmenty kluczy (drzewa BST przechowją w węzłach całe klucze). Węzeł przechowujący ostatni fragment klucza przechowuje również wartość związaną z danym kluczem lub tylko znacznik końca klucza.

Modyfikacją drzew trie są drzewa Patricia (ang. compact prefix tree), w których węzły mające tylko jednego syna są usuwane, a drzewo odpowiednio modyfikowane.

| Wstawione pary (key, value) do drzewa trie:
| ("kot",1),("koc",2),("los",3),("loty",4)
|           *
|        /    \
|       k      l
|      /        \
|     o          o
|    / \        / \
| t(1) c(2)  s(3)  t
|                 /
|               y(4)

| Wstawione pary (key, value) do drzewa Patricia:
| ("kot",1),("koc",2),("los",3),("loty",4),("dach",5)
|           *
|       /      \    \
|     ko        lo   dach(5)
|    / \        / \
| t(1) c(2)  s(3)  ty(4)