- data Ord k => SplayTree k v
- head :: Ord k => SplayTree k v -> (k, v)
- tail :: Ord k => SplayTree k v -> SplayTree k v
- singleton :: Ord k => (k, v) -> SplayTree k v
- empty :: Ord k => SplayTree k v
- null :: Ord k => SplayTree k v -> Bool
- fromList :: Ord k => [(k, v)] -> SplayTree k v
- fromAscList :: Ord k => [(k, v)] -> SplayTree k v
- toList :: Ord k => SplayTree k v -> [(k, v)]
- toAscList :: Ord k => SplayTree k v -> [(k, v)]
- insert :: Ord k => k -> v -> SplayTree k v -> SplayTree k v
- lookup :: Ord k => k -> SplayTree k v -> SplayTree k v
- (!!) :: Ord k => SplayTree k v -> Int -> (k, v)
- splay :: Ord k => SplayTree k v -> Int -> SplayTree k v
- size :: Ord k => SplayTree k v -> Int
- delete :: Ord k => k -> SplayTree k v -> SplayTree k v

# Documentation

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.

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 => k -> v -> SplayTree 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. This function is unsatisfying.

lookup :: Ord k => k -> SplayTree k v -> 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.