module BatAvlTree:sig
..end
Internals of ISet and IMap, usable as generic tree library
type +'a
tree
val empty : 'a tree
val is_empty : 'a tree -> bool
val make_tree : 'a tree -> 'a -> 'a tree -> 'a tree
val create : 'a tree -> 'a -> 'a tree -> 'a tree
create l v r
is similar to make_tree l v r
but performs no rebalancing;
in other words, you should use this only when you know that l
and r
are already balanced.
val height : 'a tree -> int
val left_branch : 'a tree -> 'a tree
Not_found
if the tree is emptyval right_branch : 'a tree -> 'a tree
Not_found
if the tree is emptyval root : 'a tree -> 'a
Not_found
if the tree is emptyval singleton_tree : 'a -> 'a tree
val split_leftmost : 'a tree -> 'a * 'a tree
val split_rightmost : 'a tree -> 'a * 'a tree
val concat : 'a tree -> 'a tree -> 'a tree
val iter : ('a -> unit) -> 'a tree -> unit
val fold : ('a -> 'b -> 'b) -> 'a tree -> 'b -> 'b
val enum : 'a tree -> 'a BatEnum.t
val check : 'a tree -> bool
Check that the tree is balanced according to the AVL tree rules. An AVL tree is balanced when for every node the height of the subnodes differs by at most 1.