GitLocker: The Coding Marketplace

Description:

radix tree 0.0.3

radix-tree

Table of Contents

Installation
What is radix tree ?
Getting started
License

Installation
pip install radix-tree

What_is_radix_tree
A radix tree is a specialized data structure used to store a
set of data indexed by strings. These can be strings of
characters, bits or any lexicographically ordered objects.
Radix tree are useful for building associative arrays with
string keys. In particular, they are very efficient to store
sets with hierarchical organization (such as IP addresses).
Insertion, deletion and searching have worst-case O(k)
(where k is the size of the key) and are therefore extremely
fast.
A set of strings of bits can be easily represented with a tree.
For instance, a 3-bits string:

The string ABB is fully represented by a unique path in the
tree. As a consequence, to associate some data to the string
ABB, we just need to store this data (say a pointer to this
data) in the last leaf of the path ABB.
Finding back the data associated to the string ABB is
straightforward (and very fast) because we just need to follow
the path (The algorithm to do this have O(3)).
This structure is then very efficient to build associative
arrays. Unfortunately it is largely memory-in(radix-tree.png)efficient as the
tree grows exponentially with the size of the key.
Here comes the radix tree. In a radix tree, we don’t branch for
every bit, but only when the radixes of strings are different.
In a way, when a node has only one child, we merge it with
its root.
For instance, a 8-bits radix tree which stores the values
AAAABABA, AAABBBAA and AAABBBBA:

Every intermediary node represents a radix of the string.
The final leaf represents the complete strings and stores the
associated data.
On this figure, you can see why the radix tree is useful to store
hierarchical organization of data. Imagine that AAAABABA is
an IP address. AAA/3 would be the network address. AAAA/4
would be the subnetwork address, and AAAABABA/8 the final
address. This is why radix trees are commonly used for IP routing.
You can also see, that insertion, deletion and search in a radix
tree have worst-case O(k) where k is the size of the key
(we branch on every bit). But it only happens when the tree is
full (very unlikely for long strings and, for short strings,
good-ol’ arrays are always your best shot).

Note that the current implementation of radix tree allows :

keys of differents lengths,
data may be associated to every node (not only leaf of the
tree)

Getting_started
from radix_tree import RadixTree

# Creation of empty radix tree
my_tree = RadixTree()

# Creation of first node
my_key = 'AAAABABA'
my_data = 'AAAABABA'
my_tree.insert_node(my_key , my_data )

# Creation of second node
my_key = 'AAABABAA'
my_data = 'AAABABAA'
my_tree.insert_node(my_key , my_data )

# Creation of third node
my_key = 'AAABBBBA'
my_data = 'AAABBBBA'
my_tree.insert_node(my_key , my_data )

# Display radix tree
my_tree.dump()

Result:
□ key: AAA key_len: 3 next: 2
│└■ key: AAAABABA key_len: 8 next: 0 data: Container -> data: AAAABABA tag: 0
└□ key: AAAB key_len: 4 next: 2
│└■ key: AAABABAA key_len: 8 next: 0 data: Container -> data: AAABABAA tag: 0
└■ key: AAABBBBA key_len: 8 next: 0 data: Container -> data: AAABBBBA tag: 0

You can also delete or get node :
# Get node
my_key = 'AAABBBBA'
print("Get node '%s'" % my_key)
print("Data associated to the node : %s" % my_tree.get_node(my_key))

# Deletion of second node
my_key = 'AAABABAA'
my_tree.delete_node(my_key)

# Deletion of third node
my_key = 'AAABBBBA'
my_tree.delete_node(my_key)

# Display radix tree
my_tree.dump()

Result:
Get node 'AAABBBBA'
Data associated to the node : Container -> data: AAABBBBA tag: 0
■ key: AAAABABA key_len: 8 next: 0 data: Container -> data: AAAABABA tag: 0

Debug
If you want to debug you can activate log in adding
argument level=debug when you launch your script :
$ python3 my_script.py level=debug

Log will be display on console and in file /tmp/radixTree.out.
License
radix-tree is distributed under the terms of the MIT license.