Binary Search Tree Implementation in Haskell

Question

I am working on an assignment in Haskell and had a question about the implementation of a binary search tree that I was given. The book I am using to learn Haskell uses the following implementation for a binary tree:

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

This definition makes a lot of sense to me as it shows that a tree is either an empty tree or an element that contains a value and two trees. However, the implementation of a binary search tree that I was given in my assignment is as followed:

data BT a b
  = Leaf
  | Branch (BT a b) a b (BT a b)
  deriving (Eq, Show)

In this implementation does each branch represent a pair of nodes that either is made up of more branches or leaves? Also what advantages/disadvantages would this implementation have over the traditional one? Any help would be greatly appreciated!

In this definition a BT is either a Leaf (not containing any values), or a Branch that contains two such BT subtrees, and an a and a b value. — Willem Van Onsem
It's a slightly odd definition, though. I would think data BT a = Leaf | Branch (BT a) a a (BT a) would be more likely. — chepner
Also, a B-Tree usually (necessarily?) allows n+1 children for a node with n values. — chepner
I suspect that a is the search key and b is the actual data. That would suggest functions like insert :: Ord a => a -> b -> BT a b -> BT a b and find :: Ord a => a -> BT a b -> Maybe b. — chepner

K. A. Buhr K. A. Buhr · Accepted Answer · 2019-11-06T16:47:54

I think @chepner has nailed it. This is intended to be a binary tree that contains both keys (of type a) and values (of type b).

Think of it this way. If you started with the definition:

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show)

and wanted to store a key/value pair at each node, you could make type a into a pair. The following isn't a legal Haskell data type because you can't use (k,v) on the left-hand side, but it illustrates what the valid type Tree (k,v) would look like:

data Tree (k,v) = EmptyTree | Node (k,v) (Tree (k,v)) (Tree (k,v))

You could make this a valid Haskell type definition by making k and v proper arguments to the type constructor Tree, i.e., replacing Tree (k,v) with Tree k v everywhere:

data Tree k v = EmptyTree | Node (k,v) (Tree k v) (Tree k v)

Now, as a general rule, if you have a data type with a constructor that includes a pair:

data SomeType a b = Pair1 (a,b)

it's more or less equivalent to:

data SomeOtherType a b = Pair2 a b

After all, you can write Pair1 (2,"hello") or Pair2 2 "hello", and they both store the same data.

Given this, we can rewrite the definition of Tree k v as:

data Tree k v = EmptyTree | Node k v (Tree k v) (Tree k v)

Now, the four fields in the Node constructor don't have to be in that order; we could reorder them and still store exactly the same information, so let's move the "left branch" field to the front:

data Tree k v = EmptyTree | Node (Tree k v) k v (Tree k v)

Now this exactly matches the structure of your BT type:

data BT a b = Leaf | Branch (BT a b) a b (BT a b)

Binary Search Tree Implementation in Haskell

1 Answers