AVL based Elm Dict

An implementation of easy to understand AVL algorithm. The basic idea is to keep both sub-trees of a node almost the same height. Almost means that heights difference must be not more that 1. As soon as this rule is violated rebalancing happens. It provides more strictly balance than red-black-tree implementation.

elm install owanturist/elm-avl-dict

Example

import AVL.Dict as Dict exposing (Comparator, Dict)

type ID
    = ID Int

idComparator : Comparator ID
idComparator (ID x) (ID y) =
    compare x y

users : Dict ID User
users =
    Dict.fromListWith idComparator
        [ ( "Alice", User (ID 0) "Alice" 28 1.65 )
        , ( "Bob", User (ID 1) "Bob" 19 1.82 )
        , ( "Chuck", User (ID 2) "Chuck" 33 1.75 )
        ]

alice : Maybe User
alice =
    Dict.get (ID 0) users

type alias User =
    { id : ID
    , name : String
    , age : Int
    , height : Float
    }

Performance

Time complexity of basic operations is the same (O(log n)) as in Core.Dict except constant time O(1) for AVL.Dict.size operation. It is achieved by tracking the size of a tree in the single place so it spends constant additional space as well.