Exercise 3.9 solution

[Mark]

Hi All,

Here's the Haskell code for the solution to exercise 3.9 I was
rambling about during the meeting. The basic idea is to take a sorted
(and finite) list of elements and build a balanced tree from it in a
single pass, with all nodes colored black except for the nodes
farthest from the root, which are colored red.

--
-- Determine the height of a balanced binary tree containing n
elements.
--
treeHeight :: Int -> Int
treeHeight n
| n == 0 = 0
| otherwise = 1 + (treeHeight (n `div` 2))

--
-- Construct a subtree with len elements, having height h, from a
sorted list
-- of elements x. Return the tree and the unconsumed items in the
list x.
--
-- The height might actually be h-1 if there are one too few
elements; this
-- case is handled.
--
makeSub :: Int -> Int -> [a] -> (RedBlackSet a, [a])
makeSub len h x
| len == 0 = (E, x)
| len == 1 = ((T (if h == 1 then R else B) E (head x)
E), tail x)
| otherwise = ((T B s1 middle s2), x'')
where
(s1,(middle:x')) = makeSub lenLeft (h-1) x
(s2,x'') = makeSub lenRight (h-1) x' -- OK if there's one
too few elements for this height
lenRight = (len-1) `div` 2 -- lenRight == lenLeft, or
lenRight == lenLeft - 1
lenLeft = (len-1) - lenRight

--
-- Construct a RedBlackSet from a sorted list of elements in O(n)
time, n = length of list.
-- The tree is constructed from the "bottom up". All paths from the
root node to a leaf
-- differ in length by 1 at most. All leaf nodes at maximum
distance from the root are
-- Red, the rest are Black.
--
fromSortedList :: [a] -> RedBlackSet a
fromSortedList x = fst $ makeSub len (treeHeight len) x
where len = length x