Trait RecursiveSizeBalancedTree 

pub trait RecursiveSizeBalancedTree<T: LinkType> {
    // Required methods
    unsafe fn get_mut_left_reference(&mut self, node: T) -> *mut T;
    unsafe fn get_mut_right_reference(&mut self, node: T) -> *mut T;
    unsafe fn get_left_reference(&self, node: T) -> *const T;
    unsafe fn get_right_reference(&self, node: T) -> *const T;
    unsafe fn get_left(&self, node: T) -> T;
    unsafe fn get_right(&self, node: T) -> T;
    unsafe fn get_size(&self, node: T) -> T;
    unsafe fn set_left(&mut self, node: T, left: T);
    unsafe fn set_right(&mut self, node: T, right: T);
    unsafe fn set_size(&mut self, node: T, size: T);
    unsafe fn first_is_to_the_left_of_second(&self, first: T, second: T) -> bool;
    unsafe fn first_is_to_the_right_of_second(
        &self,
        first: T,
        second: T,
    ) -> bool;

    // Provided methods
    unsafe fn get_left_or_default(&self, node: T) -> T { ... }
    unsafe fn get_right_or_default(&self, node: T) -> T { ... }
    unsafe fn get_size_or_zero(&self, node: T) -> T { ... }
    unsafe fn inc_size(&mut self, node: T) { ... }
    unsafe fn dec_size(&mut self, node: T) { ... }
    unsafe fn get_left_size(&self, node: T) -> T { ... }
    unsafe fn get_right_size(&self, node: T) -> T { ... }
    unsafe fn fix_size(&mut self, node: T) { ... }
    unsafe fn left_rotate(&mut self, root: *mut T) { ... }
    unsafe fn left_rotate_core(&mut self, root: T) -> T { ... }
    unsafe fn right_rotate(&mut self, root: *mut T) { ... }
    unsafe fn right_rotate_core(&mut self, root: T) -> T { ... }
    unsafe fn get_rightest(&self, current: T) -> T { ... }
    unsafe fn get_leftest(&self, current: T) -> T { ... }
    unsafe fn get_next(&self, node: T) -> T { ... }
    unsafe fn get_previous(&self, node: T) -> T { ... }
    unsafe fn contains(&self, node: T, root: T) -> bool { ... }
    unsafe fn clear_node(&mut self, node: T) { ... }
}

Base trait for a size-balanced binary search tree (SBT).

Provides node accessors, tree rotations (left_rotate, right_rotate), navigation (get_leftest, get_rightest, get_next, get_previous), and queries (contains).

Implementors supply the storage-level operations (the first 12 methods); all other methods have default implementations built on those primitives.

For iterative attach/detach, see IterativeSizeBalancedTree.

Safety

All methods are unsafe because they operate on raw node indices without bounds checking — the caller must ensure that every index passed to these methods refers to a valid, allocated node.

Required Methods

unsafe fn get_mut_left_reference(&mut self, node: T) -> *mut T

Returns a mutable raw pointer to the left-child field of node.

unsafe fn get_mut_right_reference(&mut self, node: T) -> *mut T

Returns a mutable raw pointer to the right-child field of node.

unsafe fn get_left_reference(&self, node: T) -> *const T

Returns a const raw pointer to the left-child field of node.

unsafe fn get_right_reference(&self, node: T) -> *const T

Returns a const raw pointer to the right-child field of node.

unsafe fn get_left(&self, node: T) -> T

Returns the left child of node.

unsafe fn get_right(&self, node: T) -> T

Returns the right child of node.

unsafe fn get_size(&self, node: T) -> T

Returns the subtree size stored at node.

unsafe fn set_left(&mut self, node: T, left: T)

Sets the left child of node.

unsafe fn set_right(&mut self, node: T, right: T)

Sets the right child of node.

unsafe fn set_size(&mut self, node: T, size: T)

Sets the subtree size of node.

unsafe fn first_is_to_the_left_of_second(&self, first: T, second: T) -> bool

Returns true if first should be placed to the left of second.

unsafe fn first_is_to_the_right_of_second(&self, first: T, second: T) -> bool

Returns true if first should be placed to the right of second.

Provided Methods

unsafe fn get_left_or_default(&self, node: T) -> T

Returns the left child of node, or T::funty(0) if node is zero.

unsafe fn get_right_or_default(&self, node: T) -> T

Returns the right child of node, or T::funty(0) if node is zero.

unsafe fn get_size_or_zero(&self, node: T) -> T

Returns the size of node, or zero if node is zero.

unsafe fn inc_size(&mut self, node: T)

Increments the subtree size of node by one.

unsafe fn dec_size(&mut self, node: T)

Decrements the subtree size of node by one.

unsafe fn get_left_size(&self, node: T) -> T

Returns the size of the left subtree of node.

unsafe fn get_right_size(&self, node: T) -> T

Returns the size of the right subtree of node.

unsafe fn fix_size(&mut self, node: T)

Recalculates the size of node from its children: size = left_size + right_size + 1.

unsafe fn left_rotate(&mut self, root: *mut T)

Performs a left rotation at the subtree rooted at *root, updating *root in place.

unsafe fn left_rotate_core(&mut self, root: T) -> T

Performs a left rotation and returns the new root.

unsafe fn right_rotate(&mut self, root: *mut T)

Performs a right rotation at the subtree rooted at *root, updating *root in place.

unsafe fn right_rotate_core(&mut self, root: T) -> T

Performs a right rotation and returns the new root.

unsafe fn get_rightest(&self, current: T) -> T

Returns the rightmost (maximum) node in the subtree rooted at current.

unsafe fn get_leftest(&self, current: T) -> T

Returns the leftmost (minimum) node in the subtree rooted at current.

unsafe fn get_next(&self, node: T) -> T

Returns the in-order successor of node.

unsafe fn get_previous(&self, node: T) -> T

Returns the in-order predecessor of node.

unsafe fn contains(&self, node: T, root: T) -> bool

Returns true if node exists in the tree rooted at root.

unsafe fn clear_node(&mut self, node: T)

Resets node’s left, right, and size fields to zero.

Implementors