Recursive & Iterative Binary Search Tree Implementations within Rust

Hamothy

Last update: Oct 1, 2022

Related tags

Data structures rust data-structures binary-search-tree binary-tree rust-library bst rust-crate bst-tree

Overview

bst-rs

Recursive & Iterative Binary Search Tree Implementations within Rust

Personal Goals
About
Quick Start
License
Contributing
Inspiration

About

This crate contains Recursive & Iterative Binary Search Tree Implementations. All common operations are included along with common traversal iterators.

All elements within the Binary Search Trees must implement the Ord trait.

It is also important to note that RecursiveBST is more likely to blow the stack. For more information on why that is the case, please have a look at The Story of Tail Call Optimizations in Rust.

Personal Goals

I have made this library with the personal goals of learning and solidifying concepts such as ownership, borrowing , generics and lifetimes. I cannot promise that the implementations are particularly efficient, or if they are, it was not at the forefront of my mind.

That being said, there are some areas I would love to improve/include:

Write Rust more idiomatically.
Implement a pretty_print() function to display the binary search trees nicely.
Implementing the Drop trait for iterative node cleanup.
Pre-allocating space on the heap for nodes to reduce inefficiency of inserts.

I'm more than happy to accept (and encourage) contributions if anyone is kind enough to do so. (Please look at CONTRIBUTING!)

Quick Start

use bst_rs::{BinarySearchTree, IterativeBST, RecursiveBST};

// Create new empty binary search trees
let mut iterative_bst = IterativeBST::new();
assert!(iterative_bst.is_empty());

let mut recursive_bst = RecursiveBST::new();
assert!(recursive_bst.is_empty());

// Insert elements (no duplicates are allowed)
iterative_bst.insert(10);
iterative_bst.insert(10);   // Element is not inserted
iterative_bst.insert(5);
iterative_bst.insert(2);
iterative_bst.insert(15);
iterative_bst.insert(25);

assert_eq!(iterative_bst.size(), 5);
recursive_bst.insert(10);
recursive_bst.insert(10);   // Element is not inserted
recursive_bst.insert(5);
recursive_bst.insert(2);
recursive_bst.insert(15);
recursive_bst.insert(25);
assert_eq!(recursive_bst.size(), 5);

// Check if element exists
assert!(iterative_bst.contains(&5));    // true
assert!(!iterative_bst.contains(&0));   // false
assert!(recursive_bst.contains(&5));    // true
assert!(!recursive_bst.contains(&0));   // false

// Remove elements
iterative_bst.remove(&10);
iterative_bst.remove(&50); // No change to tree as element does not exist
assert_eq!(iterative_bst.size(), 4);

recursive_bst.remove(&10);
recursive_bst.remove(&50); // No change to tree as element does not exist
assert_eq!(recursive_bst.size(), 4);

// View pre-order, in-order and post-order traversals
assert_eq!(iterative_bst.pre_order_vec(), vec![&15, &5, &2, &25]);
assert_eq!(iterative_bst.in_order_vec(), vec![&2, &5, &15, &25]);
assert_eq!(iterative_bst.post_order_vec(), vec![&2, &5, &25, &15]);

assert_eq!(recursive_bst.pre_order_vec(), vec![&15, &5, &2, &25]);
assert_eq!(recursive_bst.in_order_vec(), vec![&2, &5, &15, &25]);
assert_eq!(recursive_bst.post_order_vec(), vec![&2, &5, &25, &15]);

// Compare equality of trees
assert_eq!(iterative_bst.sorted_vec(), recursive_bst.sorted_vec());
assert_ne!(iterative_bst, IterativeBST::new());
assert_ne!(recursive_bst, RecursiveBST::new());

License

MIT License

Contributing

Please read the CONTRIBUTING.md before contributing! (Thank you!)

Inspiration

The book Learn Rust With Entirely Too Many Linked Lists inspired me to try and implement a Binary Search Trees within the language. I had also been wanting to create my first library for other crates to use.

A number of collections, such as linked-lists, binary-trees, or B-Trees are most easily implemented with aliasing pointers.

StaticRc is a safe reference-counted pointer, similar to Rc or Arc, though performing its reference-counting at compile-time rather than run-time, and

372 Dec 19, 2022

Rust-algorithm-club - Learn algorithms and data structures with Rust

Rust Algorithm Club 🚧 🚧 This repo is under construction. Most materials are written in Chinese. Check it out here if you are able to read Chinese. W

360 Dec 28, 2022

Array helpers for Rust's Vector and String types

array_tool Array helpers for Rust. Some of the most common methods you would use on Arrays made available on Vectors. Polymorphic implementations for

69 Dec 9, 2022

Generic array types in Rust

generic-array This crate implements generic array types for Rust. Requires minumum Rust version of 1.36.0, or 1.41.0 for From[T; N] implementations

325 Dec 25, 2022

A priority queue for Rust with efficient change function.

PriorityQueue This crate implements a Priority Queue with a function to change the priority of an object. Priority and items are stored in an IndexMap

139 Dec 30, 2022

Roaring bitmap implementation for Rust

RoaringBitmap This is not yet production ready. The API should be mostly complete now. This is a Rust port of the Roaring bitmap data structure, initi

Roaring bitmaps: A better compressed bitset

552 Jan 1, 2023

Rust Persistent Data Structures

Rust Persistent Data Structures Rust Persistent Data Structures provides fully persistent data structures with structural sharing. Setup To use rpds a

883 Dec 31, 2022

Rust crate to extend io::Read & io::Write types with progress callbacks

progress-streams Rust crate to provide progress callbacks for types which implement io::Read or io::Write. Examples Reader extern crate progress_strea

19 Dec 3, 2022

Parameterized routing for generic resources in Rust

Usher Usher provides an easy way to construct parameterized routing trees in Rust. The nodes of these trees is naturally generic, allowing Usher to le

34 Oct 22, 2022

Comments

Improve documentation

This change aims to improve on the grammar in the comments. I also adjusted the Personal Goals link in the README to match the order in the detailed section.

These are not very critical changes. As a newbie to Rust,the goal for me here is to get familiar with the project as I find it particularly interesting :)

opened by nassersaazi 1
[v0.1.1] -> Add bst![] macro defaulting to IterativeBST
Motivation

Users can currently only use IterativeBST & RecursiveBST structs directly for creating BinarySearchTrees. We should streamline this process by implementing a declarative macro that can instantiate the tree for them that defaults to the IterativeBST implementation.

E.G Given the user wants to represent the following tree:

graph TB; A((8))-->B((3)) A-->C((10)) B-->D((1)) B-->E((6)) C-->F((9)) C-->G((15))

The code could look like:

let mut bst = bst![8, 10, 9, 15, 3, 6, 1];

What We Need To Do

Add bst![] macro that defaults to the IterativeBST implementation.
enhancement good first issue
opened by sgoudham 0
[v0.1.1] -> Add retrieval methods for Predecessor & Successor
Context

Common operations surrounding BST's are retrieving Predecessor & Successor Successors. The definitions of both terms are as follows:

Successor

The Successor can be thought of as the smallest value greater than the value of the given node.

E.G. Given a tree that looks like:

graph TB; A((8))-->B((3)) A-->C((10)) B-->D((1)) B-->E((6)) C-->F((9)) C-->G((14)) E-->H((4)) E-->I((7))

The Successor of 3 is 4.

Predecessor

The Predecessor can be thought of as the greatest value less than the value of the given node.

E.G Given a tree that looks like:

graph TB; A((8))-->B((3)) A-->C((10)) B-->D((1)) B-->E((6)) C-->F((9)) C-->G((14)) E-->H((4)) E-->I((7))

The Predecessor of 8 is 7.

What We Need To Do

Successor & Predecessor retrieval methods should implemented as part of the BinarySearchTree trait and implemented within RecursiveBST & IterativeBST
enhancement good first issue
opened by sgoudham 0