# Binary search tree (Haskell)

### From LiteratePrograms

**Other implementations**: C | C++ |**Haskell**| Java | Scheme | Standard ML

A Binary Search Tree is a tree, where each node has two children, and the children are related in a manner which allows them to be compared. The generic example is that all items to the left of a given node are less than that node, and all items to the right are greater. How equality is treated is ambiguous, and depends on the specific application of the tree.

This file contains basic Binary Search Tree functions (including the data type definition) which operate unrelated to the actual contents of the BST.

<<BinarySearch.hs>>=-- This file contains functions to work with Binary Search Trees unrelated to their contents.moduleBinarySearchwhere-- The data type definition. A tree can consist of either a Tip or a node with a value and two tree.dataTree a = Tip | Node a(Tree a)(Tree a)deriving(Show,Eq)-- Returns a leaf node, makes writing leafs easier leaf x = Node x Tip Tip -- Some examples of structure in code t1 = Node 10 Tip Tip t2 = Node 17(Node 12(Node 5 Tip(leaf 8))(leaf 15))(Node 115(Node 32(leaf 30)(Node 46 Tip(leaf 57)))(leaf 163))-- The size of the tree - the number of items in the tree size Tip = 0 size(Node _ tl tr)= 1 + size tl + size tr -- Converts a tree into a list. This list, if converted back into a tree, will return the same tree treeToList Tip =[]treeToList(Node x xl xr)= x : treeToList xl ++ treeToList xr -- Converts a tree into a sorted list. This list will not convert back into the same tree. treeToListOrd Tip =[]treeToListOrd(Node x xl xr)= treeToListOrd xl ++ x : treeToListOrd xr -- Visually outputs a tree (sideways) by indenting each next node and additional tab in, outputs the right side, then the node, then the left side pict t = putStr(pic "" t)wherepic ind Tip = ind ++ "." pic ind(Node x tl tr)= pic('\t':ind)tr ++ "\n" ++ ind ++ show x ++ "\n" ++ pic('\t':ind)tl ++ "\n" -- Finds farthest left item. In a BST this is the smallest value farLft(Node x Tip _)= x farLft(Node x xl _)= farLft xl -- Finds farthest right item. In a BST this is the largest value farRt(Node x _ Tip)= x farRt(Node x _ xr)= farRt xr -- Mirrors a tree, so every right and left node switch mirror Tip = Tip mirror(Node x xl xr)= Node x(mirror xr)(mirror xl)

This file contains functions which work with BSTs of naturally comparable items, such as numbers and strings. The comparison function is (<=)

<<BinarySearchNum.hs>>=-- This file contains functions to work with Numeric (and string, since Haskell can use the < operator on strings) Binary Search Trees.moduleBinarySearchNumwhereimportBinarySearch -- Insert into a tree -- The third parameter is a comparator function, if the contents of the tree are not numbers or strings, you can pass a different function to this third parameter to properly define how to compare, and therefore sort, the tree. insert a Tip = leaf a insert a(Node x xl xr)| a <= x = Node x(insert a xl)xr | otherwise = Node x xl(insert a xr)-- Converts a list to a tree, using either comparator function f, or the natural (<=) function listToTree = foldl(flip insert)Tip -- Tree Sort - takes a list, and sorts it by converting to a tree and then back to a list tsort = treeToListOrd . listToTree -- Adds up all items in a numerical Binary Tree sumt Tip = 0 sumt(Node x xl xr)= x + sumt xl + sumt xr -- Finds smalles item in a tree (not necessarily ordered) -- This function does not deal with a tree which is just a tip mint(Node x Tip Tip)= x mint(Node x xl Tip)= min x(mint xl)mint(Node x Tip xr)= min x(mint xr)mint(Node x xl xr)= min x(min(mint xl)(mint xr))-- Finds largest item in a tree (not necessarily ordered) -- This function does not deal with a tree which is just a tip maxt(Node x Tip Tip)= x maxt(Node x xl Tip)= max x(maxt xl)maxt(Node x Tip xr)= max x(maxt xr)maxt(Node x xl xr)= max x(max(maxt xl)(maxt xr))-- Finds height of tree height Tip = 0 height(Node _ xl xr)= 1 + max(height xl)(height xr)

This file contains functions which work with any binary search tree. The comparison function must be specified via the f parameter.

<<BinarySearchAll.hs>>=-- This file contains functions to work with any kind of Binary Search Tree - the comparison operator is passed as needed by the f parametermoduleBinarySearchAllwhereimportBinarySearch -- Insert into a tree -- The third parameter is a comparator function, if the contents of the tree are not numbers or strings, you can pass a different function to this third parameter to properly define how to compare, and therefore sort, the tree. insert a Tip _ = leaf a insert a(Node x xl xr)f | f a x = Node x(insert a xl f)xr | otherwise = Node x xl(insert a xr f)-- Converts a list to a tree, using either comparator function f, or the natural (<=) function listToTree ls f = foldl(\tre x -> insert x tre f)Tip ls -- Tree Sort - takes a list, and sorts it by converting to a tree and then back to a list tsort ls f = treeToListOrd(listToTree ls f)-- Adds up all items in a numerical Binary Tree -- h is a function which combines two items - default would be (+) sumt Tip h = 0 sumt(Node x xl xr)h = h(h x(sumt xl h))(sumt xr h)-- Finds smalles item in a tree (not necessarily ordered) using comparator f -- This function does not deal with a tree which is just a tip mint(Node x Tip Tip)f = x mint(Node x xl Tip)f | f x xlSm = x | otherwise = xlSmwherexlSm = mint xl f mint(Node x Tip xr)f | f x xrSm = x | otherwise = xrSmwherexrSm = mint xr f mint(Node x xl xr)f | f x xlSm && f x xrSm = x | f xlSm xrSm = xlSm | otherwise = xrSmwherexlSm = mint xl f xrSm = mint xr f -- Finds largest item in a tree (not necessarily ordered) using comparator f -- flips the parameters of f in order to find the largest using a smaller-than comparator -- This function does not deal with a tree which is just a tip maxt(Node x Tip Tip)f = x maxt(Node x xl Tip)f |(flip f)x xlSm = x | otherwise = xlSmwherexlSm = maxt xl f maxt(Node x Tip xr)f |(flip f)x xrSm = x | otherwise = xrSmwherexrSm = maxt xr f maxt(Node x xl xr)f |(flip f)x xlSm &&(flip f)x xrSm = x |(flip f)xlSm xrSm = xlSm | otherwise = xrSmwherexlSm = maxt xl f xrSm = maxt xr f -- Finds height of tree height Tip = 0 height(Node _ xl xr)= 1 + max(height xl)(height xr)