README.md

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
• 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)

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.