An empty constructor and a constructor containing a label and two subtrees give a polymorphic algebraic data type:
data STree a = Empty | Node (STree a) a (STree a)
deriving (Eq, Show)The binary search tree invariant is at each
Node left x right, together with the same invariant recursively in both subtrees. Labels are distinct because the representation is of a set. The declaration itself needs no ordering constraint; operations that compare labels require Ord a in their type signatures.Follow the unique branch in which the new key could belong. At an equal key, keep the existing node so that duplicate insertion does not change the represented set:
insert :: Ord a => a -> STree a -> STree a
insert y Empty = Node Empty y Empty
insert y (Node left x right) =
case compare y x of
LT -> Node (insert y left) x right
EQ -> Node left x right
GT -> Node left x (insert y right)The Haskell Ord class supplies the three-way comparison. Each visited nonempty node costs one such comparison; rebuilding a node preserves all untouched subtrees. The inserted key satisfies every comparison along its search path, so it obeys both the local and ancestor binary search tree inequalities.
For height of a binary tree , the worst search costs when it reaches the bottom. With existing nodes, a chain can require comparisons, giving a worst case of . Under the standard random-insertion model, distinct keys arrive in a uniformly random order and the expected path length is . Thus the usual average-case answer is for growing , but this expectation needs the stated distribution: an arbitrary unbalanced binary search tree has no logarithmic guarantee.
A tree fold replaces
Empty by a seed and Node by a combining function. The combining function receives the already folded left subtree, the node's label and the already folded right subtree:foldSTree :: (b -> a -> b -> b) -> b -> STree a -> b
foldSTree combine empty Empty = empty
foldSTree combine empty (Node left x right) =
combine (foldSTree combine empty left)
x
(foldSTree combine empty right)Its polymorphic type signature isThe result type need not be the label type: it may be a list, a number or another structure. No ordering constraint is needed because this tree fold follows constructors without comparing labels.
Use the empty list for an empty subtree, and join the left result, the current label and the right result:
flatten :: STree a -> [a]
flatten = foldSTree (\left x right -> left ++ (x : right)) []Thus . This is an inorder traversal. By structural induction, each subtree produces its labels in order; the binary search tree invariant places every left label below and every right label above , proving that the whole result is increasing. The definition works for any binary-tree shape, although its result is sorted only when the ordering invariant holds. Repeated list concatenation can give quadratic cost on a left chain; the question asks for a tree fold definition, rather than an optimal traversal implementation.
An empty binary search tree has zero nodes; a nonempty node contributes one in addition to the sizes of its two subtrees:
size :: STree a -> Integer
size = foldSTree (\left _ right -> 1 + left + right) 0The answer is . The tree fold visits every node once, so this takes arithmetic operations for nodes.
Count the number of nonempty levels on the longest root-to-leaf branch, taking the empty binary search tree to have depth zero:
depth :: STree a -> Integer
depth = foldSTree (\left _ right -> 1 + max left right) 0Thus . A singleton has depth one under this convention. If height of a binary tree is instead counted in edges, subtract one for a nonempty tree. The complete tree fold takes operations.
Search as for insertion. Removing a node with at most one nonempty child leaves that child in its place. With two children, use the smallest key in the right subtree as the replacement and remove that occurrence from the right subtree:
delete :: Ord a => a -> STree a -> STree a
delete _ Empty = Empty
delete y (Node left x right) =
case compare y x of
LT -> Node (delete y left) x right
GT -> Node left x (delete y right)
EQ -> join left right
where
-- Join two search trees with every left key below every right key.
join :: STree a -> STree a -> STree a
join Empty r = r
join l Empty = l
join l r = let (smallest, rest) = takeMin r
in Node l smallest rest
-- Precondition: the input tree is nonempty.
takeMin :: STree a -> (a, STree a)
takeMin Empty = error "takeMin: empty tree"
takeMin (Node Empty x right) = (x, right)
takeMin (Node left x right) =
let (smallest, rest) = takeMin left
in (smallest, Node rest x right)The call to
takeMin occurs only after both empty cases have been excluded. Its structural recursion follows left children until it reaches the minimum label and rebuilds the path with that occurrence removed.For a matching label and successor , all left labels are below , while every label remaining on the right is strictly above . Thus replacing by preserves the binary search tree invariant. Every other branch preserves the invariant by structural induction. The resulting set is exactlyWhether the key is absent or present, untouched subtrees can be shared. The search path followed by the successor path uses time and fresh nodes for original height of a binary tree , so the worst case is without balancing. This is persistent binary search tree deletion: the original value remains available.
Articles by others on the same topic
There are currently no matching articles.