Tries

Trie data structure in PHP

Tries are persistent and ordered tree structures with an empty root node capable of storing string-indexed sets, similar to hash tables and maps. They’re made up of nodes that store partial set keys, dispersed across the entire structure. Because tries can be used to store key-value pairs, they can be used in place of the standard PHP array. The trie pictured below has the i, so, sin, sit, sir, a, an, ant, and and nodes, whose corresponding values are 3, 10, 4, 6, 15, 9, 5, 13, and 7.