C# Treap implementation

Question

I recently developed a simple treap data structure in C#. In the future, I may have the class extend IDictionary. For now, I only expose a public accessor and a delete method.

 public TValue this[TKey key]
 {
 get { return Get(root, key).Value; }
 set { root = Set(root, new Node(key, value)); }
 }

The data structure is generic and maintains the key-value pairs in an inner Node class. Internally, the tree is organized both by the binary search requirement on Node.Key and the heap invariant requirement on Node.Priority.

public class BinaryTreap<TKey, TValue> where TKey : IComparable<TKey>
{
 [DebuggerDisplay("Key={Key}, Priority={Priority}")]
 /// <summary>Represents a Node in a BinaryTreap</summary>
 class Node
 {
 private static Random random = new Random();
 public readonly int Priority;
 public readonly TKey Key;
 public readonly TValue Value;
 public Node Left, Right;
 public Node(TKey key, TValue value, 
 Node left = null, Node right = null)
 {
 Priority = random.Next(); Key = key; 
 Value = value; Left = left; Right = right;
 }
 }
 /// <summary>Tree root, organized as min-heap/BST</summary>
 private Node root;
}

The methods Set and Delete are implemented similar to the standard binary search tree functions for adding/removing from the tree (these can be found on wikipedia). The only difference is that now an insertion or a deletion might trigger rotating the tree to ensure the heap invariant.

 /// <summary>
 /// Sets/Replaces node located at child.key in root 
 /// and rebalances the tree if necessary
 /// </summary>
 private Node Set(Node root, Node child)
 {
 if (root == null) return child;
 int cmp = child.Key.CompareTo(root.Key);
 if (cmp == 0)
 return child;
 else if (cmp > 0)
 {
 root.Right = Set(root.Right, child);
 if (root.Right.Priority < root.Priority)
 root = LRotate(root);
 }
 else if (cmp < 0)
 {
 root.Left = Set(root.Left, child);
 if (root.Left.Priority < root.Priority)
 root = RRotate(root);
 }
 return root;
 }
 /// <summary>
 /// Deletes key from root by demoting it down to a leaf
 /// and rebalances the tree if necessary
 /// </summary>
 private Node Delete(Node root, TKey key)
 {
 if (root == null) return null;
 int cmp = key.CompareTo(root.Key);
 if (cmp < 0) root.Left = Delete(root.Left, key);
 if (cmp > 0) root.Right = Delete(root.Right, key);
 if (cmp== 0)
 {
 if (root.Left != null && root.Right != null)
 {
 if (root.Left.Priority < root.Right.Priority)
 root = RRotate(root); 
 else
 root = LRotate(root); 
 }
 else if (root.Left != null) root = RRotate(root);
 else if (root.Right != null) root = LRotate(root);
 else return null;
 root = Delete(root, key);
 }
 return root;
 } 

I'm wondering if my tree rotation methods can be improved. Should I make the Nodes in the tree immutable, and return a new rotated Node instead?

 /// <summary>
 /// Promotes the right child to root 
 /// (i.e. rotate the "right child" left)
 /// </summary>
 private Node LRotate(Node root)
 {
 Node temp = root.Right;
 root.Right = temp.Left;
 temp.Left = root;
 return temp;
 }
 /// <summary>
 /// Promotes the left child to root 
 /// (i.e. rotate the "left child" right)
 /// </summary>
 private Node RRotate(Node root)
 {
 Node temp = root.Left;
 root.Left = temp.Right;
 temp.Right = root;
 return temp;
 }

Finally, my code provides validation. This is intended for testing purposes only, though I'm not sure how this should be exposed to a test project without making Node internal and then exposing the project's internals. Maybe there's no better way.

 /// <summary>Performs an in-order traversal from root</summary>
 private IEnumerable<Node> InOrder(Node root)
 {
 if (root == null)
 yield break;
 foreach (Node child in InOrder(root.Left).Append(root).Concat(InOrder(root.Right)))
 yield return child;
 }
 /// <summary>Validates the min-heap order for root</summary>
 private bool IsHeap(Node root)
 {
 if (root == null)
 return true;
 if (root.Right != null && root.Right.Priority < root.Priority)
 return false;
 if (root.Left != null && root.Left.Priority < root.Priority)
 return false;
 return IsHeap(root.Left) && IsHeap(root.Right);
 }
 /// <summary>
 /// Returns true if the heap order and bst order
 /// properties are satisfied
 /// </summary>
 public bool AssertTreap()
 {
 return root == null ? true :
 InOrder(root).SequenceEqual(InOrder(root).OrderBy(x => x.Key)) && IsHeap(root); 
 }

I've definedAppend in an extension method

internal static class Extensions
{
 public static IEnumerable<T> Append<T>(this IEnumerable<T> source, T item)
 {
 foreach (T x in source)
 yield return x;
 yield return item;
 }
}

Example of use

Here's a simple test that can be run in the debugger.

class Program
{
 public static void Main(string[] args)
 {
 var t = new BinaryTreap<int, int>();
 for (int i = 0; i < 1000; i++)
 t[i] = i;
 bool valid = t.AssertTreap();
 t.Delete(1);
 try
 {
 int one = t[1];
 }
 catch
 {
 // doesn't exist
 }
 }
}

What I'd like reviewed

• Better (more functional) implementations of RotateR and RotateL?
• How should I expose Node to a test project? Right now I have my validation code in the class itself which doesn't seem right. I don't want to mark Node internal; is there a better way to expose the underlying data structure for testing purposes?

Edit

Here is the Get method used by the indexer.

 /// <summary>Retrieves Node located at key by binary search</summary>
 private Node Get(Node root, TKey key)
 {
 if (root == null) return null;
 int cmp = key.CompareTo(root.Key);
 if (cmp < 0) return Get(root.Left, key);
 if (cmp > 0) return Get(root.Right, key);
 return root;
 }

Here is the public wrapper for Delete.

 public void Delete(TKey key)
 {
 root = Delete(root, key);
 }

Answer 1

1. It would be nice to be able to pass an IComparer<TKey> instead of having to make sure TKey implements IComparable<>. It could default to Comparer<TKey>.Default. This provides you with a lot more flexibility in terms of which types can be used as keys.

2. Get can return null . So if you try to access a non-existing key you will get a NullReferenceException which is typically not very meaningful. The indexer should protect against that and throw a KeyNotFoundException instead.

3. Related to the previous point you may want to consider implementing a TryGet method similar to what other data structure implementations in the .NET framework provide.

4. Regarding the validation code: I don't think the validation code should live in the data structure. What I'd do is to make BinaryTreap implement IEnumerable<KeyValuePair<TKey, TValue>> with the enumerator doing a in-order traversal, but instead of yielding the node it yields a KeyValuePair<TKey, TValue> with the data. This way you can write the validation code as a unit test.
   The IsHeap one is a bit more tricky. Need to think about that one.