Splay Tree

The SplayTree type is an implementation of Splay Tree in Julia. It is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. Operations such as search, insert and delete can be done in O(log n) amortized time, where n is the number of nodes in the SplayTree.

Examples:

julia> tree = SplayTree{Int}();

julia> for k in 1:2:20
           push!(tree, k)
       end

julia> haskey(tree, 3)
true

julia> tree[4]
7

julia> for k in 1:2:10
           delete!(tree, k)
       end

julia> haskey(tree, 5)
false