Choose the middle element as the root:The input is a finite, strictly ascending list, as required for distinct elements of a set. The two child lengths differ by at most one. Applying the same argument recursively gives a balanced binary tree of logarithmic height. All values on each side retain their original order, proving the binary search tree property. With linked lists, the repeated splitting gives time; it does not repeatedly insert values into a skewed tree.
build :: [a] -> Tree a
build [] = Empty
build xs = Tree (build ls) x (build rs)
where
(ls,x:rs) = splitAt (length xs `div` 2) xs Articles by others on the same topic
There are currently no matching articles.