BatAvlTree (u.c54fcfcc5a7ff0c09beed4cdb8d1b2da.batteries.3.9.0.doc.batteries.unthreaded.BatAvlTree)

Sourcetype +'a tree

Sourceval empty : 'a tree

Sourceval is_empty : 'a tree -> bool

Sourceval make_tree : 'a tree -> 'a -> 'a tree -> 'a tree

Sourceval 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.

Sourceval height : 'a tree -> int

Sourceval left_branch : 'a tree -> 'a tree

raises Not_found
if the tree is empty

Sourceval right_branch : 'a tree -> 'a tree

raises Not_found
if the tree is empty

Sourceval root : 'a tree -> 'a

raises Not_found
if the tree is empty

Sourceval singleton_tree : 'a -> 'a tree

Sourceval split_leftmost : 'a tree -> 'a * 'a tree

Sourceval split_rightmost : 'a tree -> 'a * 'a tree

Sourceval concat : 'a tree -> 'a tree -> 'a tree

Sourceval iter : ('a -> unit) -> 'a tree -> unit

Sourceval fold : ('a -> 'b -> 'b) -> 'a tree -> 'b -> 'b

Sourceval enum : 'a tree -> 'a BatEnum.t

Sourceval 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.

since 2.3.0