RedBlackTree

ferum_std::red_black_tree

Ferum's implementation of a Red Black Tree. A red black tree is a self balancing binary tree which performs rotations on tree manipulations to maintain a tree height of log(k), where k is the number of keys in the tree. Values with duplicate keys can be inserted into the tree; each value will stored in a linked list on each tree node. When a node no longer has any values, the node is removed (this is referred to as key deletion). The tree only supports u128 keys because (as of writing) move has no way to define comparators for generic types.

The tree supports the following operations with the given time complexities:

Operation	Worst Case Time Complexity	Amortized Time Complexity
Deletion of value	O(1)	O(1)
Deletion of key	O(log(k))	O(1)
Insertion of value with new key	O(log(k))	O(log(k))
Insertion of value with existing key	O(1)	O(1)
Retrieval of min/max key	O(1)	O(1)

Quick Example

use ferum_std::red_black_tree::{Self, Tree};

// Create a tree with u128 values.
let tree = red_black_tree::new<u128>();

// Insert
red_black_tree::insert(&mut tree, 100, 50);
red_black_tree::insert(&mut tree, 100, 40);
red_black_tree::insert(&mut tree, 120, 10);
red_black_tree::insert(&mut tree, 90, 5);

// Get values.
let firstValue = red_black_tree::first_value_at(&tree, 100);
let allValue = red_black_tree::values_at(&tree, 100);

// Get min/max.
let min = red_black_tree::min_key(&tree);
let max = red_black_tree::max_key(&tree);

// Get tree metadata.
let keyCount = red_black_tree::key_count(&tree);
let valueCount = red_black_tree::value_count(&tree);

// Delete values and keys.
red_black_tree::delete_value(&mut tree, 100, 40);
red_black_tree::delete_key(&mut tree, 90);

Struct TreePosition

Used for traversal the tree in various directions.

struct TreePosition<V: copy, drop, store> has copy, drop

Constants

KEY_NOT_FOUND

Thrown when trying to perform an operation for a specific key but the key is not set.

const KEY_NOT_FOUND: u64 = 1;

VALUE_NOT_FOUND

Thrown when attempting to delete a value that doesn't exist.

const VALUE_NOT_FOUND: u64 = 2;

EXPECTING_KEY_TO_BE_SET

Expecting the key to be set i.e. asserting leftChildNodeKeyIsSet, before accessing leftChildNodeKey.

const EXPECTING_KEY_TO_BE_SET: u64 = 12;

INVALID_FIX_DOUBLE_RED_OPERATION

Thrown when trying fix a double red but the tree doesn't follow the correct structure.

const INVALID_FIX_DOUBLE_RED_OPERATION: u64 = 8;

INVALID_LEAF_NODE_HAS_LEFT_CHILD

Thrown when trying to perform an operation on a leaf node but that node has a left child.

const INVALID_LEAF_NODE_HAS_LEFT_CHILD: u64 = 9;

INVALID_LEAF_NODE_HAS_RIGHT_CHILD

Thrown when trying to perform an operation on a leaf node but that node has a right child.

const INVALID_LEAF_NODE_HAS_RIGHT_CHILD: u64 = 10;

INVALID_LEAF_NODE_NO_PARENT

Thrown when trying to perform an operation on a leaf node but that node has no parent.

const INVALID_LEAF_NODE_NO_PARENT: u64 = 11;

INVALID_NEXT_OPERATION

Thrown when trying to go to the next value or key in the iterator, when there isn't one!

const INVALID_NEXT_OPERATION: u64 = 13;

INVALID_OUTGOING_SWAP_EDGE_DIRECTION

Thrown when the edges being swapped doesn't define a valid edge direction.

const INVALID_OUTGOING_SWAP_EDGE_DIRECTION: u64 = 6;

INVALID_ROTATION_NODES

Thrown when trying to perform an invalid rotation on the tree.

const INVALID_ROTATION_NODES: u64 = 3;

ITERATION_DIRECTION_MAX

When using an iterator, encodes the direction towards the next maximum value i.e. reverse inorder traversal.

const ITERATION_DIRECTION_MAX: u8 = 1;

ITERATION_DIRECTION_MIN

When using an iterator, encodes the direction towards the next minimum value i.e. inorder traversal.

const ITERATION_DIRECTION_MIN: u8 = 0;

ONLY_LEAF_NODES_CAN_BE_ADDED

Thrown when trying to add a non leaf node to the tree.

const ONLY_LEAF_NODES_CAN_BE_ADDED: u64 = 7;

SUCCESSOR_FOR_LEAF_NODE

Thrown when trying to get the successor for a leaf node.

const SUCCESSOR_FOR_LEAF_NODE: u64 = 5;

TREE_IS_EMPTY

Thrown when trying to perform an operation on the tree that requires the tree to be non empty.

const TREE_IS_EMPTY: u64 = 0;

Functions

Function new

Creates a new tree.

public fun new<V: copy, drop, store>(): red_black_tree::Tree<V>

Function is_empty

Returns if the tree is empty.

public fun is_empty<V: copy, drop, store>(tree: &red_black_tree::Tree<V>): bool

Function contains_key

Returns true if the tree has at least one value with the given key.

public fun contains_key<V: copy, drop, store>(tree: &red_black_tree::Tree<V>, key: u128): bool

Function key_count

Returns how many keys are in the tree.

public fun key_count<V: copy, drop, store>(tree: &red_black_tree::Tree<V>): u128

Function value_count

Returns the total number of values in the tree.

public fun value_count<V: copy, drop, store>(tree: &red_black_tree::Tree<V>): u128

Function key_value_count

Returns the total number of values for the given key.

public fun key_value_count<V: copy, drop, store>(tree: &red_black_tree::Tree<V>, key: u128): u128

Function first_value_at

Returns the first value with the givem key.

public fun first_value_at<V: copy, drop, store>(tree: &red_black_tree::Tree<V>, key: u128): &V

Function values_at

Returns all the values with the given key.

public fun values_at<V: copy, drop, store>(tree: &red_black_tree::Tree<V>, key: u128): vector<V>

Function values_at_list

Returns all the values with the given key as a doubly linked list.

public fun values_at_list<V: copy, drop, store>(tree: &red_black_tree::Tree<V>, key: u128): &linked_list::LinkedList<V>

Function max_key

Returns the maximum key in the tree, if one exists.

public fun max_key<V: copy, drop, store>(tree: &red_black_tree::Tree<V>): u128

Function min_key

Returns the minimum key in the tree, if one exists.

public fun min_key<V: copy, drop, store>(tree: &red_black_tree::Tree<V>): u128

Function get_next_key

Returns the next key and updates position.

public fun get_next_key<V: copy, drop, store>(tree: &red_black_tree::Tree<V>, position: &mut red_black_tree::TreePosition<V>): u128