use crate::Error;
#[derive(Debug)]
struct BstNode<T: Ord + Clone> {
value: T,
left: Option<Box<BstNode<T>>>,
right: Option<Box<BstNode<T>>>,
}
#[derive(Debug)]
pub struct BinarySearchTree<T: Ord + Clone> {
root: Option<Box<BstNode<T>>>,
len: usize,
}
impl<T: Ord + Clone> BinarySearchTree<T> {
pub fn new() -> Self {
Self { root: None, len: 0 }
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn insert(&mut self, value: T) {
if self.search(&value) {
return;
}
self.root = Some(Self::insert_node(self.root.take(), value));
self.len += 1;
}
fn insert_node(node: Option<Box<BstNode<T>>>, value: T) -> Box<BstNode<T>> {
match node {
None => Box::new(BstNode {
value,
left: None,
right: None,
}),
Some(mut n) => {
if value < n.value {
n.left = Some(Self::insert_node(n.left.take(), value));
} else if value > n.value {
n.right = Some(Self::insert_node(n.right.take(), value));
}
n
}
}
}
pub fn delete(&mut self, value: &T) -> Result<(), Error> {
if !self.search(value) {
return Err(Error::NotFound);
}
self.root = Self::delete_node(self.root.take(), value);
self.len -= 1;
Ok(())
}
fn delete_node(node: Option<Box<BstNode<T>>>, value: &T) -> Option<Box<BstNode<T>>> {
let mut n = node?;
if value < &n.value {
n.left = Self::delete_node(n.left.take(), value);
} else if value > &n.value {
n.right = Self::delete_node(n.right.take(), value);
} else {
if n.left.is_none() {
return n.right;
}
if n.right.is_none() {
return n.left;
}
let successor = Self::min_node(n.right.as_ref().unwrap()).value.clone();
n.value = successor;
n.right = Self::delete_node(n.right.take(), &n.value);
}
Some(n)
}
fn min_node(node: &BstNode<T>) -> &BstNode<T> {
match &node.left {
Some(left) => Self::min_node(left),
None => node,
}
}
pub fn search(&self, value: &T) -> bool {
let mut current = &self.root;
while let Some(n) = current {
if value == &n.value {
return true;
} else if value < &n.value {
current = &n.left;
} else {
current = &n.right;
}
}
false
}
pub fn in_order(&self) -> Vec<T> {
let mut result = Vec::with_capacity(self.len);
Self::in_order_node(&self.root, &mut result);
result
}
fn in_order_node(node: &Option<Box<BstNode<T>>>, result: &mut Vec<T>) {
if let Some(n) = node {
Self::in_order_node(&n.left, result);
result.push(n.value.clone());
Self::in_order_node(&n.right, result);
}
}
}
impl<T: Ord + Clone> Default for BinarySearchTree<T> {
fn default() -> Self {
Self::new()
}
}
#[derive(Debug)]
struct AvlNode<T: Ord + Clone> {
value: T,
left: Option<Box<AvlNode<T>>>,
right: Option<Box<AvlNode<T>>>,
height: i32,
}
#[derive(Debug)]
pub struct AvlTree<T: Ord + Clone> {
root: Option<Box<AvlNode<T>>>,
len: usize,
}
impl<T: Ord + Clone> AvlTree<T> {
pub fn new() -> Self {
Self { root: None, len: 0 }
}
pub fn len(&self) -> usize {
self.len
}
pub fn is_empty(&self) -> bool {
self.len == 0
}
pub fn height(&self) -> i32 {
Self::height_node(&self.root)
}
fn height_node(node: &Option<Box<AvlNode<T>>>) -> i32 {
match node {
None => 0,
Some(n) => n.height,
}
}
fn update_height(n: &mut AvlNode<T>) {
n.height = 1
+ std::cmp::max(
Self::height_node(&n.left),
Self::height_node(&n.right),
);
}
fn balance_factor(n: &AvlNode<T>) -> i32 {
Self::height_node(&n.left) - Self::height_node(&n.right)
}
fn right_rotate(mut y: Box<AvlNode<T>>) -> Box<AvlNode<T>> {
let mut x = y.left.take().unwrap();
let t2 = x.right.take();
x.right = Some(y);
x.right.as_mut().unwrap().left = t2;
Self::update_height(x.right.as_mut().unwrap());
Self::update_height(&mut x);
x
}
fn left_rotate(mut x: Box<AvlNode<T>>) -> Box<AvlNode<T>> {
let mut y = x.right.take().unwrap();
let t2 = y.left.take();
y.left = Some(x);
y.left.as_mut().unwrap().right = t2;
Self::update_height(y.left.as_mut().unwrap());
Self::update_height(&mut y);
y
}
pub fn insert(&mut self, value: T) {
if self.search(&value) {
return;
}
self.root = Some(Self::insert_node(self.root.take(), value));
self.len += 1;
}
fn insert_node(node: Option<Box<AvlNode<T>>>, value: T) -> Box<AvlNode<T>> {
match node {
None => Box::new(AvlNode {
value,
left: None,
right: None,
height: 1,
}),
Some(mut n) => {
if value < n.value {
n.left = Some(Self::insert_node(n.left.take(), value.clone()));
} else if value > n.value {
n.right = Some(Self::insert_node(n.right.take(), value.clone()));
} else {
return n;
}
Self::update_height(&mut n);
let balance = Self::balance_factor(&n);
if balance > 1 && value < n.left.as_ref().unwrap().value {
return Self::right_rotate(n);
}
if balance < -1 && value > n.right.as_ref().unwrap().value {
return Self::left_rotate(n);
}
if balance > 1 && value > n.left.as_ref().unwrap().value {
n.left = Some(Self::left_rotate(n.left.take().unwrap()));
return Self::right_rotate(n);
}
if balance < -1 && value < n.right.as_ref().unwrap().value {
n.right = Some(Self::right_rotate(n.right.take().unwrap()));
return Self::left_rotate(n);
}
n
}
}
}
pub fn delete(&mut self, value: &T) -> Result<(), Error> {
if !self.search(value) {
return Err(Error::NotFound);
}
self.root = Self::delete_node(self.root.take(), value);
self.len -= 1;
Ok(())
}
fn delete_node(node: Option<Box<AvlNode<T>>>, value: &T) -> Option<Box<AvlNode<T>>> {
let mut n = node?;
if value < &n.value {
n.left = Self::delete_node(n.left.take(), value);
} else if value > &n.value {
n.right = Self::delete_node(n.right.take(), value);
} else {
if n.left.is_none() || n.right.is_none() {
let temp = if n.left.is_some() { n.left } else { n.right };
return temp;
}
let successor = Self::min_value_node(n.right.as_ref().unwrap()).value.clone();
n.value = successor;
n.right = Self::delete_node(n.right.take(), &n.value);
}
Self::update_height(&mut n);
let balance = Self::balance_factor(&n);
if balance > 1 && Self::balance_factor(n.left.as_ref().unwrap()) >= 0 {
return Some(Self::right_rotate(n));
}
if balance > 1 && Self::balance_factor(n.left.as_ref().unwrap()) < 0 {
n.left = Some(Self::left_rotate(n.left.take().unwrap()));
return Some(Self::right_rotate(n));
}
if balance < -1 && Self::balance_factor(n.right.as_ref().unwrap()) <= 0 {
return Some(Self::left_rotate(n));
}
if balance < -1 && Self::balance_factor(n.right.as_ref().unwrap()) > 0 {
n.right = Some(Self::right_rotate(n.right.take().unwrap()));
return Some(Self::left_rotate(n));
}
Some(n)
}
fn min_value_node(node: &AvlNode<T>) -> &AvlNode<T> {
match &node.left {
Some(left) => Self::min_value_node(left),
None => node,
}
}
pub fn search(&self, value: &T) -> bool {
let mut current = &self.root;
while let Some(n) = current {
if value == &n.value {
return true;
} else if value < &n.value {
current = &n.left;
} else {
current = &n.right;
}
}
false
}
pub fn in_order(&self) -> Vec<T> {
let mut result = Vec::with_capacity(self.len);
Self::in_order_node(&self.root, &mut result);
result
}
fn in_order_node(node: &Option<Box<AvlNode<T>>>, result: &mut Vec<T>) {
if let Some(n) = node {
Self::in_order_node(&n.left, result);
result.push(n.value.clone());
Self::in_order_node(&n.right, result);
}
}
}
impl<T: Ord + Clone> Default for AvlTree<T> {
fn default() -> Self {
Self::new()
}
}