Copyright	(c) Highlander Paiva 2022
License	BSD-style (see the LICENSE file)
Maintainer	hvpaiva@icloud.com
Stability	experimental
Portability	portable
Safe Haskell	Safe-Inferred
Language	Haskell2010

Data.BTree

Contents

BTree type
Constructors
Operations
Traversals to list
Drawing

Description

The BTree type, and associated operations.

This module allows you to use a BTree to store a set of values, and to efficiently lookup values in the set. The BTree is a balanced tree, which means that the tree is more efficient than a conventional binary tree.

Most of BTree operations are performed in O(log n) time.

Synopsis

data BTree a
empty :: BTree a
singleton :: Ord a => a -> BTree a
fromList :: Ord a => [a] -> BTree a
insert :: forall a. Ord a => a -> BTree a -> BTree a
delete :: forall a. Ord a => a -> BTree a -> BTree a
search :: forall a. Ord a => a -> BTree a -> Maybe a
height :: forall a. BTree a -> Int
levels :: forall a. Ord a => BTree a -> [[a]]
preorder :: forall a. BTree a -> [a]
inorder :: forall a. BTree a -> [a]
postorder :: forall a. BTree a -> [a]
draw :: forall a. Show a => BTree a -> String

BTree type

data BTree a Source #

The BTree type represents a tree using the b-tree algorithm.

A BTree a is a self-balancing tree as its nodes are traversed in-order. The node is a set of elements pointing to its children, and a leaf has no children and nothing in itself.

This implementation uses a order 3 BTree, this means:

{one, two} elements per node and {two, three} subtrees.
A leaf contains nothing.
Every leaf is equidistant from the root.
Subtrees must have the same height.
Data are ordered left to right.

             4              <-- (3) root
         /      \
        2       6           <-- (2) internal nodes
       / \     / \
      1   3   5   7         <-- (1) internal nodes
     / \ / \ / \ / \
    .  ..  ..  ..   .       <-- (0) leafs

The complexity of the operations:

Algorithm	Medium Case	Worst Case
Search	O(log n)	O(log n)
Insert	O(log n)	O(log n)
Delete	O(log n)	O(log n)

Examples

Expand

A BTree Int may be represented as:

>>> let t = fromList [1,2,3,4,5,6,7]
>>> t
"(((. 1 .) 2 (. 3 .)) 4 ((. 5 .) 6 (. 7 .)))"

>>> let n = insert 8 t
>>> n
"(((. 1 .) 2 (. 3 .)) 4 ((. 5 .) 6 (. 7 . 8 .)))"

Since: 1.0.0

Instances

Instances details

Foldable BTree Source #
Instance details Defined in Data.BTree Methods fold :: Monoid m => BTree m -> m # foldMap :: Monoid m => (a -> m) -> BTree a -> m # foldMap' :: Monoid m => (a -> m) -> BTree a -> m # foldr :: (a -> b -> b) -> b -> BTree a -> b # foldr' :: (a -> b -> b) -> b -> BTree a -> b # foldl :: (b -> a -> b) -> b -> BTree a -> b # foldl' :: (b -> a -> b) -> b -> BTree a -> b # foldr1 :: (a -> a -> a) -> BTree a -> a # foldl1 :: (a -> a -> a) -> BTree a -> a # toList :: BTree a -> [a] # null :: BTree a -> Bool # length :: BTree a -> Int # elem :: Eq a => a -> BTree a -> Bool # maximum :: Ord a => BTree a -> a # minimum :: Ord a => BTree a -> a # sum :: Num a => BTree a -> a # product :: Num a => BTree a -> a #
Traversable BTree Source #	The default `Traversable` instance is implemented in a in-order traversal. `>>>` `let incOdd n = if odd n then Just $ n + 1 else Nothing``>>>` `traverse incOdd $ fromList [1,3,5,7,9]`Just ("((. 2 .) 4 (. 6 .) 8 (. 10 .))")
Instance details Defined in Data.BTree Methods traverse :: Applicative f => (a -> f b) -> BTree a -> f (BTree b) # sequenceA :: Applicative f => BTree (f a) -> f (BTree a) # mapM :: Monad m => (a -> m b) -> BTree a -> m (BTree b) # sequence :: Monad m => BTree (m a) -> m (BTree a) #
Functor BTree Source #
Instance details Defined in Data.BTree Methods fmap :: (a -> b) -> BTree a -> BTree b # (<$) :: a -> BTree b -> BTree a #
Show a => Show (BTree a) Source #
Instance details Defined in Data.BTree Methods showsPrec :: Int -> BTree a -> ShowS # show :: BTree a -> String # showList :: [BTree a] -> ShowS #

Constructors

empty :: BTree a Source #

A empty BTree. It consists of a single leaf.

It may be used to construct a new BTree by inserting elements into it.

>>> let t = empty
>>> t
"."

>>> let n = insert 1 t
>>> n
"(. 1 .)"

>>> let j = insert 2 empty
>>> j
"(. 2 .)"

Since: 1.0.0

singleton :: Ord a => a -> BTree a Source #

Creates a singleton BTree from a single element.

>>> let t = singleton 1
>>> t
"(. 1 .)"

Since: 1.0.0

fromList :: Ord a => [a] -> BTree a Source #

Creates a BTree from a list.

>>> let t = fromList [1,2,3,4,5,6,7]
>>> t
"(((. 1 .) 2 (. 3 .)) 4 ((. 5 .) 6 (. 7 .)))"

Since: 1.0.0

Operations

insert :: forall a. Ord a => a -> BTree a -> BTree a Source #

Inserts an element into a BTree.

Inserts the element into the BTree in inorder fashion.

Algorithm	Medium Case	Worst Case
Insert	O(log n)	O(log n)

>>> let t = insert 1 empty
>>> t
"(. 1 .)"

>>> let n = insert 2 t
>>> n
"(. 1 . 2 .)"

Since: 1.0.0

delete :: forall a. Ord a => a -> BTree a -> BTree a Source #

Delete an element from a BTree.

Algorithm	Medium Case	Worst Case
Delete	O(log n)	O(log n)

>>> let t = fromList [1,2,3,4,5,6,7]
>>> let n = delete 3 t
>>> n
"((. 1 . 2 .) 4 (. 5 .) 6 (. 7 .))"

Since: 1.0.0

search :: forall a. Ord a => a -> BTree a -> Maybe a Source #

Search an element in a BTree. It will return a Maybe.

Algorithm	Medium Case	Worst Case
Search	O(log n)	O(log n)

>>> let t = fromList [1,2,3,4,5]

>>> search 3 t
Just 3

>>> search 6 t
Nothing

Since: 1.0.0

height :: forall a. BTree a -> Int Source #

The height of the BTree.

Represents the number of levels in the BTree.

            4             <-- height 3
        /      \
       2       6          <-- height 2
      / \     / \
     1   3   5   7        <-- height 1
    / \ / \ / \ / \
   .  ..  ..  ..   .      <-- height 0

>>> height (fromList [1,2,3,4,5,6,7])
3

Since: 1.0.0

levels :: forall a. Ord a => BTree a -> [[a]] Source #

Return the BTree as a list of lists, grouped by hights.

It will start by the root level and then go down to the branches.

  a
 / \    => [[a], [b,c]]
b   c

>>> levels (fromList [1,2,3,4,5,6,7])
[[4],[2,6],[1,3,5,7]]

Since: 1.0.0

Traversals to list

preorder :: forall a. BTree a -> [a] Source #

Return the BTree as a list in a pre-order traversal.

The pre-order traversal runs through the elements of the BTree in the following order:

The root element.
The left subtree.
The right subtree.

A BTree of [1, 2, 3, 4, 5, 6, 7] is represented as:

            4
        /      \
       2       6
      / \     / \
     1   3   5   7
    / \ / \ / \ / \
   .  ..  ..  ..   .

>>> preorder (fromList [1,2,3,4,5,6,7])
[4,2,1,3,6,5,7]

Since: 1.0.0

inorder :: forall a. BTree a -> [a] Source #

Return the BTree as a list in a in-order traversal.

The in-order traversal runs through the elements of the BTree in the following order:

The left subtree.
The root element.
The right subtree.

Note: The in-order traversal is the default traversal for the BTree, and is used to return as list.

A BTree of [1, 2, 3, 4, 5, 6, 7] is represented as:

            4
        /      \
       2       6
      / \     / \
     1   3   5   7
    / \ / \ / \ / \
   .  ..  ..  ..   .

>>> inorder (fromList [1,2,3,4,5,6,7])
[1,2,3,4,5,6,7]

Since: 1.0.0

postorder :: forall a. BTree a -> [a] Source #

Return the BTree as a list in a post-order traversal.

The post-order traversal runs through the elements of the BTree in the following order:

The left subtree.
The right subtree.
The root element.

A BTree of [1, 2, 3, 4, 5, 6, 7] is represented as:

            4
        /      \
       2       6
      / \     / \
     1   3   5   7
    / \ / \ / \ / \
   .  ..  ..  ..   .

>>> postorder (fromList [1,2,3,4,5,6,7])
[1,3,2,5,7,6,4]

Since: 1.0.0

Drawing

draw :: forall a. Show a => BTree a -> String Source #

Draws the BTree.

The output is a string of the form:

Each Leaf is represented by a ' . '
Each Node is represented as (left, value, right) where left and right are the left and right subtrees.

So, the current list [1, 2, 3, 4, 5, 6, 7] will be represented as:

"(((. 1 .) 2 (. 3 .)) 4 ((. 5 .) 6 (. 7 .)))"

Which is an inline representation of the BTree.

Examples

Expand

>>> draw (fromList [1,2,3,4,5,6,7])
"(((. 1 .) 2 (. 3 .)) 4 ((. 5 .) 6 (. 7 .)))"

Since: 1.0.0