Hi! My personal favourite is a neat (read: efficient and mostly write-only) way to balance AVL trees which I learned at a Haskell course on my university.
This is the first implementation which comes to one's mind when playing with Trees: > data Tree a = L | N (T a) a (T a) Balanceness is defined in terms of a tree's height: > height :: T a -> Int > height L = 0 > height (N l a r) = 1 + max (height l) (height r) This gets the difference of the subtrees' heights: (Note that it could return a negative value, too.) > skew :: T a -> Int > skew L = 0 > skew (N l a r) = (height l)-(height r) Our tree is balanced iff the skew is at most 1 for every subtree: > balanced :: T a -> Bool > balanced L = True > balanced t@(N l a r) > | abs (skew t) <= 1 = balanced l && balanced r > | otherwise = False Now the interesting part. What if a tree is not balanced? Here do rotations come into the picture. There are several types of rotations which usually need some attention and are awkward to code in an imperative language. Of course one can do it in a functional language almost as awkward as in an imperative one, but the point is to use pattern matching like shown below: > rightRot :: T a -> T a > rightRot (N (N x a y) b z) = N x a (N y b z) > rightRot a = a This is one of the simplest cases which makes it relatively easy to read. The thing is that this is a really fast implementation achieved at almost no effort. Also, it doesn't get harder than this: > leftRightRot :: T a -> T a > leftRightRot (N (N x a (N y b z)) c v) = N (N x a y) b (N z c v) > leftRightRot a = a which can also be written as: > leftRightRot (N x a y) = rightRot (N (leftRot x) a y) So I think this was the moment when I made up my mind to commit myself to Haskell & FP. Cheers, Zsolt
signature.asc
Description: PGP signature
_______________________________________________ Haskell mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell
