TreeStructures-0.0.1: Tree structures

Data.Tree.Splay

Synopsis

# Documentation

data Ord k => SplayTree k v Source

Instances

 (Eq v, Ord k) => Eq (SplayTree k v) (Ord k, Ord v) => Ord (SplayTree k v)

head :: Ord k => SplayTree k v -> (k, v)Source

O(1). `head` returns the key-value pair of the root.

tail :: Ord k => SplayTree k v -> SplayTree k vSource

Amortized O(lg n). `tail` removes the root of the tree and merges its subtrees

singleton :: Ord k => (k, v) -> SplayTree k vSource

O(1). `singleton` constructs a splay tree containing one element.

empty :: Ord k => SplayTree k vSource

O(1). `empty` constructs an empty splay tree.

null :: Ord k => SplayTree k v -> BoolSource

O(1). `null` returns true if a splay tree is empty.

fromList :: Ord k => [(k, v)] -> SplayTree k vSource

O(n lg n). Constructs a splay tree from an unsorted list of key-value pairs.

fromAscList :: Ord k => [(k, v)] -> SplayTree k vSource

O(n lg n). Constructs a splay tree from a list of key-value pairs sorted in ascending order.

toList :: Ord k => SplayTree k v -> [(k, v)]Source

O(n lg n). Converts a splay tree into a list of key-value pairs with no constraint on ordering.

toAscList :: Ord k => SplayTree k v -> [(k, v)]Source

O(n lg n). `toAscList` converts a splay tree to a list of key-value pairs sorted in ascending order.

insert :: Ord k => SplayTree k v -> (k, v) -> SplayTree k vSource

Amortized O(lg n). Given a splay tree and a key-value pair, `insert` places the the pair into the tree in BST order.

lookup :: Ord k => SplayTree k v -> k -> SplayTree k vSource

Amortized O(lg n). Given a splay tree and a key, `lookup` attempts to find a node with the specified key and splays this node to the root. If the key is not found, the nearest node is brought to the root of the tree.