Struct BstNode 

pub struct BstNode<Data, Parent = WithNoParent<Data>> {
    pub data: Data,
    pub parent: Parent,
    pub child: [Option<NonNull<BstNode<Data, Parent>>>; 2],
}

Fields

data: Data

parent: Parent

child: [Option<NonNull<BstNode<Data, Parent>>>; 2]

Implementations

impl<Data, Parent> BstNode<Data, Parent>

where Parent: Default,

pub fn new(data: Data) -> Self

Examples found in repository

crates/competitive/src/data_structure/binary_search_tree/node.rs (line 344)

    pub fn from_data<A>(data: Spec::Data, allocator: &mut A) -> Self
    where
        A: Allocator<BstNode<Spec::Data, Spec::Parent>>,
    {
        Self::new(allocator.allocate(BstNode::new(data)))
    }

crates/competitive/src/tree/link_cut_tree.rs (lines 192-195)

    pub fn add_node(&mut self, value: S::Value) -> usize {
        let index = self.nodes.len();
        let node = self.allocator.allocate(BstNode::new(LinkCutData {
            inner: S::new(value),
            index_and_reverse: index << 1,
        }));
        self.nodes.push(node);
        index
    }

crates/competitive/src/tree/top_tree.rs (lines 350-358)

    pub fn add_node(&mut self, info: S::Info) -> usize {
        let index = self.nodes.len();
        let sum = S::vertex(&info);
        let node = self.node_allocator.allocate(BstNode::new(TopTreeData {
            info,
            sum,
            light: None,
            belong: None,
            heavy_action: <A::ActionMonoid as Unital>::unit(),
            light_action: <A::ActionMonoid as Unital>::unit(),
            index_and_reverse: index << 1,
        }));
        self.nodes.push(node);
        index
    }

    fn node(&self, index: usize) -> TopPtr<S, A> {
        self.nodes[index]
    }

    #[inline]
    unsafe fn pull_top(node: TopPtr<S, A>) {
        unsafe { TopBstSpec::<S, A>::bottom_up(BstDataMutRef::new_unchecked(node)) };
    }

    #[inline]
    unsafe fn pull_rake(node: RakePtr<S, A>) {
        unsafe { RakeBstSpec::<S, A>::bottom_up(BstDataMutRef::new_unchecked(node)) };
    }

    #[inline]
    unsafe fn splay_top(node: TopPtr<S, A>) {
        let root = if A::ROOT_TO_NODE_TOP_DOWN {
            unsafe {
                splay_operations::with_parent::splay::<TopBstSpec<S, A>, TopTreeData<S, A>>(node)
            }
        } else {
            unsafe {
                splay_operations::with_parent::splay_with_local_top_down::<
                    TopBstSpec<S, A>,
                    TopTreeData<S, A>,
                >(node)
            }
        };
        if root != node {
            unsafe {
                (*node.as_ptr()).data.belong = (*root.as_ptr()).data.belong.take();
            }
        }
    }

    #[inline]
    unsafe fn splay_rake(node: RakePtr<S, A>) {
        unsafe {
            splay_operations::with_parent::splay_with_local_top_down::<
                RakeBstSpec<S, A>,
                RakeData<S, A>,
            >(node)
        };
    }

    unsafe fn rake_rightmost(mut node: RakePtr<S, A>) -> RakePtr<S, A> {
        loop {
            unsafe { RakeBstSpec::<S, A>::top_down(BstDataMutRef::new_unchecked(node)) };
            match unsafe { node.as_ref().child[1] } {
                Some(right) => node = right,
                None => return node,
            }
        }
    }

    unsafe fn rake_insert(
        &mut self,
        root: Option<RakePtr<S, A>>,
        key: S::Point,
    ) -> (RakePtr<S, A>, RakePtr<S, A>) {
        let mut node = self.rake_allocator.allocate(BstNode::new(RakeData {
            sum: key.clone(),
            key,
            action: <A::ActionMonoid as Unital>::unit(),
            buffer: <A::ActionMonoid as Unital>::unit(),
        }));
        if let Some(mut root) = root {
            unsafe {
                node.as_mut().child[0] = Some(root);
                root.as_mut().parent.parent = Some(node);
                Self::pull_rake(node);
            }
        }
        (node, node)
    }