This is a hobby project, simple rewrite of Sedgewick's tree structures in Rust.
Please contribute, feel free to write an issue, there are still plenty things to improve (such as improvement of docs).
- 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 |
- 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) |
- 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
- Popular usage in CFS: Completely Fair Scheduler
| Algorithm | Average | Worst Case |
|---|---|---|
| Space | O(n) | O(n) |
| Search | O(log n) | O(log n) |
| Insert | O(log n) | O(log n) |
- 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) |
- 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
- Ivan Zvonimir Horvat GitHub Profile
Licensed under the MIT License.