CMTreeTrait

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait

pub trait CMTreeTrait

Trait functions

new

Creates a new empty Cartesian Merkle Tree.

Examples

let tree = CMTreeTrait::new();
assert_eq!(tree.get_root_hash(), 0);
assert!(!tree.search(42));

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::new

fn new() -> CMTree

insert

Inserts a key into the Cartesian Merkle Tree.

The insertion maintains all three tree properties (BST, heap, Merkle) through:

BST insertion based on key comparison
Treap rotations to maintain heap property based on priority
Merkle hash updates for cryptographic integrity

Priority is deterministically calculated from the key, ensuring consistent tree structure.

Examples

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.search(42));

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::insert

fn insert(ref self: CMTree, key: felt252)

insert_node

Internal recursive function for inserting a node while maintaining tree properties.

Performs BST insertion based on key comparison, then checks and restores heap property through rotations if necessary. Updates Merkle hashes along the insertion path.

Arguments

current - The current node being examined
new_node - The node to insert

Returns

The root of the subtree after insertion and any necessary rotations

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::insert_node

fn insert_node(current: Box<CMTNode>, new_node: Box<CMTNode>) -> Box<CMTNode>

restore_heap_property

Restores the heap property by performing rotations when a child has higher priority than parent.

This function checks if the specified child violates the heap property (child priority > parent priority) and performs the appropriate rotation to restore it. This maintains the treap invariant.

Arguments

node - The node to check and potentially rotate
check_left - Whether to check the left child (true) or right child (false)

Returns

The root of the subtree after any necessary rotation

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::restore_heap_property

fn restore_heap_property(node: Box<CMTNode>, check_left: bool) -> Box<CMTNode>

search

Searches for a key in the Cartesian Merkle Tree.

Performs a standard BST search using key comparisons to navigate the tree. Time complexity is O(log n) on average due to the randomized heap property.

Returns

true if the key exists in the tree, false otherwise

Examples

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.search(42));
assert!(!tree.search(100));

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::search

fn search(self: @CMTree, key: felt252) -> bool

search_node

Internal recursive function for searching a key starting from a given node.

Performs BST traversal by comparing keys and recursively searching the appropriate subtree.

Arguments

node - The current node being examined
key - The key to search for

Returns

true if the key is found in the subtree, false otherwise

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::search_node

fn search_node(node: @Box<CMTNode>, key: felt252) -> bool

get_root_hash

Returns the Merkle hash of the tree’s root node.

The root hash serves as a cryptographic commitment to the entire tree structure and contents, enabling efficient verification of tree state and proof validation.

Returns

0 for empty trees
The Merkle hash of the root node for non-empty trees

Examples

let tree = CMTreeTrait::new();
assert_eq!(tree.get_root_hash(), 0);

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.get_root_hash() != 0);

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::get_root_hash

fn get_root_hash(self: @CMTree) -> felt252

remove

Removes a key from the Cartesian Merkle Tree.

Removal maintains all tree properties through a rotation-based approach:

Locate the target node using BST search
For nodes with children, rotate them toward a leaf position
Remove the node once it becomes a leaf
Update Merkle hashes along the removal path

Returns

true if the key was found and removed, false if the key wasn’t in the tree

Examples

let mut tree = CMTreeTrait::new();
tree.insert(42);
assert!(tree.remove(42));
assert!(!tree.search(42));
assert!(!tree.remove(100)); // Non-existent key

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::remove

fn remove(ref self: CMTree, key: felt252) -> bool

remove_node

Internal recursive function for removing a node while maintaining tree properties.

This function handles the BST deletion process, including special handling for nodes with two children by delegating to rotation-based removal.

Arguments

node - The current node being examined
key - The key to remove

Returns

A tuple containing:

The new root of this subtree (None if subtree becomes empty)
Whether the key was found and removed

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::remove_node

fn remove_node(node: Box<CMTNode>, key: felt252) -> (Option<Box<CMTNode>>, bool)

rotate_to_leaf_and_remove

Rotates a node with two children toward a leaf position, then removes it.

This function implements the treap deletion strategy for nodes with both children: repeatedly rotate the node down the tree based on child priorities until it becomes a leaf, then remove it. This maintains both BST and heap properties.

Arguments

node - The node to rotate and remove
key - The key being removed (for verification)

Returns

The new root of this subtree after rotation and removal

Fully qualified path: cartesian_merkle_tree::library::tree::CMTreeTrait::rotate_to_leaf_and_remove

fn rotate_to_leaf_and_remove(node: Box<CMTNode>, key: felt252) -> Option<Box<CMTNode>>

Keyboard shortcuts

cartesian_merkle_tree - Cairo