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 | |-----------------------------|:------------------------:| | preorder | Pre Order Traversal; DFS | | inorder | In Order Traversal; DFS | | postorder | Post Order Traversal; DFS | | levelorder | 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

https://docs.rs/treers

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

• Algorithms, 4th Edition
• Coursera - Algorithms, Part I
• Coursera - Algorithms, Part II
• algs4, GitHub

Authors

• Ivan Zvonimir Horvat GitHub Profile

License

Licensed under the MIT License.