Treaps in VB.NET

• Download source files - 25.4 Kb

Introduction

A Treap is an efficient general purpose data structure. It has the characteristics of both a binary search tree (see Figure 1) and a heap ordered priority queue (see Figure 2).

Since the efficiency of tree traversal is dependent on the tree's height, a balanced tree (in which the left and right subtrees of any node are of the same height) is much more efficient than an unbalanced one (see Figure 3).

A Treap is an ordered, binary search tree that balances its nodes using a key and a random number priority attribute (Figure 4). The nodes are first ordered so that every node's left subtree key has values less than the node's key, and every right subtree has values greater than the node's key. The nodes are then reordered by priority according to the minimum heap order (priority queue) property which implies that the priority value at the node is less than (or equal) to the priority value of both the left and right child subtrees (if they are not empty).

The result is a data structure that performs reasonably well. Because it's a balanced tree, a node is never more than about log n steps away.

Background

The Treap was devised by C. R. Aragon and R. Seidel and described in Randomized Search Trees (Algorithmica, 16(4/5):464-497, 1996). I discovered the Treap while looking for a more efficient data structure than the hash table provided by Java, several years ago. During my search, I found Stefan Nilsson's Treaps in Java article in Dr. Dobb's Journal (pp. 40-44, Vol. 267, July 1997) and adapted his Treap for my particular use. Stefan has an online article entitled Treaps in Java.

Recently, I needed a VB.NET implementation, so I converted my Java implementation to VB.NET. At some point, I'll produce a C# version.

Using the code

The project available for download includes a Test project that gives examples calling Treap. Extract the zip file into a directory of your choice. The zipped file will create its own directory called TreapVB.

The Treap project consists of four classes:

1. Treap: The main class that implements the Treap API and functionality.
2. TreapEnumerator: Returns the keys or data objects of the Treap in sorted order.
3. TreapException: Distinguishes Treap exceptions from .NET exceptions.
4. TreapNode: Encapsulates a node in the Treap; performs the rotations to balance the Treap.

After including the TreapVB.DLL as a Reference to the calling project, using the Treap is similar to using the .NET HashTable class.

To create a Treap, call the default constructor:

Dim treap As Treap = new Treap()

Like the HashTable, the Treap's Add method requires a key and data object passed as arguments.

Public Sub Add(ByRef key As IComparable, ByRef data As Object)

The key reference can be a standalone object or embedded within the data object. The Test project includes samples of both.

In order for the Treap to make the necessary key comparisons, the key object must implement the .NET IComparable interface.

Public Class MyKey
    Implements IComparable

    Private Dim intMyKey As Integer

    Public Sub New(ByVal key As Integer)
        intMyKey = key
    End Sub

    Public Overloads Function CompareTo(ByVal key As Object) As Integer _
        Implements IComparable.CompareTo

        If (intMyKey > (CType(key, MyKey)).intMyKey)
            return 1
        Else  _
        If (intMyKey < (CType(key, MyKey)).intMyKey)
            return -1
        Else _
            return 0
        End If
    End Function
End Class

Calling the GetData method passing a key object as an argument retrieves a data object from the Treap.

Public Function GetData(ByVal key As IComparable) As Object

Nodes are removed by calling the Remove method.

Public Sub Remove(ByVal key As IComparable)

Additionally, the Treap class contains several other methods that offer convenient functionality.

• GetMinKey(): Returns the minimum key value.
• GetMaxKey(): Returns the maximum key value.
• GetMinValue(): Returns the object having the minimum key value.
• GetMaxValue(): Returns the object having the maximum key value.
• GetEnumerator(): Returns a TreapEnumerator used to iterate through the Treap.
• Keys(): Returns a TreapEnumerator used to iterate through the Treap keys.
• Values(): Returns a TreapEnumerator used to iterate through the Treap data objects.
• RemoveMin(): Removes the node with the minimum key.
• RemoveMax(): Removes the node with the maximum key.

Partial Output from the Test Project

The sample project demonstrates various method calls to the Treap and displays the effect of the calls dumping the Treap's contents to the Console. Executing the sample project produces the following partial output:

Improvements

There's lots of room for improvement in performance, usability, and functionality. For example, no method exists to determine if a particular key is present in the Treap. This is needed, I think, and will probably be my first enhancement. Regardless, the source is included in the download for your use to modify as you see fit.

Also, the code makes use of recursion in several methods. You might choose to remove the recursive calls to increase performance. I sort of like recursion, but, of course, there're tradeoffs between speed and clarity for a recursive vs. an iterative implementation.

Points of Interest

For a C# implementation of the Treap, see: Treaps in C#.

The following link contains an excellent animation of a Treap: Randomized Binary Search Trees.