3 releases
| 0.1.2 | Oct 1, 2020 |
|---|---|
| 0.1.1 | Aug 26, 2020 |
| 0.1.0 | Aug 25, 2020 |
#1697 in Data structures
72KB
1.5K
SLoC
treers
Sedgewick's Tree Maps, simple implementations
About
This is a hobby project, simple rewrite of Sedgewick's tree structures in Rust.
Contribute
Please contribute, feel free to write an issue, there are still plenty things to improve (such as improvement of docs).
Tree Maps
Interfaces Traits
- SedgewickMap
| Name | Description |
|---|---|
| new | New Instance of Tree Map |
| size | Count of items in map |
| get | Fetch an value in map by key |
| put | Insert by key-value |
| height | Tree Height |
| is_empty | Checks if map is empty |
| contains | Returns true if item exists |
| min | Retrieve a minimum key in map |
| max | Retrieve a maximum key in map |
| delete | TODO |
- TreeTraversal
| Name | Description |
|---|---|
| pre_order | Pre Order Traversal; DFS |
| in_order | In Order Traversal; DFS |
| post_order | Post Order Traversal; DFS |
| level_order | Level Order Traversal; BFS |
BST - Binary Search Tree
- Really slow (check benchmarks)
- Has a Tree Traversal implementation
| Algorithm | Average | Worst Case |
|---|---|---|
| Space | O(n) | O(n) |
| Search | O(log n) | O(n) |
| Insert | O(log n) | O(n) |
Red-Black Tree
- Only 3x slower (check benchmarks) times that Standard Balanced Tree Implementation
- Has a Tree Traversal implementation
- Basic Rules
- Every node can be only red or black
- Root node has to be black
- Red nodes lean left
- Every path from the root to a null link has the same number of black links
| Algorithm | Average | Worst Case |
|---|---|---|
| Space | O(n) | O(n) |
| Search | O(log n) | O(log n) |
| Insert | O(log n) | O(log n) |
BTree - Balanced Tree
- Really slow (check benchmarks)
- Doesn't have a Tree Traversal implementation
- Popular usage in Databases and File Systems
- NOTE: I have fixed a loitering (memory) bug in official algs4
| Algorithm | Average | Worst Case |
|---|---|---|
| Space | O(n) | O(n) |
| Search | O(log n) | O(log n) |
| Insert | O(log n) | O(log n) |
Documentation
TODO
- More work on documentation and README
- BTree, use stack memory for entries
- Replace tree traversals with iterators
- Implement remaining methods for trees
- Make Red-Black Tree blazingly fast
Resources
Authors
- Ivan Zvonimir Horvat GitHub Profile
License
Licensed under the MIT License.