Safe Haskell	Safe-Inferred
Language	Haskell98

Data.Tree.Splay

Synopsis

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

data Ord k => SplayTree k v Source #

Instances

Instances details

(Ord k, Eq v) => Eq (SplayTree k v) Source #
Instance details Defined in Data.Tree.Splay Methods (==) :: SplayTree k v -> SplayTree k v -> Bool # (/=) :: SplayTree k v -> SplayTree k v -> Bool #
(Ord k, Ord v) => Ord (SplayTree k v) Source #
Instance details Defined in Data.Tree.Splay Methods compare :: SplayTree k v -> SplayTree k v -> Ordering # (<) :: SplayTree k v -> SplayTree k v -> Bool # (<=) :: SplayTree k v -> SplayTree k v -> Bool # (>) :: SplayTree k v -> SplayTree k v -> Bool # (>=) :: SplayTree k v -> SplayTree k v -> Bool # max :: SplayTree k v -> SplayTree k v -> SplayTree k v # min :: SplayTree k v -> SplayTree k v -> 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 v Source #

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

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

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

empty :: Ord k => SplayTree k v Source #

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

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

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

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

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

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

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 v Source #

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 Source #

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) Source #

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

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

Splays the i^{th} element in BST order

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

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