1
2
3
4
5
6
7
8
| relabel::Tree -> Tree
relabel t = let (t', size) = re (t, size) in t'
re :: (Tree, Int) -> (Tree, Int)
re (Leaf x, s) = (Leaf (if x < s then (2*s) else x) , 1)
re (Node l x r, s) =
let (l', sl) = re (l,s)
(r', sr) = re (r, s)
in (Node l' (if x < s then (2*s) else x) r', (1+sr+sl)) |