| Name | pythonic-bst JSON |
| Version |
1.0.3
JSON |
| download |
| home_page | |
| Summary | Minimalistic, unbalanced Binary Search Tree |
| upload_time | 2023-01-08 15:24:14 |
| maintainer | |
| docs_url | None |
| author | |
| requires_python | >=3.7 |
| license | 0BSD |
| keywords |
binary search tree
data structures
bst
|
| VCS |
|
| bugtrack_url |
|
| requirements |
No requirements were recorded.
|
| Travis-CI |
No Travis.
|
| coveralls test coverage |
No coveralls.
|
# PYTHONIC BST
A minimalistic, unbalanced Binary Search Tree written in pure Python. Originally developed as an example in a Python course.
The class `BST` works almost like a `dict` with sorted keys, and supports slicing and broadcasting. The methods exploit *lazy execution* when possible, all relevant operations are $O(log)$ complexity.
### BASIC USAGE
Install the latest stable version from PyPi:
```shell
~$ pip install pythonic-bst
```
then
```python
from bst import BST
```
* Create an empty BST: `foo = BST()`
* Add/update an item: `foo[k] = v`
* Remove an existing item: `rm foo[k]`
* Count items: `len(foo)`
* Check wether key $k$ is present: `if k in foo: ...`
* Check if the BST is not empty: `if foo: ...`
* Iterate forward: `for k, v in foo: ...`
* Iterate backward: `for k, v in reversed(foo): ...`
* Generate all the keys: `foo.keys()`
* Generate all the values: `foo.values()`
* Generate all $(k, v)$ pairs: `foo.items()`
* Standard BST-esque visits: `foo.visit_in_order()`, `foo.visit_pre_order()`, `foo.visit_post_order()`
### INITIALIZATION / CONVERSION
A BST can be initialized from a sequence of $(k, v)$ pairs, like another BST's iterator.
* Duplicate a BST: `bar = BST(foo)`
* Initialize a BST from a generic sequence of pairs: `foo = BST([(18, 5), (23, 10)])`
A dictionary may be used directly to initialize a BST and vice-versa.
* Initialize from a dictionary: `foo = BST(baz)`
* Create a dictionary from a BST: `baz = dict(foo)`
### SLICING / BROADCASTING
**Notes:** Slices are half-open. In `[k1:k2]`, key `k1` must be present in the BST, key `k2` is never included. The `step` can be `+1` (default) for *forward* and `-1` for *backward*.
* Iterate forward on keys $k \in [k_1, k_2[$: `for k, v in foo[k1:k2]: ...`
* Iterate backward on keys $k \in ]k_1, k_2]$: `for k, v in foo[k2:k1:-1]: ...`
* Update the first three items with keys $k \in [k_1, k_2[$: `foo[k1:k2] = [v1, v2, v3]`
* Set all items with keys $k < k_2$ to a specific value: `foo[:k2] = v`
* Remove item with key $k_1$ and all subsequent ones: `rm foo[k1:]`
### PERFORMANCES
The *height* (longest path from the root), the *density* (percentage of internal nodes that have two successors), and the *unbalance* (relative difference between the longest and the shortest path from the root) may be accessed as properties, although at a **significant** cost.
```python
foo = BST()
for n in range(1_000_000):
foo[random.random()] = n
print(foo.height, foo.density, foo.unbalance)
# Initializing from known data creates an optimized structure
bar = BST(foo)
print(bar.height, bar.density, bar.unbalance)
```
may yield something like
```python
49 0.4997143041393656 0.8775510204081632
20 0.9073503634459752 0.05
```
### TESTING
Some unsystematic unit test has been implemented using [pytest](https://docs.pytest.org/) and [Coverage.py](https://coverage.readthedocs.io).
## LICENSE
**Copyright © 2023 by Giovanni Squillero**
Distributed under a [Zero-Clause BSD License](https://tldrlegal.com/license/bsd-0-clause-license) (SPDX: [0BSD](https://spdx.org/licenses/0BSD.html)), which allows unlimited freedom with the software without the requirement to include legal notices. See the full text for details.
Raw data
{
"_id": null,
"home_page": "",
"name": "pythonic-bst",
"maintainer": "",
"docs_url": null,
"requires_python": ">=3.7",
"maintainer_email": "",
"keywords": "Binary Search Tree,Data Structures,BST",
"author": "",
"author_email": "Giovanni Squillero <giovanni.squillero@polito.it>",
"download_url": "https://files.pythonhosted.org/packages/94/b5/fe3f85b40a4c1448c98c9a1d12ede332417c83095652873fa66f3deedf01/pythonic-bst-1.0.3.tar.gz",
"platform": null,
"description": "# PYTHONIC BST\n\nA minimalistic, unbalanced Binary Search Tree written in pure Python. Originally developed as an example in a Python course.\n\nThe class `BST` works almost like a `dict` with sorted keys, and supports slicing and broadcasting. The methods exploit *lazy execution* when possible, all relevant operations are $O(log)$ complexity.\n\n### BASIC USAGE\n\nInstall the latest stable version from PyPi:\n\n```shell\n~$ pip install pythonic-bst\n```\n\nthen\n\n```python\nfrom bst import BST\n```\n\n* Create an empty BST: `foo = BST()`\n* Add/update an item: `foo[k] = v`\n* Remove an existing item: `rm foo[k]`\n* Count items: `len(foo)`\n* Check wether key $k$ is present: `if k in foo: ...`\n* Check if the BST is not empty: `if foo: ...`\n* Iterate forward: `for k, v in foo: ...`\n* Iterate backward: `for k, v in reversed(foo): ...`\n* Generate all the keys: `foo.keys()`\n* Generate all the values: `foo.values()`\n* Generate all $(k, v)$ pairs: `foo.items()`\n* Standard BST-esque visits: `foo.visit_in_order()`, `foo.visit_pre_order()`, `foo.visit_post_order()`\n\n### INITIALIZATION / CONVERSION\n\nA BST can be initialized from a sequence of $(k, v)$ pairs, like another BST's iterator.\n\n* Duplicate a BST: `bar = BST(foo)`\n* Initialize a BST from a generic sequence of pairs: `foo = BST([(18, 5), (23, 10)])`\n\nA dictionary may be used directly to initialize a BST and vice-versa.\n\n* Initialize from a dictionary: `foo = BST(baz)`\n* Create a dictionary from a BST: `baz = dict(foo)`\n\n### SLICING / BROADCASTING\n\n**Notes:** Slices are half-open. In `[k1:k2]`, key `k1` must be present in the BST, key `k2` is never included. The `step` can be `+1` (default) for *forward* and `-1` for *backward*.\n\n* Iterate forward on keys $k \\in [k_1, k_2[$: `for k, v in foo[k1:k2]: ...`\n* Iterate backward on keys $k \\in ]k_1, k_2]$: `for k, v in foo[k2:k1:-1]: ...`\n\n* Update the first three items with keys $k \\in [k_1, k_2[$: `foo[k1:k2] = [v1, v2, v3]`\n* Set all items with keys $k < k_2$ to a specific value: `foo[:k2] = v`\n* Remove item with key $k_1$ and all subsequent ones: `rm foo[k1:]`\n\n### PERFORMANCES\n\nThe *height* (longest path from the root), the *density* (percentage of internal nodes that have two successors), and the *unbalance* (relative difference between the longest and the shortest path from the root) may be accessed as properties, although at a **significant** cost.\n\n```python\nfoo = BST()\nfor n in range(1_000_000):\n foo[random.random()] = n\nprint(foo.height, foo.density, foo.unbalance)\n\n# Initializing from known data creates an optimized structure\nbar = BST(foo)\nprint(bar.height, bar.density, bar.unbalance)\n```\n\nmay yield something like\n\n```python\n49 0.4997143041393656 0.8775510204081632\n20 0.9073503634459752 0.05\n```\n\n### TESTING\n\nSome unsystematic unit test has been implemented using [pytest](https://docs.pytest.org/) and [Coverage.py](https://coverage.readthedocs.io).\n\n## LICENSE\n\n**Copyright \u00a9 2023 by Giovanni Squillero** \nDistributed under a [Zero-Clause BSD License](https://tldrlegal.com/license/bsd-0-clause-license) (SPDX: [0BSD](https://spdx.org/licenses/0BSD.html)), which allows unlimited freedom with the software without the requirement to include legal notices. See the full text for details.\n",
"bugtrack_url": null,
"license": "0BSD",
"summary": "Minimalistic, unbalanced Binary Search Tree",
"version": "1.0.3",
"split_keywords": [
"binary search tree",
"data structures",
"bst"
],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "0907411e05297e35bd67bd2ad7806b400194b8ffaf4c85cf55a6e2698920481d",
"md5": "559d0228e391b3a4b0eebe0354699d95",
"sha256": "365ec487a00a1a4721bb54d7114454fa24a343ffdc4bf32841a5708b3785c53c"
},
"downloads": -1,
"filename": "pythonic_bst-1.0.3-py3-none-any.whl",
"has_sig": false,
"md5_digest": "559d0228e391b3a4b0eebe0354699d95",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": ">=3.7",
"size": 7220,
"upload_time": "2023-01-08T15:24:12",
"upload_time_iso_8601": "2023-01-08T15:24:12.812655Z",
"url": "https://files.pythonhosted.org/packages/09/07/411e05297e35bd67bd2ad7806b400194b8ffaf4c85cf55a6e2698920481d/pythonic_bst-1.0.3-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "94b5fe3f85b40a4c1448c98c9a1d12ede332417c83095652873fa66f3deedf01",
"md5": "bb913090725d5160bf00e8b7d9935f2b",
"sha256": "5ed9df20b351716c7105a6c64dc918f1de8bb49d525db0ed0f2ac87d8dc1d465"
},
"downloads": -1,
"filename": "pythonic-bst-1.0.3.tar.gz",
"has_sig": false,
"md5_digest": "bb913090725d5160bf00e8b7d9935f2b",
"packagetype": "sdist",
"python_version": "source",
"requires_python": ">=3.7",
"size": 8470,
"upload_time": "2023-01-08T15:24:14",
"upload_time_iso_8601": "2023-01-08T15:24:14.396969Z",
"url": "https://files.pythonhosted.org/packages/94/b5/fe3f85b40a4c1448c98c9a1d12ede332417c83095652873fa66f3deedf01/pythonic-bst-1.0.3.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2023-01-08 15:24:14",
"github": false,
"gitlab": false,
"bitbucket": false,
"lcname": "pythonic-bst"
}
