Data Structures

Let us implement in julia 0.6.0 a binary search tree to store integers. Each node is either of type Nil or of type bst, as declared below. Type Nil is used a null pointer. We use type union MayBe to hold either a Nil() or a bst. At the start the tree is empty so it is initialized to Nil(). Removing the type declaration from the data element should be sufficient to store datatypes for which a comparator is implemented.

In this post, we implement in Haskell, the augmenting path method to find a maximum matching in a bipartite graph. We use function composition and recursion mostly. We obtain a simple implementation of an algorithm to compute maximum matching in a bipartite graph. As a side affect of this exercise, you should know about algorithms to compute terminal objects, and fix points in a category. Only a basic familiarity with Haskell is assumed here.

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.