Data.Tree.Splay

Documentation

data Ord k => SplayTree k v

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)

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

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

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

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

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

empty :: Ord k => SplayTree k v

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

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

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

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

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

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

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)]

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)]

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 v

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 v

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.

(!!) :: Ord k => SplayTree k v -> Int -> (k, v)

Locates the i^{th} element in BST order without splaying it.

splay :: Ord k => SplayTree k v -> Int -> SplayTree k v

Splays the i^{th} element in BST order

size :: Ord k => SplayTree k v -> Int

delete :: Ord k => k -> SplayTree k v -> SplayTree k v