Science Fair Project Encyclopedia
Radix tree
A radix tree is a binary search tree that is used to store binary strings and to quickly check if a given bit-string is stored in the tree.
Radix tree consists of nodes which have two edges (one for 'true' and one for 'false') and a color 'black' or 'white'. To associate values with bit-strings, the node could also contain a value.
To check if a given string is stored in the tree, the search starts from the top and follows the 'true' or 'false' edges along the bits in the string. If the search encounters a black node, the search fails. If the search-string is consumed and the actual node is a white node, the search has succeeded.
Last updated: 06-03-2005 10:31:51
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details