

Line 1: 
Line 1: 
−  "We describe a datatype of polymorphic balanced binary trees: AVL trees.
 
−  The trees are polymorphic: the values in different nodes may have
 
−  different type. The trees are balanced: for each nonleaf node, the
 
−  heights of its two children can differ at most by one. Here, by
 
−  definition the height of a node is 1 + max of the heights of its
 
−  children. A leaf node has the height of 0.
 
   
−  The main feature of the present approach is a blended static and dynamic
 
−  enforcement of the balancing constraint. The function make_node
 
−  verifies the balancing constraint at compile time  if it can. If the
 
−  static check is not possible, the function delays the check till the
 
−  runtime"
 
− 
 
−  [http://okmij.org/ftp/Haskell/types.html#stanamicAVL Polymorphic stanamically balanced AVL trees]
 
− 
 
−  [[Category:Idioms]]
 