Haskell Data Analysis Cookbook

Using a self-balancing tree

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.

Getting ready

We will be using the AvlTree package to use Data.Tree.AVL:

$ cabal install AvlTree

How to do it...

1. Import the relevant AVL tree packages:

   import Data.Tree.AVL
   import Data.COrdering

2. Set up an AVL tree from a list of values and read the minimum ...