Struct OrderedBinaryTreeMapper 

pub struct OrderedBinaryTreeMapper<SA, T, A = CurrentStorage>
where
    SA: StorageMapperApi,
    A: StorageAddress<SA>,
    T: NestedEncode + NestedDecode + PartialOrd + PartialEq + Clone,
{ /* private fields */ }

A storage mapper implementing a binary search tree for ordered element storage. Note: This is NOT a self-balancing tree and can degrade to O(n) in worst-case scenarios.

Storage Layout

The OrderedBinaryTreeMapper stores nodes in a tree structure with parent/child relationships:

1. Root tracking:

   • base_key + "_rootId" → ID of the root node

2. Node storage:

   • base_key + "_id" + node_id → OrderedBinaryTreeNode<T> containing:
     • current_node_id: this node’s ID
     • left_id: ID of left child (smaller values)
     • right_id: ID of right child (larger values)
     • parent_id: ID of parent node
     • data: the stored value

3. ID counter:

   • base_key + "_lastId" → highest assigned node ID (auto-incrementing)

Binary Search Tree Properties

• Ordering: For any node, all left descendants < node < all right descendants
• Uniqueness: Duplicate values are rejected on insertion
• Node IDs: Auto-incrementing, never reused (similar to AddressToIdMapper)

Main Operations

• Insert: insert_element(data) - Adds element maintaining BST order. O(log n) average, O(n) worst case.
• Delete: delete_node(data) - Removes element. O(log n) average, O(n) worst case.
• Search: iterative_search(node, data) / recursive_search(node, data) - Finds element. O(log n) average.
• Min/Max: find_min(node) / find_max(node) - Finds minimum/maximum in subtree. O(log n).
• Successor/Predecessor: find_successor(node) / find_predecessor(node) - Next/previous in order. O(log n).
• Depth: get_depth(node) - Computes tree depth from node. O(n).
• Root: get_root() - Returns root node. O(1).

Trade-offs

• Pros: Maintains sorted order; efficient ordered iteration; supports range queries; successor/predecessor lookups.
• Cons: NOT self-balancing (can degrade to O(n) in worst case); complex deletion logic; higher storage overhead than simple collections; removed nodes leave ID gaps.

Performance Notes

This is a basic binary search tree, not a balanced variant (e.g., AVL, Red-Black). Performance depends on insertion order:

• Balanced tree (random insertions): O(log n) operations
• Degenerate tree (sorted insertions): O(n) operations (becomes a linked list)

Use Cases

• Leaderboards requiring sorted access
• Priority systems with ordered iteration
• Range queries (find all elements between X and Y)
• Scenarios needing both membership testing and ordering
• When you need successor/predecessor operations

Example

// Insert elements (maintains BST ordering)
let node1_id = mapper.insert_element(50);
let node2_id = mapper.insert_element(30);
let node3_id = mapper.insert_element(70);
let node4_id = mapper.insert_element(20);
let node5_id = mapper.insert_element(40);

// Duplicate insertion returns 0 (failure)
let duplicate = mapper.insert_element(50);
assert_eq!(duplicate, 0);

// Search for element
let root = mapper.get_root().unwrap();
let found = mapper.iterative_search(Some(root.clone()), &30);
assert!(found.is_some());
assert_eq!(found.unwrap().data, 30);

// Find minimum and maximum
let min_node = mapper.find_min(root.clone());
assert_eq!(min_node.data, 20);

let max_node = mapper.find_max(root.clone());
assert_eq!(max_node.data, 70);

// Find successor (next larger element)
let node_30 = mapper.iterative_search(Some(root.clone()), &30).unwrap();
let successor = mapper.find_successor(node_30);
assert_eq!(successor.unwrap().data, 40);

// Find predecessor (next smaller element)
let node_50 = root.clone();
let predecessor = mapper.find_predecessor(node_50);
assert_eq!(predecessor.unwrap().data, 40);

// Get tree depth
let depth = mapper.get_depth(&root);
assert!(depth > 0);

// Delete element
mapper.delete_node(30);
let not_found = mapper.iterative_search(mapper.get_root(), &30);
assert!(not_found.is_none());

// Tree structure is maintained after deletion
let new_root = mapper.get_root().unwrap();
let still_there = mapper.iterative_search(Some(new_root), &40);
assert!(still_there.is_some());

Implementations

impl<SA, T, A> OrderedBinaryTreeMapper<SA, T, A>

where SA: StorageMapperApi, A: StorageAddress<SA>, T: NestedEncode + NestedDecode + PartialOrd + PartialEq + Clone,

pub fn get_root(&self) -> Option<OrderedBinaryTreeNode<T>>

pub fn get_depth(&self, node: &OrderedBinaryTreeNode<T>) -> usize

pub fn recursive_search( &self, opt_node: Option<OrderedBinaryTreeNode<T>>, data: &T, ) -> Option<OrderedBinaryTreeNode<T>>

pub fn iterative_search( &self, opt_node: Option<OrderedBinaryTreeNode<T>>, data: &T, ) -> Option<OrderedBinaryTreeNode<T>>

pub fn find_max( &self, node: OrderedBinaryTreeNode<T>, ) -> OrderedBinaryTreeNode<T>

pub fn find_min( &self, node: OrderedBinaryTreeNode<T>, ) -> OrderedBinaryTreeNode<T>

pub fn find_successor( &self, node: OrderedBinaryTreeNode<T>, ) -> Option<OrderedBinaryTreeNode<T>>

pub fn find_predecessor( &self, node: OrderedBinaryTreeNode<T>, ) -> Option<OrderedBinaryTreeNode<T>>

pub fn insert_element(&mut self, new_data: T) -> u64

pub fn delete_node(&mut self, data: T)

Trait Implementations

impl<SA, T> StorageMapper<SA> for OrderedBinaryTreeMapper<SA, T, CurrentStorage>

where SA: StorageMapperApi, T: NestedEncode + NestedDecode + PartialOrd + PartialEq + Clone + 'static,

fn new(base_key: StorageKey<SA>) -> Self

Will be called automatically by the #[storage_mapper] annotation generated code.