An AVL tree is a balanced binary search tree. The heights of each subtree differ by at most one. On each insertion or deletion, the tree shifts around its nodes through a series of rotations to become balanced. A balanced tree ensures the height is minimized, which guarantees lookups and insertions to be within O(log n) time. In this recipe, we will use an AVL tree package directly, but self-balancing trees also exist within the Data.Set and Data.Map implementations.
Import the relevant AVL tree packages:
import Data.Tree.AVL import Data.COrdering
Set up an AVL tree from a list of values and read the minimum and maximum values from it:
main = do let avl = asTree fstCC [4,2,1,5,3,6] let min = tryReadL avl let max = tryReadR avl print min print max
The minimum and maximum values are printed out as follows:
$ runhaskell Main.hs Just 1 Just 6