use rand::seq::SliceRandom;
use rand::{thread_rng, Rng};

use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Debug, PartialEq)]
enum NodeColor {
    Red,
    Black,
}

#[derive(Debug)]
struct TreeNode<T> {
    pub color: NodeColor,
    pub key: T,
    pub parent: Option<Weak<RefCell<TreeNode<T>>>>,
    left: Option<Rc<RefCell<TreeNode<T>>>>,
    right: Option<Rc<RefCell<TreeNode<T>>>>,
}

impl<T> TreeNode<T> {
    fn new(val: T) -> Self {
        TreeNode {
            color: NodeColor::Red,
            key: val,
            parent: None,
            left: None,
            right: None,
        }
    }

    fn is_parent_red(&self) -> bool {
        match self.parent.as_ref() {
            None => false,
            Some(x) => x.upgrade().unwrap().borrow().color == NodeColor::Red,
        }
    }
}

#[derive(Debug)]
pub struct RBTree {
    root: Option<Rc<RefCell<TreeNode<u32>>>>,
}

impl RBTree {
    pub fn new() -> Self {
        RBTree { root: None }
    }

    fn rotate_left(&mut self, target: &Rc<RefCell<TreeNode<u32>>>) {
        {
            let o_p_option = &target.borrow().parent;

            let n_p_option = &target.borrow().right;

            if target.borrow().parent.is_none() {
                self.root = n_p_option.clone();
            }

            if let Some(o_p) = o_p_option {
                if RBTree::am_i_left_side(target) {
                    o_p.upgrade().unwrap().borrow_mut().left = n_p_option.clone();
                } else {
                    o_p.upgrade().unwrap().borrow_mut().right = n_p_option.clone();
                }
            }
            n_p_option.as_ref().unwrap().borrow_mut().parent = o_p_option.clone();
        }
        let n_p = target.borrow().right.as_ref().unwrap().clone();
        target.borrow_mut().parent = Some(Rc::downgrade(&n_p));

        // movedown
        if n_p.borrow().left.is_some() {
            target.borrow_mut().right = Some(n_p.borrow().left.as_ref().unwrap().clone());
            n_p.borrow_mut().left.as_ref().unwrap().borrow_mut().parent =
                Some(Rc::downgrade(target));
        } else {
            target.borrow_mut().right = None;
        }
        n_p.borrow_mut().left = Some(target.clone());
    }

    fn rotate_right(&mut self, target: &Rc<RefCell<TreeNode<u32>>>) {
        {
            let o_p_option = &target.borrow().parent;

            let n_p_option = &target.borrow().left;

            if target.borrow().parent.is_none() {
                self.root = n_p_option.clone();
            }

            if let Some(o_p) = o_p_option {
                if RBTree::am_i_left_side(target) {
                    o_p.upgrade().unwrap().borrow_mut().left = n_p_option.clone();
                } else {
                    o_p.upgrade().unwrap().borrow_mut().right = n_p_option.clone();
                }
            }
            n_p_option.as_ref().unwrap().borrow_mut().parent = o_p_option.clone();
        }
        let n_p = target.borrow().left.as_ref().unwrap().clone();
        target.borrow_mut().parent = Some(Rc::downgrade(&n_p));
        // movedown

        if n_p.borrow().right.is_some() {
            target.borrow_mut().left = Some(n_p.borrow().right.as_ref().unwrap().clone());
            n_p.borrow_mut().right.as_ref().unwrap().borrow_mut().parent =
                Some(Rc::downgrade(target));
        } else {
            target.borrow_mut().left = None;
        }
        n_p.borrow_mut().right = Some(target.clone());
    }
    fn find_successor(
        node: Option<Rc<RefCell<TreeNode<u32>>>>,
    ) -> Option<Rc<RefCell<TreeNode<u32>>>> {
        if node.as_ref().unwrap().borrow().right.is_some() {
            return Self::find_successor(node.as_ref().unwrap().borrow().right.clone());
        }
        return node;
    }

    fn find_replacement(node: &Rc<RefCell<TreeNode<u32>>>) -> Option<Rc<RefCell<TreeNode<u32>>>> {
        let node = node.borrow();
        if node.left.is_some() && node.right.is_some() {
            return Self::find_successor(node.left.clone());
        }

        if node.left.is_none() && node.right.is_none() {
            return None;
        }

        if node.left.is_some() {
            return node.left.clone();
        } else {
            return node.right.clone();
        }
    }

    pub fn delete(&mut self, val: u32) -> Result<(), String> {
        if self.root.is_none() {
            return Err(format!("Tree has no nodes").to_string());
        }
        let (found, option_to_delete) = self.binary_search(val);
        if !found {
            return Err(format!("Node not found").to_string());
        }
        let mut node_to_delete = option_to_delete.as_ref().unwrap();
        self.delete_node(&mut node_to_delete)
    }

    fn delete_node(
        &mut self,
        node_to_delete: &mut &Rc<RefCell<TreeNode<u32>>>,
    ) -> Result<(), String> {
        let u = Self::find_replacement(node_to_delete);

        let uv_black: bool = (u.is_none()
            || Self::get_color(u.as_ref().unwrap()) == NodeColor::Black)
            && Self::get_color(node_to_delete) == NodeColor::Black;
        let parent = if node_to_delete.borrow().parent.is_some() {
            node_to_delete.borrow().parent.as_ref().unwrap().upgrade()
        } else {
            None
        };

        if u.is_none() {
            // u is null so the node_to_delete is the leaf
            if node_to_delete.borrow().parent.is_none() {
                // Node is the root.
                self.root = None;
            } else {
                if uv_black {
                    // u & node_to_delete are black. node_to_delete is the leaf.
                    self.fix_double_black(node_to_delete);
                } else {
                    // u or node_to_delete is red
                    if Self::get_sibiling(node_to_delete).is_some() {
                        // Sibiling exists, so make it red.
                        Self::set_color_rc(node_to_delete, NodeColor::Red);
                    }
                }

                // Remove node_to_delete from tree
                if Self::am_i_left_side(node_to_delete) {
                    parent.as_ref().unwrap().borrow_mut().left = None;
                } else {
                    parent.as_ref().unwrap().borrow_mut().right = None;
                }
            }

            // Deleted node.
            return Ok(());
        }

        if node_to_delete.borrow().left.is_none() || node_to_delete.borrow().right.is_none() {
            // Node to delete has 1 child
            if node_to_delete.borrow().parent.is_none() {
                // Node to delete is the root. Assign the value of u to the node-to-delete.
                let u_key = Self::get_key(u.as_ref().unwrap());
                let mut root = self.root.as_ref().unwrap().borrow_mut();
                root.key = u_key;
                root.left = None;
                root.right = None;
            } else {
                // Detach node-to-delete from tree and move up.
                if Self::am_i_left_side(node_to_delete) {
                    parent.as_ref().unwrap().borrow_mut().left = u.clone();
                } else {
                    parent.as_ref().unwrap().borrow_mut().right = u.clone();
                }

                // Set u's parent to be a weak reference to "parent"
                u.as_ref().unwrap().borrow_mut().parent =
                    Some(Rc::downgrade(&parent.as_ref().unwrap().clone()));
                if uv_black {
                    self.fix_double_black(u.as_ref().unwrap());
                } else {
                    Self::set_color_rc(&mut u.as_ref().unwrap(), NodeColor::Black);
                }
            }
            return Ok(());
        }

        // node_to_delete has 2 children, swap values with successor and recurse.
        let u_key = Self::get_key(u.as_ref().unwrap());
        let node_to_delete_key = Self::get_key(node_to_delete);
        u.as_ref().unwrap().borrow_mut().key = node_to_delete_key;
        node_to_delete.borrow_mut().key = u_key;

        self.delete_node(&mut u.as_ref().unwrap())?;
        return Ok(());
    }

    fn fix_double_black(&mut self, node: &Rc<RefCell<TreeNode<u32>>>) {
        if node.borrow().parent.is_none() {
            // Node is root.
            return;
        }

        let sibiling = Self::get_sibiling(node);
        let parent = Self::get_parent(node);

        if sibiling.is_none() {
            // No sibiling, double black pushed up.
            self.fix_double_black(&parent.unwrap());
        } else {
            if Self::get_color(sibiling.as_ref().unwrap()) == NodeColor::Red {
                // Sibiling red
                Self::set_color_rc(&mut parent.as_ref().unwrap(), NodeColor::Red);
                Self::set_color_rc(&mut sibiling.as_ref().unwrap(), NodeColor::Black);

                if Self::am_i_left_side(sibiling.as_ref().unwrap()) {
                    // left case
                    self.rotate_right(parent.as_ref().unwrap());
                } else {
                    // right case
                    self.rotate_left(parent.as_ref().unwrap());
                }
                self.fix_double_black(node);
            } else {
                // Sibiling is black
                if Self::has_red_child(sibiling.as_ref().unwrap()) {
                    // at least 1 red child
                    if sibiling.as_ref().unwrap().borrow().left.is_some()
                        && Self::get_color(
                            sibiling.as_ref().unwrap().borrow().left.as_ref().unwrap(),
                        ) == NodeColor::Red
                    {
                        if Self::am_i_left_side(sibiling.as_ref().unwrap()) {
                            // left left
                            let sibiling_color = Self::get_color(sibiling.as_ref().unwrap());
                            let parent_color = Self::get_color(parent.as_ref().unwrap());
                            Self::set_color_rc(
                                &mut sibiling
                                    .as_ref()
                                    .unwrap()
                                    .borrow_mut()
                                    .left
                                    .as_ref()
                                    .unwrap(),
                                sibiling_color,
                            );
                            Self::set_color_rc(&mut sibiling.as_ref().unwrap(), parent_color);
                            self.rotate_right(parent.as_ref().unwrap());
                        } else {
                            // right right
                            let parent_color = Self::get_color(parent.as_ref().unwrap());
                            Self::set_color_rc(
                                &mut sibiling
                                    .as_ref()
                                    .unwrap()
                                    .borrow_mut()
                                    .left
                                    .as_ref()
                                    .unwrap(),
                                parent_color,
                            );
                            self.rotate_right(sibiling.as_ref().unwrap());
                            self.rotate_left(parent.as_ref().unwrap());
                        }
                    } else {
                        if Self::am_i_left_side(sibiling.as_ref().unwrap()) {
                            // left right
                            let parent_color = Self::get_color(parent.as_ref().unwrap());
                            Self::set_color_rc(
                                &mut sibiling
                                    .as_ref()
                                    .unwrap()
                                    .borrow_mut()
                                    .right
                                    .as_ref()
                                    .unwrap(),
                                parent_color,
                            );
                            self.rotate_left(sibiling.as_ref().unwrap());
                            self.rotate_right(parent.as_ref().unwrap());
                        } else {
                            // right right
                            let sibiling_color = Self::get_color(sibiling.as_ref().unwrap());
                            let parent_color = Self::get_color(parent.as_ref().unwrap());
                            Self::set_color_rc(
                                &mut sibiling
                                    .as_ref()
                                    .unwrap()
                                    .borrow_mut()
                                    .right
                                    .as_ref()
                                    .unwrap(),
                                sibiling_color,
                            );
                            Self::set_color_rc(&mut sibiling.as_ref().unwrap(), parent_color);
                            self.rotate_left(parent.as_ref().unwrap());
                        }
                    }
                    Self::set_color_rc(&mut parent.as_ref().unwrap(), NodeColor::Black);
                } else {
                    // 2 black children
                    Self::set_color_rc(&mut sibiling.as_ref().unwrap(), NodeColor::Red);

                    if Self::get_color(parent.as_ref().unwrap()) == NodeColor::Black {
                        self.fix_double_black(parent.as_ref().unwrap());
                    } else {
                        Self::set_color_rc(&mut parent.as_ref().unwrap(), NodeColor::Black);
                    }
                }
            }
        }
    }

    pub fn search(&mut self, val: u32) -> Result<(), String> {
        match self.binary_search(val) {
            (false, _) => Err(format!("Node not found").to_string()),
            (true, _) => Ok(()),
        }
    }

    fn binary_search(&mut self, val: u32) -> (bool, Option<Rc<RefCell<TreeNode<u32>>>>) {
        let mut parent_option = None;
        if self.root.is_none() {
            return (false, None);
        }
        let mut child_option = Some(self.root.as_ref().unwrap().clone());
        // THIS COPIES THE NODE, WHICH WE DONT WANT, COPY THE REF INSTEAD!!
        // let mut child_option = self.root.clone();

        // will be reset no matter what, setting it only so the compiler doesnt yell

        // While we have a child to navigate
        while child_option.is_some() {
            // we want to keep track of who the parent is, because child will be None when the loop ends
            parent_option = child_option;
            // a lot of stripping required to get to the actual node. as_ref borrows it so we can use it later
            // unwrap removes the option, and borrow borrows the value from the refcell
            let parent_node = parent_option.as_ref().unwrap();
            // Now that we own the actual node, we use it to get the key, and determine whether we go down left or right path
            if parent_node.borrow().key > val {
                child_option = match parent_node.borrow().left {
                    // if left exists, set the child to be equal to left
                    Some(ref y) => (Some(y.clone())),
                    // otherwise, remember which side to put it, and return
                    None => None,
                };
            } else if parent_node.borrow().key < val {
                child_option = match parent_node.borrow().right {
                    Some(ref y) => (Some(y.clone())),
                    None => None,
                };
            } else {
                // if the value is already in the tree, dont add it again
                return (true, parent_option);
            }
        }
        return (false, parent_option);
    }

    pub fn insert(&mut self, val: u32) -> Result<(), String> {
        if self.is_empty() {
            let mut new_node = TreeNode::new(val);
            new_node.color = NodeColor::Black;
            self.root = Some(Rc::new(RefCell::new(new_node)));
        } else {
            let (found, parent_option) = self.binary_search(val);
            if found {
                return Err(format!("Node already exists").to_string());
            }
            let child_belongs_on_left = val < parent_option.as_ref().unwrap().borrow().key;
            // Make a newchild with val
            let new_child_node = Rc::new(RefCell::new(TreeNode::new(val)));
            let new_child_ref_clone = new_child_node.clone();
            let new_child = Some(new_child_node);

            // Make a weak pointing to the parent
            let weak_parent_ref = Rc::downgrade(&parent_option.as_ref().unwrap().clone());
            // set it as the child's parent
            new_child.as_ref().unwrap().borrow_mut().parent = Some(weak_parent_ref);

            // put it on the side that it should be on (we found it earlier)
            if child_belongs_on_left {
                parent_option.as_ref().unwrap().borrow_mut().left = new_child;
            } else {
                parent_option.as_ref().unwrap().borrow_mut().right = new_child;
            }
            self.rebalance(new_child_ref_clone);
        }
        Ok(())
    }

    fn rebalance(&mut self, new_child: Rc<RefCell<TreeNode<u32>>>) {
        // let mut child_node = child.borrow();
        // using rebalancing cases from
        // https://en.wikipedia.org/wiki/Red%E2%80%93black_tree#Insertion
        let mut child = new_child;
        loop {
            // child = new_child;
            if child.borrow().parent.is_none() {
                // Case 2
                Self::set_color_rc(&mut self.root.as_ref().unwrap(), NodeColor::Black);
                return;
            }
            if !child.borrow().is_parent_red() {
                // Case 3
                return;
            }
            // We know parent is red
            let mut parent = child.borrow().parent.as_ref().unwrap().upgrade().unwrap();
            // let parent_node = parent.borrow();
            if parent.borrow().parent.is_none() && parent.borrow().color == NodeColor::Red {
                // Case 6
                RBTree::set_color_rc(&mut &parent, NodeColor::Black);
                return;
            }
            // We know grandparent exists
            let grandparent = parent.borrow().parent.as_ref().unwrap().upgrade().unwrap();
            let uncle;

            // Check which side our parent is on to find our uncle (opposite side)
            let parent_left_side = RBTree::am_i_left_side(&parent);
            if parent_left_side {
                // if there is no (right side) uncle, or uncle is black:
                if grandparent.borrow().right.is_none()
                    || grandparent.borrow().right.as_ref().unwrap().borrow().color
                        == NodeColor::Black
                {
                    if !RBTree::am_i_left_side(&child) {
                        //Case 4

                        // &parent.borrow_mut().rotate_left();
                        self.rotate_left(&parent);
                        // child = parent;
                        parent = grandparent.borrow().left.as_ref().unwrap().clone();
                    }
                    // Case 5
                    self.rotate_right(&grandparent);
                    RBTree::set_color_rc(&mut &parent, NodeColor::Black);
                    RBTree::set_color_rc(&mut &grandparent, NodeColor::Red);

                    // grandparent.borrow_mut().rotate_right();
                    return;
                } else {
                    //Case 1
                    // if right side uncle exists
                    uncle = grandparent.borrow().right.as_ref().unwrap().clone();
                    RBTree::set_color_rc(&mut &parent, NodeColor::Black);
                    RBTree::set_color_rc(&mut &uncle, NodeColor::Black);
                    RBTree::set_color_rc(&mut &grandparent, NodeColor::Red);
                    // We've solved the problem at our node, but grandparent may have the same issue, so run it again.
                    child = grandparent;
                    continue;
                }
            } else {
                // if there is no (right side) uncle, or uncle is black:
                if grandparent.borrow().left.is_none()
                    || grandparent.borrow().left.as_ref().unwrap().borrow().color
                        == NodeColor::Black
                {
                    if RBTree::am_i_left_side(&child) {
                        //Case 4
                        self.rotate_right(&parent);

                        // parent.borrow_mut().rotate_right();

                        // child = parent;
                        parent = grandparent.borrow().right.as_ref().unwrap().clone();
                    }
                    // Case 5
                    self.rotate_left(&grandparent);
                    RBTree::set_color_rc(&mut &parent, NodeColor::Black);
                    RBTree::set_color_rc(&mut &grandparent, NodeColor::Red);

                    // grandparent.borrow_mut().rotate_left();
                    return;
                } else {
                    //Case 1
                    // if left side uncle exists
                    uncle = grandparent.borrow().left.as_ref().unwrap().clone();
                    RBTree::set_color_rc(&mut &parent, NodeColor::Black);
                    RBTree::set_color_rc(&mut &uncle, NodeColor::Black);
                    RBTree::set_color_rc(&mut &grandparent, NodeColor::Red);
                    // We've solved the problem at our node, but grandparent may have the same issue, so run it again.
                    child = grandparent;
                    continue;
                }
            }
        }
    }

    fn am_i_left_side(child: &Rc<RefCell<TreeNode<u32>>>) -> bool {
        let child_node = child.borrow();
        let parent = &child_node.parent.as_ref().unwrap().upgrade().unwrap();
        let parent_node = parent.borrow();
        // Check which side our parent is on
        match parent_node.left.as_ref() {
            Some(x) => x.borrow().key == child_node.key,
            None => false,
        }
    }

    fn get_sibiling(child: &Rc<RefCell<TreeNode<u32>>>) -> Option<Rc<RefCell<TreeNode<u32>>>> {
        let child_node = child.borrow();
        if child_node.parent.is_some() {
            let parent = &child_node.parent.as_ref().unwrap().upgrade().unwrap();
            let parent_node = parent.borrow();
            if Self::am_i_left_side(child) {
                return parent_node.right.clone();
            }
            return parent_node.left.clone();
        }
        return None
    }

    fn get_parent(child: &Rc<RefCell<TreeNode<u32>>>) -> Option<Rc<RefCell<TreeNode<u32>>>> {
        let child_node = child.borrow();
        if child_node.parent.is_some() {
            return child_node.parent.as_ref().unwrap().upgrade();
        }
        return None
    }

    fn has_red_child(child: &Rc<RefCell<TreeNode<u32>>>) -> bool {
        let child_node = child.borrow();

        if child_node.left.is_some()
            && Self::get_color(child_node.left.as_ref().unwrap()) == NodeColor::Red
        {
            return true;
        }
        if child_node.right.is_some()
            && Self::get_color(child_node.right.as_ref().unwrap()) == NodeColor::Red
        {
            return true;
        }
        return false;
    }

    fn get_color(node: &Rc<RefCell<TreeNode<u32>>>) -> NodeColor {
        let node = node.borrow();
        if node.color == NodeColor::Black {
            return NodeColor::Black;
        }
        return NodeColor::Red;
    }

    fn get_key(node: &Rc<RefCell<TreeNode<u32>>>) -> u32 {
        let node = node.borrow();
        return node.key;
    }

    fn set_color_rc(node: &mut &Rc<RefCell<TreeNode<u32>>>, color: NodeColor) {
        let mut node = node.borrow_mut();
        node.color = color;
    }

    pub fn get_num_leaves(&self) -> u32 {
        let mut count: u32 = 0;
        if self.is_empty() {
            return count;
        } else {
            count = private_get_num_leaves(&self.root, count);
        }

        fn private_get_num_leaves(
            node: &Option<Rc<RefCell<TreeNode<u32>>>>,
            mut current_count: u32,
        ) -> u32 {
            let node = node.as_ref().unwrap().borrow_mut();

            if !node.left.is_none() {
                current_count = private_get_num_leaves(&node.left, current_count);
            }
            if !node.right.is_none() {
                current_count = private_get_num_leaves(&node.right, current_count);
            }
            if node.left.is_none() && node.right.is_none() {
                current_count = current_count + 1;
            }

            current_count
        }

        count
    }

    pub fn height(&self) -> u32 {
        if self.is_empty() {
            return 0u32;
        }

        return recursive_get_depth(&self.root);

        fn recursive_get_depth(node: &Option<Rc<RefCell<TreeNode<u32>>>>) -> u32 {
            if node.is_none() {
                return 0u32;
            }

            let node = node.as_ref().unwrap().borrow_mut();

            let left_depth: u32 = recursive_get_depth(&node.left);
            let right_depth: u32 = recursive_get_depth(&node.right);

            if left_depth > right_depth {
                return left_depth + 1;
            }
            return right_depth + 1;
        }
    }

    pub fn is_empty(&self) -> bool {
        self.root.is_none()
    }

    fn get_nodes_in_order(&self) -> Vec<u32> {
        let mut vec = Vec::new();
        self.recursive_peek(&self.root, &mut vec);
        vec
    }

    fn recursive_peek(&self, node: &Option<Rc<RefCell<TreeNode<u32>>>>, vec: &mut Vec<u32>) {
        if node.is_none() {
            return;
        }

        let node = node.as_ref().unwrap().borrow_mut();

        self.recursive_peek(&node.left, vec);
        vec.push(node.key);
        self.recursive_peek(&node.right, vec);
    }

    pub fn print_nodes_in_order(&self) {
        if self.is_empty() {
            println!("Nothing in tree.");
        } else {
            let mut vec = Vec::new();
            self.recursive_peek(&self.root, &mut vec);
            println!("{:?}", vec);
        }
    }

    pub fn print_tree(&self) {
        println!("\nPrinting Tree in format <Left/Right Child> <Node Key> <Node Color>");
        recursive_print(&self.root, &"".to_string(), false, "Root".to_string());
        fn recursive_print(
            node: &Option<Rc<RefCell<TreeNode<u32>>>>,
            prefix_space: &String,
            is_right: bool,
            child_prefix: String,
        ) {
            if node.is_none() {
                let null_prefix = if is_right { "└ " } else { "├ " };
                println!("{}{}{} {}", prefix_space, null_prefix, child_prefix, "null");
                return;
            }

            let node = node.as_ref().unwrap().borrow();
            let color = if node.color == NodeColor::Black {
                "Black"
            } else {
                "Red"
            };
            let prefix_current = if is_right { "└ " } else { "├ " }; // Always prints L-node first then R-node

            // Print the current node
            println!(
                "{}{}{} {}:{}",
                prefix_space, prefix_current, child_prefix, node.key, color
            );

            // Increase the space
            let prefix_child = if is_right { "  " } else { "┤ " };
            let mut prefix_space = prefix_space.to_owned();
            prefix_space.push_str(&prefix_child);

            recursive_print(&node.left, &prefix_space, false, "🅻 ".to_string());
            recursive_print(&node.right, &prefix_space, true, "🆁 ".to_string());
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn nodes_sorted_rb() -> Result<(), String> {
        for _ in 0..100 {
            let mut my_tree = RBTree::new();
            let mut vec: Vec<u32> = (1..100).collect();
            vec.shuffle(&mut thread_rng());

            for i in 0..99 {
                my_tree.insert(vec[i])?;
            }
            let mut max = 0;

            for i in my_tree.get_nodes_in_order() {
                assert!(max < i);
                max = i;
            }
            assert!(my_tree.height() <= 9);
        }
        Ok(())
    }

    #[test]
    fn nodes_deleted_rb() -> Result<(), String> {
        let mut my_tree = RBTree::new();
        let iterations: usize = 100;
        let mut vec: Vec<u32> = (1..iterations as u32).collect();
        vec.shuffle(&mut thread_rng());

        for i in 0..(iterations - 1) {
            my_tree.insert(vec[i])?;
        }

        vec.shuffle(&mut thread_rng());

        let mut removed: Vec<u32> = Vec::new();

        for i in 0..(iterations - 1) {
            my_tree.delete(vec[i])?;
            removed.push(vec[i]);

            for j in 0..(iterations - 1) {
                if removed.contains(&vec[j]) {
                    assert!(my_tree.search(vec[j]).is_err());
                } else {
                    assert!(my_tree.search(vec[j]).is_ok());
                }
            }
        }

        assert!(my_tree.height() <= 9);
        Ok(())
    }
}