Randomized Binary Search Tree

rbst.rs

fn main() {
    let tree = RBST::new();
}

//https://tjkendev.github.io/procon-library/python/binary_search_tree/RBST.html
pub mod rbst {
    use std::cmp::{Ordering::*, *};
    pub struct RBST<K> {
        root: Node<K>,
    }
    impl<K: Ord> RBST<K> {
        fn new() -> Self {
            Self { root: Node::NIL }
        }

        fn find(&self, x: &K) -> bool {
            let mut node = &self.root;
            while let Node::NODE {
                left, right, key, ..
            } = node
            {
                node = match key.cmp(x) {
                    Equal => return true,
                    Less => left,
                    Greater => right,
                }
            }
            false
        }

        fn at(&self, mut index: usize) -> Option<&K> {
            let mut node = &self.root;
            index += 1;
            while let Node::NODE {
                left,
                right,
                size,
                key,
            } = node
            {
                let v = if let Node::NODE { size, .. } = left {
                    size + 1
                } else {
                    1
                };
                node = match k.cmp(v) {
                    Equal => return Some(key),
                    Less => left,
                    Greater => right,
                };
            }
            None
        }
    }
    pub enum Node<K> {
        NIL,
        NODE {
            left: Box<Node<K>>,
            right: Box<Node<K>>,
            key: K,
            size: usize,
        },
    }
    impl<K: Ord> Node<K> {}
}