C# Treap implementation

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 where TKey : IComparable
{
    [DebuggerDisplay("Key={Key}, Priority={Priority}")]
    /// Represents a Node in a BinaryTreap
    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;
        }
    }

    /// Tree root, organized as min-heap/BST
    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.

```
///
/// Sets/Replaces node located at child.key in root
/// and rebalances the tree if necessary
///
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
/// Deletes key from root by demoti

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

-
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.

-
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.

-
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> with the enumerator doing a in-order traversal, but instead of yielding the node it yields a KeyValuePair 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.

StackExchange Code Review Q#108184, answer score: 10