Module grove::trees::avl

Implementation of AVL trees. Balanced by keeping track of node ranks, this is a worst-case balancing Algorithm that has a small memory overhead per node.

Structs

AVLTree

An AVL tree. Balanced by keeping track of node ranks, this is a worst-case balancing Algorithm that has a small memory overhead per node.

AVLWalker

A walker struct for AVLTree.

Functions

concatenate_with_middle

Concatenates the trees together, in place, with a given value for the middle. Complexity: O(log n). More precisely, O(dr) where dr is the difference of ranks between the two trees.