AVL Trees are binary search trees with a balance condition. The balance condition ensures that the height of the tree is bounded.
The two conditions satisfied by an AVL tree are:
order property: the value stored at every node, is larger than any value stored in the left subtree, and is smaller than any value stored in the right subtree.
balance property: at every node the difference in the height of the right and the left subtrees is at most 1.
Let us implement Splay Trees in Julia which is, relatively new and popular, dynamically typed language with multiple dispatch.
We model a node in the splay tree as an abstract data type. Each node contains a single integer data value and two references to the left and the right subtrees. The subtrees can be empty, as in the case of leaf nodes, and we model this by using the Nil type.