| Name | radix_tree JSON |
| Version |
0.0.3
JSON |
| download |
| home_page | None |
| Summary | Generic pure python radix tree implementation |
| upload_time | 2024-04-08 10:39:27 |
| maintainer | None |
| docs_url | None |
| author | None |
| requires_python | >=3.5 |
| license | None |
| keywords |
radix
tree
|
| VCS |
 |
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
|
# radix-tree
[](https://pypi.org/project/radix-tree)
[](https://pypi.org/project/radix-tree)
-----
**Table of Contents**
- [Installation](#installation)
- [What is radix tree ?](#what_is_radix_tree)
- [Getting started](#Getting_started)
- [License](#license)
## Installation
```console
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
```python
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:
```console
□ 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 :
```python
# 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:
```console
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 :
```console
$ 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](https://spdx.org/licenses/MIT.html) license.
Raw data
{
"_id": null,
"home_page": null,
"name": "radix_tree",
"maintainer": null,
"docs_url": null,
"requires_python": ">=3.5",
"maintainer_email": null,
"keywords": "radix, tree",
"author": null,
"author_email": "Nicolas Jeudy <nicola.jeudy@gmail.com>",
"download_url": "https://files.pythonhosted.org/packages/3c/ac/480af1233f33ec0f0165634946b203e0cd70a6fe0ad143558ae389a0875c/radix_tree-0.0.3.tar.gz",
"platform": null,
"description": "# radix-tree\n\n[](https://pypi.org/project/radix-tree)\n[](https://pypi.org/project/radix-tree)\n\n-----\n\n**Table of Contents**\n\n- [Installation](#installation)\n- [What is radix tree ?](#what_is_radix_tree)\n- [Getting started](#Getting_started)\n- [License](#license)\n\n## Installation\n\n```console\npip install radix-tree\n```\n## What_is_radix_tree\nA radix tree is a specialized data structure used to store a \nset of data indexed by strings. These can be strings of \ncharacters, bits or any lexicographically ordered objects.\n\nRadix tree are useful for building associative arrays with \nstring keys. In particular, they are very efficient to store \nsets with hierarchical organization (such as IP addresses).\n\nInsertion, deletion and searching have worst-case O(k) \n(where k is the size of the key) and are therefore extremely \nfast.\n\nA set of strings of bits can be easily represented with a tree. \nFor instance, a 3-bits string:\n\n\n\nThe string **ABB** is fully represented by a unique path in the \ntree. As a consequence, to associate some data to the string \n**ABB**, we just need to store this data (say a pointer to this \ndata) in the last leaf of the path **ABB**.\n\nFinding back the data associated to the string **ABB** is \nstraightforward (and very fast) because we just need to follow \nthe path (The algorithm to do this have O(3)).\n\nThis structure is then very efficient to build associative \narrays. Unfortunately it is largely memory-in(radix-tree.png)efficient as the \ntree grows exponentially with the size of the key.\n\nHere comes the radix tree. In a radix tree, we don\u2019t branch for \nevery bit, but only when the radixes of strings are different. \nIn a way, when a node has only one child, we merge it with \nits root.\n\nFor instance, a 8-bits radix tree which stores the values \n**AAAABABA**, **AAABBBAA** and **AAABBBBA**:\n\n\n\nEvery intermediary node represents a radix of the string. \nThe final leaf represents the complete strings and stores the \nassociated data.\n\nOn this figure, you can see why the radix tree is useful to store\nhierarchical organization of data. Imagine that **AAAABABA** is \nan IP address. **AAA/3** would be the network address. **AAAA/4** \nwould be the subnetwork address, and **AAAABABA/8** the final \naddress. This is why radix trees are commonly used for IP routing.\n\nYou can also see, that insertion, deletion and search in a radix\ntree have worst-case O(k) where k is the size of the key \n(we branch on every bit). But it only happens when the tree is \nfull (very unlikely for long strings and, for short strings, \ngood-ol\u2019 arrays are always your best shot).\n\n>**Note that the current implementation of radix tree allows :**\n>* keys of differents lengths,\n>* data may be associated to every node (not only leaf of the \ntree)\n\n## Getting_started\n```python\nfrom radix_tree import RadixTree\n\n# Creation of empty radix tree\nmy_tree = RadixTree()\n\n# Creation of first node\nmy_key = 'AAAABABA'\nmy_data = 'AAAABABA'\nmy_tree.insert_node(my_key , my_data )\n\n# Creation of second node\nmy_key = 'AAABABAA'\nmy_data = 'AAABABAA'\nmy_tree.insert_node(my_key , my_data )\n\n# Creation of third node\nmy_key = 'AAABBBBA'\nmy_data = 'AAABBBBA'\nmy_tree.insert_node(my_key , my_data )\n\n# Display radix tree\nmy_tree.dump()\n\n```\n\nResult:\n\n```console\n\u25a1 key: AAA key_len: 3 next: 2\n\u2502\u2514\u25a0 key: AAAABABA key_len: 8 next: 0 data: Container -> data: AAAABABA tag: 0\n\u2514\u25a1 key: AAAB key_len: 4 next: 2\n \u2502\u2514\u25a0 key: AAABABAA key_len: 8 next: 0 data: Container -> data: AAABABAA tag: 0\n \u2514\u25a0 key: AAABBBBA key_len: 8 next: 0 data: Container -> data: AAABBBBA tag: 0\n```\n\nYou can also delete or get node :\n\n```python\n\n# Get node\nmy_key = 'AAABBBBA'\nprint(\"Get node '%s'\" % my_key)\nprint(\"Data associated to the node : %s\" % my_tree.get_node(my_key))\n\n# Deletion of second node\nmy_key = 'AAABABAA'\nmy_tree.delete_node(my_key)\n\n# Deletion of third node\nmy_key = 'AAABBBBA'\nmy_tree.delete_node(my_key)\n\n# Display radix tree\nmy_tree.dump()\n```\n\nResult:\n\n```console\nGet node 'AAABBBBA'\nData associated to the node : Container -> data: AAABBBBA tag: 0\n\u25a0 key: AAAABABA key_len: 8 next: 0 data: Container -> data: AAAABABA tag: 0\n```\n## Debug\nIf you want to debug you can activate log in adding \nargument **level=debug** when you launch your script :\n```console\n$ python3 my_script.py level=debug\n```\nLog will be display on console and in file /tmp/radixTree.out.\n\n## License\n\n`radix-tree` is distributed under the terms of the [MIT](https://spdx.org/licenses/MIT.html) license.\n",
"bugtrack_url": null,
"license": null,
"summary": "Generic pure python radix tree implementation",
"version": "0.0.3",
"project_urls": {
"Documentation": "https://github.com/Nicola-31/radix-tree#readme",
"Issues": "https://github.com/Nicola-31/radix-tree/issues",
"Source": "https://github.com/Nicola-31/radix-tree"
},
"split_keywords": [
"radix",
" tree"
],
"urls": [
{
"comment_text": null,
"digests": {
"blake2b_256": "05c70d62d00e6c70136a83fe06e5a420f743550e84ce60c795a829a5930e1d4d",
"md5": "8f69c4d285b5ac347c1eaca1346e7f8e",
"sha256": "8a9ef311e04340928d87a0e51ef1a3563b0641bfe4b7b2427bdfc5bb5d388e43"
},
"downloads": -1,
"filename": "radix_tree-0.0.3-py3-none-any.whl",
"has_sig": false,
"md5_digest": "8f69c4d285b5ac347c1eaca1346e7f8e",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.5",
"size": 12975,
"upload_time": "2024-04-08T10:39:29",
"upload_time_iso_8601": "2024-04-08T10:39:29.534182Z",
"url": "https://files.pythonhosted.org/packages/05/c7/0d62d00e6c70136a83fe06e5a420f743550e84ce60c795a829a5930e1d4d/radix_tree-0.0.3-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": null,
"digests": {
"blake2b_256": "3cac480af1233f33ec0f0165634946b203e0cd70a6fe0ad143558ae389a0875c",
"md5": "a6e3d8affdcced32604c7cfb75cb4bf7",
"sha256": "c959692fad240cde172beaef3e7f2abaea6c0e96a7fbc187f213c045dd13333d"
},
"downloads": -1,
"filename": "radix_tree-0.0.3.tar.gz",
"has_sig": false,
"md5_digest": "a6e3d8affdcced32604c7cfb75cb4bf7",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.5",
"size": 104999,
"upload_time": "2024-04-08T10:39:27",
"upload_time_iso_8601": "2024-04-08T10:39:27.028128Z",
"url": "https://files.pythonhosted.org/packages/3c/ac/480af1233f33ec0f0165634946b203e0cd70a6fe0ad143558ae389a0875c/radix_tree-0.0.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-04-08 10:39:27",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "Nicola-31",
"github_project": "radix-tree#readme",
"travis_ci": false,
"coveralls": true,
"github_actions": false,
"lcname": "radix_tree"
}
