|
|
| 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 non-leaf 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
| |
| run-time"
| |
|
| |
| [http://okmij.org/ftp/Haskell/types.html#stanamic-AVL Polymorphic stanamically balanced AVL trees]
| |
|
| |
| [[Category:Idioms]]
| |