3 releases

0.1.2 Oct 1, 2020
0.1.1 Aug 26, 2020
0.1.0 Aug 25, 2020

#1408 in Data structures

36 downloads per month

MIT license

72KB
1.5K SLoC

treers

Sedgewick's Tree Maps, simple implementations

Travis Status Version GitHub Issues GitHub Pull Requests Downloads License GitHub last commit Twitter

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

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

Authors

License

Licensed under the MIT License.

No runtime deps