Created
February 9, 2022 15:13
-
-
Save joelpalmer/5b01e48c09ccbf7b4a00242e1ad6afc8 to your computer and use it in GitHub Desktop.
Balanced Binary Tree in Rust
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
use std::collections::VecDeque; | |
#[derive(Debug, PartialEq)] | |
pub struct BinaryTree<T> { | |
pub value: T, | |
pub left: Option<Box<BinaryTree<T>>>, | |
pub right: Option<Box<BinaryTree<T>>>, | |
} | |
impl<T> BinaryTree<T> | |
where | |
T: Copy, | |
{ | |
pub fn new(value: T) -> Self { | |
BinaryTree { | |
value, | |
left: None, | |
right: None, | |
} | |
} | |
pub fn left(mut self, node: BinaryTree<T>) -> Self { | |
self.left = Some(Box::new(node)); | |
self | |
} | |
pub fn right(mut self, node: BinaryTree<T>) -> Self { | |
self.right = Some(Box::new(node)); | |
self | |
} | |
pub fn insert(&mut self, new_value: T) { | |
let mut queue: VecDeque<&mut BinaryTree<T>> = VecDeque::new(); | |
queue.push_front(self); | |
loop { | |
let BinaryTree { | |
ref mut left, | |
ref mut right, | |
.. | |
} = queue.pop_back().unwrap(); | |
match left { | |
Some(node) => { | |
queue.push_front(node); | |
} | |
None => { | |
*left = Some(Box::new(BinaryTree::new(new_value))); | |
return; | |
} | |
} | |
match right { | |
Some(node) => { | |
queue.push_front(node); | |
} | |
None => { | |
*right = Some(Box::new(BinaryTree::new(new_value))); | |
return; | |
} | |
} | |
} | |
} | |
pub fn from(new_values: &[T]) -> Self { | |
let (first, rest) = new_values.split_first().unwrap(); | |
let mut root: BinaryTree<T> = BinaryTree::new(*first); | |
for value in rest { | |
root.insert(*value); | |
} | |
root | |
} | |
} | |
#[cfg(test)] | |
mod tests { | |
use crate::BinaryTree; | |
#[test] | |
fn create_new_btree() { | |
let btree = BinaryTree::new(1); | |
assert_eq!(btree.value, 1); | |
} | |
#[test] | |
fn insert_left() { | |
let btree = BinaryTree::new(1).left(BinaryTree::new(2)); | |
if let Some(node) = btree.left { | |
assert_eq!(node.value, 2); | |
} | |
assert_eq!(btree.right, None); | |
} | |
#[test] | |
fn insert_right() { | |
let btree = BinaryTree::new(1).right(BinaryTree::new(2)); | |
if let Some(node) = btree.right { | |
assert_eq!(node.value, 2); | |
} | |
assert_eq!(btree.left, None); | |
} | |
#[test] | |
fn insert() { | |
let mut btree = BinaryTree::new(1); | |
btree.insert(2); | |
btree.insert(3); | |
btree.insert(47); | |
btree.insert(5); | |
assert_eq!( | |
btree, | |
BinaryTree::new(1) | |
.left( | |
BinaryTree::new(2) | |
.left(BinaryTree::new(47)) | |
.right(BinaryTree::new(5)) | |
) | |
.right(BinaryTree::new(3)) | |
); | |
btree.insert(7); | |
assert_eq!( | |
btree, | |
BinaryTree::new(1) | |
.left( | |
BinaryTree::new(2) | |
.left(BinaryTree::new(47)) | |
.right(BinaryTree::new(5)) | |
) | |
.right(BinaryTree::new(3).left(BinaryTree::new(7))) | |
) | |
} | |
#[test] | |
fn create_btree_from_array() { | |
let btree = BinaryTree::from(&[1, 2, 3, 47, 5, 6]); | |
assert_eq!( | |
btree, | |
BinaryTree::new(1) | |
.left( | |
BinaryTree::new(2) | |
.left(BinaryTree::new(47)) | |
.right(BinaryTree::new(5)) | |
) | |
.right(BinaryTree::new(3).left(BinaryTree::new(6))) | |
) | |
} | |
} | |
// Ref: https://dawchihliou.github.io/articles/binary-tree-insertion-in-rust |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment