Editing Radix tree (section)

==Variants==

A common extension of radix trees uses two colors of nodes, 'black' and 'white'. To check if a given string is stored in the tree, the search starts from the top and follows the edges of the input string until no further progress can be made.  If the search string is consumed and the final node is a black node, the search has failed; if it is white, the search has succeeded. This enables us to add a large range of strings with a common prefix to the tree, using white nodes, then remove a small set of "exceptions" in a space-efficient manner by ''inserting'' them using black nodes.

The '''[[HAT-trie]]''' is a cache-conscious data structure based on radix trees that offers efficient string storage and retrieval, and ordered iterations.  Performance, with respect to both time and space, is
comparable to the cache-conscious [[hashtable]].<ref>{{Cite book | title=HAT-trie: A Cache-conscious Trie-based Data Structure for Strings | first1=Nikolas | last1=Askitis | first2=Ranjan | last2=Sinha | year=2007 | url=http://portal.acm.org/citation.cfm?id=1273749.1273761&coll=GUIDE&dl= | isbn=978-1-920682-43-9 | pages=97–105 | volume=62 | journal=Proceedings of the 30th Australasian Conference on Computer Science }}</ref><ref>
  {{Cite journal
  | title=Engineering scalable, cache and space efficient tries for strings
  | first1=Nikolas
  | last1=Askitis
  | first2=Ranjan
  | last2=Sinha
  | date=October 2010
  | doi=10.1007/s00778-010-0183-9
  | journal=The VLDB Journal
  | issue=5
  | volume=19
  | pages=633–660
  | s2cid=432572
 }}
</ref>

A '''PATRICIA''' trie is a special variant of the radix 2 (binary) trie, in which rather than explicitly store every bit of every key, the nodes store only the position of the first bit which differentiates two sub-trees. During traversal the algorithm examines the indexed bit of the search key and chooses the left or right sub-tree as appropriate. Notable features of the PATRICIA trie include that the trie only requires one node to be inserted for every unique key stored, making PATRICIA much more compact than a standard binary trie. Also, since the actual keys are no longer explicitly stored it is necessary to perform one full key comparison on the indexed record in order to confirm a match. In this respect PATRICIA bears a certain resemblance to indexing using a hash table.<ref name="patricia" />

The '''adaptive radix tree''' is a radix tree variant that integrates adaptive node sizes to the radix tree.  One major drawback of the usual radix trees is the use of space, because it uses a constant node size in every level. The major difference between the radix tree and the adaptive radix tree is its variable size for each node based on the number of child elements, which grows while adding new entries.  Hence, the adaptive radix tree leads to a better use of space without reducing its speed.<ref>
  {{Cite book
  | title=Datenbanksysteme, Eine Einführung
  | first1=Alfons
  | last1=Kemper
  | first2=André
  | last2=Eickler
  | date=2013
  | isbn=978-3-486-72139-3
  | volume=9
  | pages=604–605
  | publisher=Oldenbourg
 }}
</ref><ref>{{cite web|url=https://github.com/armon/libart|title=armon/libart: Adaptive Radix Trees implemented in C|work=GitHub|access-date=17 September 2014}}</ref><ref>{{cite book|author=Viktor Leis|title=2013 IEEE 29th International Conference on Data Engineering (ICDE) |chapter=The adaptive radix tree: ARTful indexing for main-memory databases |date=2013 |display-authors=et. al.|pages=38–49|doi=10.1109/ICDE.2013.6544812|isbn=978-1-4673-4910-9 |s2cid=14030601 }}</ref>

A common practice is to relax the criteria of disallowing parents with only one child in situations where the parent represents a valid key in the data set. This variant of radix tree achieves a higher space efficiency than the one which only allows internal nodes with at least two children.<ref>[https://cs.stackexchange.com/q/98459 Can a node of Radix tree which represents a valid key have one child?]</ref>