REVISED: Wednesday, January 24, 2024
Haskell Recursive Binary Search Tree.
I. DEFINITIONS
A. BINARY TREE
A binary tree is a data structure that has a single root node; each node in the tree is either a leaf or a branch. If it is a leaf, it holds a value; if it is a branch, it holds a value and a left child and a right child. Each of these children is another node.
B. COMPLETE BINARY TREE
A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
C. HEIGHT OF A BINARY TREE
The height of a binary tree is the length of a path from the root to the deepest node. For example, the height of a tree with a single node is 0; the height of a tree with three nodes, whose root has two children, is 1; and so on.
D. INTERNAL NODES
Internal nodes have a parent, a root node is not an internal node, and internal nodes have at least one child.
E. LEAF NODES
Leaf nodes have a parent, but no children.
F. PERFECT BINARY TREE
A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level.
To determine if a tree is perfect, iterate through the tree, noting its depth and counting the number of leaves, where a tree with one node has a depth of 1. If you have 2^(d-1) leaves then your tree is perfect.
By the definition of complete, a tree can be complete but not perfect, but because a perfect tree is a complete tree that has the entire deepest level filled, any tree that is perfect must be complete.
G. ROOT
A root is the topmost node in a tree. It is a kind of main node in the tree, because all other nodes can be reached from the root. Root has no parent. Root is the node, at which operations on the tree begin.
II. HASKELL RED-BLACK TREE AND AVL TREE
Defined below is a polymorphic Binary Tree of as which is either a Leaf which holds an a, or it is a Branch with a left child, which is a Binary Tree of as, a node value, which is an a, and a right child, which is also a Binary Tree of as.
Prelude> data Tree a = Leaf a | Branch (Tree a) a (Tree a)
data Tree a = Leaf a | Branch (Tree a) a (Tree a)
Prelude>
Prelude>
Tree is a type constructor; Branch and Leaf are data constructors. The above declaration defines the following types for Branch and Leaf:
Prelude> :type Branch
Branch :: Tree a -> a -> Tree a -> Tree a
Prelude>
Prelude> :type Leaf
Leaf :: a -> Tree a
Prelude>
Values are stored at each node, with smaller values to the left, greater to the right.
Using the typeclass concept the names of abstract types start with a lowercase letter, and names of concrete types start with an uppercase letter.
A. RED-BLACK TREE
Red-Black tree was invented in 1972 by Rudolf Bayer who called them symmetric binary B-trees.
Red-Black trees are binary search trees in which all nodes are assigned a color as an extra attribute, either red or black. The leaves are considered black.
A Red-Black tree must satisfy these four properties:
1. The root is black
2. All leaves are black.
3. Red nodes can only have black children.
4. All paths from a node to its leaves contain the same number of black nodes.
B. AVL TREE
The AVL tree is named after its inventors, Adelson-Velskii and Landis in 1962.
An AVL tree is a self-balancing binary search tree where the height of the two child subtrees of any node differ by at most one, otherwise known as height-balanced.
III. HASKELL RECURSIVE BINARY SEARCH TREE (BST)
Building a balanced binary tree from a list.
Use your text editor to save BalancedTree.hs shown below, to your working directory:
module BalancedTree where
data Tree a = Leaf
| Node Integer (Tree a) a (Tree a)
deriving (Show, Eq)
foldTree :: [a] -> Tree a
foldTree = foldr (\x tree -> insertInTree x tree) Leaf
insertInTree :: a -> Tree a -> Tree a
insertInTree x Leaf = Node 0 (Leaf) x (Leaf)
insertInTree x (Node n t1 val t2) = if h1 < h2
then Node (h2+1) (insertInTree x t1) val t2
else Node (h1+1) t1 val (insertInTree x t2)
where h1 = heightTree t1
h2 = heightTree t2
heightTree :: Tree a -> Integer
heightTree Leaf = 0
heightTree (Node n t1 val t2) = n
Load the above BalancedTree.hs file into GHCi:
Prelude> :load BalancedTree.hs
[1 of 1] Compiling Main ( BalancedTree.hs, interpreted )
Ok, modules loaded: Main.
Prelude>
Call the foldTree function, in GHCi:
Prelude> foldTree "ABCDEFGHIJ"
Node 3 (Node 2 (Node 0 Leaf 'B' Leaf) 'G' (Node 1 Leaf 'F' (Node 0 Leaf 'C' Leaf))) 'J' (Node 2 (Node 1 Leaf 'D' (Node 0 Leaf 'A' Leaf)) 'I' (Node 1 Leaf 'H' (Node 0 Leaf 'E' Leaf)))
Prelude>
IV. REFERENCES
Bird, R. (2015). Thinking Functionally with Haskell. Cambridge, England: Cambridge University Press.
Davie, A. (1992). Introduction to Functional Programming Systems Using Haskell. Cambridge, England: Cambridge University Press.
Goerzen, J. & O'Sullivan, B. & Stewart, D. (2008). Real World Haskell. Sebastopol, CA: O'Reilly Media, Inc.
Hutton, G. (2007). Programming in Haskell. New York: Cambridge University Press.
Lipovača, M. (2011). Learn You a Haskell for Great Good!: A Beginner's Guide. San Francisco, CA: No Starch Press, Inc.
Thompson, S. (2011). The Craft of Functional Programming. Edinburgh Gate, Harlow, England: Pearson Education Limited.
In this tutorial, you have received an introduction to the Haskell recursive binary tree.
