# Augmented AVL Tree for Interval Search
## Overview
This project implements an augmented AVL tree (a self-balancing binary search tree) in Python, designed specifically for storing and querying intervals efficiently. The tree allows you to insert intervals (with associated keys) and quickly search for the smallest interval containing a given point. This implementation is particularly useful for tasks like BIN (Bank Identification Number) range searches, where each interval represents a range of possible values.
## Features
- **Self-Balancing Tree**: The tree remains balanced after each insertion, ensuring that operations like search, insert, and delete remain efficient.
- **Interval Queries**: Efficiently find the smallest interval that contains a given point.
- **Pure Python Implementation**: The core logic is implemented purely in Python, making it easy to understand and modify.
## Installation
### Using `pip`
1. Ensure you have Python 3.9 or higher installed.
2. Install the package using `pip`:
```sh
pip install avl_range_tree
```
### Building from Source
If you'd like to build the package from source:
1. Clone the repository:
```sh
git clone git@github.com:mcoira/python-range-tree.git
cd python-range-tree/
```
2. Install the package:
```sh
pip install .
```
## Usage
### Importing the Tree
```python
from avl_range_tree.avl_tree import RangeTree
```
### Inserting Intervals
Each interval is defined by a start value, an end value, and a key (a unique identifier for that interval).
```python
tree = RangeTree()
tree.insert(123456000000000000, 123456999999999999, "key1")
tree.insert(987654000000000000, 987654999999999999, "key2")
```
### Searching for Intervals
To search for the smallest interval containing a given point:
```python
search_value = int(str(12345678).ljust(16, '0')) # Convert 123456 to 1234567800000000
result = tree.search(search_value)
if result:
start, end, key = result
print(f"Found interval: [{start}, {end}] with key: {key}")
else:
print("No interval found containing the point.")
```
### Example Output
```shell
Found interval: [123456000000000000, 123456999999999999] with key: key1
```
## Use Cases
### 1. BIN Range Lookup for Financial Transactions
In financial systems, BIN ranges are used to identify the issuing bank for credit and debit cards and some of the card's features. This tree can efficiently store and query BIN ranges, ensuring quick lookups during transaction processing.
### 2. IP Address Range Search
This implementation can also be adapted to store and search IP address ranges, allowing for quick identification of network blocks.
### 3. Date Range Queries
You can store and search for date ranges, which can be useful in applications like booking systems, where you need to check if a date falls within a certain range.
## Performance
Thanks to the self-balancing nature of AVL trees, this implementation is highly efficient for both insertion and search operations. Unlike Red-Black trees, which are approximately balanced, AVL trees maintain strict balance, ensuring the tree's height is minimized. This strict balancing results in more rotations during insertion, making AVL trees slightly more expensive to build. However, this additional overhead pays off during queries, as the tree's height is kept to a minimum, improving search performance.
This characteristic is particularly beneficial in scenarios like BIN number management, where data is periodically updated but queried frequently. In such cases, the AVL tree offers a superior balance between build time and query performance, ensuring that the time complexity for operations remains O(log n + m), where n is the number of elements in the tree, and m is the number of overlapping intervals that contain the point.
## License
This project is licensed under the MIT License. See the LICENSE file for details.
Raw data
{
"_id": null,
"home_page": "https://github.com/mcoira/python-range-tree",
"name": "avl_range_tree",
"maintainer": null,
"docs_url": null,
"requires_python": "<4.0,>=3.9",
"maintainer_email": null,
"keywords": null,
"author": "Mikel",
"author_email": null,
"download_url": "https://files.pythonhosted.org/packages/0e/f6/d9564a0647b46069265b49db27c60b0493ea169107638d45028be1e8ad9c/avl_range_tree-0.4.0.tar.gz",
"platform": null,
"description": "# Augmented AVL Tree for Interval Search\n\n## Overview\n\nThis project implements an augmented AVL tree (a self-balancing binary search tree) in Python, designed specifically for storing and querying intervals efficiently. The tree allows you to insert intervals (with associated keys) and quickly search for the smallest interval containing a given point. This implementation is particularly useful for tasks like BIN (Bank Identification Number) range searches, where each interval represents a range of possible values.\n\n## Features\n\n- **Self-Balancing Tree**: The tree remains balanced after each insertion, ensuring that operations like search, insert, and delete remain efficient.\n- **Interval Queries**: Efficiently find the smallest interval that contains a given point.\n- **Pure Python Implementation**: The core logic is implemented purely in Python, making it easy to understand and modify.\n\n## Installation\n\n### Using `pip`\n\n1. Ensure you have Python 3.9 or higher installed.\n2. Install the package using `pip`:\n\n ```sh\n pip install avl_range_tree\n ```\n\n### Building from Source\n\nIf you'd like to build the package from source:\n\n1. Clone the repository:\n\n ```sh\n git clone git@github.com:mcoira/python-range-tree.git\n cd python-range-tree/\n ```\n \n2. Install the package:\n\n ```sh\n pip install .\n ```\n\n## Usage\n\n### Importing the Tree\n\n```python\nfrom avl_range_tree.avl_tree import RangeTree\n```\n\n### Inserting Intervals\n\nEach interval is defined by a start value, an end value, and a key (a unique identifier for that interval).\n\n```python\ntree = RangeTree()\ntree.insert(123456000000000000, 123456999999999999, \"key1\")\ntree.insert(987654000000000000, 987654999999999999, \"key2\")\n```\n\n### Searching for Intervals\n\nTo search for the smallest interval containing a given point:\n\n```python\nsearch_value = int(str(12345678).ljust(16, '0')) # Convert 123456 to 1234567800000000\nresult = tree.search(search_value)\n\nif result:\n start, end, key = result\n print(f\"Found interval: [{start}, {end}] with key: {key}\")\nelse:\n print(\"No interval found containing the point.\")\n```\n\n### Example Output\n\n```shell\nFound interval: [123456000000000000, 123456999999999999] with key: key1\n```\n\n## Use Cases\n\n### 1. BIN Range Lookup for Financial Transactions\n\nIn financial systems, BIN ranges are used to identify the issuing bank for credit and debit cards and some of the card's features. This tree can efficiently store and query BIN ranges, ensuring quick lookups during transaction processing.\n\n### 2. IP Address Range Search\n\nThis implementation can also be adapted to store and search IP address ranges, allowing for quick identification of network blocks.\n\n### 3. Date Range Queries\n\nYou can store and search for date ranges, which can be useful in applications like booking systems, where you need to check if a date falls within a certain range.\n\n## Performance\n\nThanks to the self-balancing nature of AVL trees, this implementation is highly efficient for both insertion and search operations. Unlike Red-Black trees, which are approximately balanced, AVL trees maintain strict balance, ensuring the tree's height is minimized. This strict balancing results in more rotations during insertion, making AVL trees slightly more expensive to build. However, this additional overhead pays off during queries, as the tree's height is kept to a minimum, improving search performance.\n\nThis characteristic is particularly beneficial in scenarios like BIN number management, where data is periodically updated but queried frequently. In such cases, the AVL tree offers a superior balance between build time and query performance, ensuring that the time complexity for operations remains O(log n + m), where n is the number of elements in the tree, and m is the number of overlapping intervals that contain the point.\n\n## License\n\nThis project is licensed under the MIT License. See the LICENSE file for details.\n\n",
"bugtrack_url": null,
"license": null,
"summary": "Augmented AVL tree to index and search intervals.",
"version": "0.4.0",
"project_urls": {
"Homepage": "https://github.com/mcoira/python-range-tree",
"Repository": "https://github.com/mcoira/python-range-tree"
},
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "c86d77c9318184b37c3bc559f6991fa1abda04219e0cc65afcb81cb51e4b4204",
"md5": "776a1043a1973692528d8d2b4708e26c",
"sha256": "9a29762658ff59f2a882bd4a69955a3669b173e64368804d8740569802312e64"
},
"downloads": -1,
"filename": "avl_range_tree-0.4.0-py3-none-any.whl",
"has_sig": false,
"md5_digest": "776a1043a1973692528d8d2b4708e26c",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": "<4.0,>=3.9",
"size": 7032,
"upload_time": "2024-08-20T14:44:02",
"upload_time_iso_8601": "2024-08-20T14:44:02.579295Z",
"url": "https://files.pythonhosted.org/packages/c8/6d/77c9318184b37c3bc559f6991fa1abda04219e0cc65afcb81cb51e4b4204/avl_range_tree-0.4.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "0ef6d9564a0647b46069265b49db27c60b0493ea169107638d45028be1e8ad9c",
"md5": "d901c475dfcb99e05823c08a25409c4f",
"sha256": "7337718218f6d5f570968f0ad14b810f03abd8e8b824fea8229e2316b0c351e0"
},
"downloads": -1,
"filename": "avl_range_tree-0.4.0.tar.gz",
"has_sig": false,
"md5_digest": "d901c475dfcb99e05823c08a25409c4f",
"packagetype": "sdist",
"python_version": "source",
"requires_python": "<4.0,>=3.9",
"size": 6303,
"upload_time": "2024-08-20T14:44:03",
"upload_time_iso_8601": "2024-08-20T14:44:03.989950Z",
"url": "https://files.pythonhosted.org/packages/0e/f6/d9564a0647b46069265b49db27c60b0493ea169107638d45028be1e8ad9c/avl_range_tree-0.4.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2024-08-20 14:44:03",
"github": true,
"gitlab": false,
"bitbucket": false,
"codeberg": false,
"github_user": "mcoira",
"github_project": "python-range-tree",
"travis_ci": false,
"coveralls": false,
"github_actions": false,
"lcname": "avl_range_tree"
}
JSON
