Week 6: Exercises

1. Sort

Write a generic method sort() that can sort an array of elements of any type T that implements the IComparable<T> interface. You may use any sorting algorithm that you like.

2. Binary Tree

In the lecture we began to write a class holding a set of values in a binary search tree:

class TreeSet<T> where T: IComparable<T> {
    class Node {
        public T val;
        public Node? left, right;

        public Node(T val) { this.val = val; }
    }

    Node? root;

    public bool contains(T x) {
        Node? p = root;
        while (p != null) {
            int c = x.CompareTo(p.val);
            if (c == 0)
                return true;
            else if (c < 0)
                p = p.left;
            else
                p = p.right;
        }
                
        return false;
    }

    // more methods here: insert(), delete(), ...
}

a) Write an insert() method, giving it an appropriate type.

b) Add a constructor TreeSet(T[] a) that builds a TreeSet from an array a. The resulting tree should be balanced. Do not modify the array.

c) Add a method T[] range(T a, T b) that returns a sorted array of all values x such that a ≤ x ≤ b.

d) Add a method void validate() that verifies that the structure satisfies the ordering requirements of a binary tree. If the structure is invalid, throw an exception with the message "invalid".

3. Dictionary

In the lecture we began to write a generic class Dictionary<K, V>:

class Dictionary<K, V> where K : IComparable<K> {
    class Node {
        public K key;
        public V val;
        public Node? next;

        public Node(K key, V val) {
            this.key = key; this.val = val;
        }
    }

    Node?[] a;  // array of hash chains
    
    ...
}

Complete the implementation of this class, including an indexer that lets the caller assign and lookup key/value pairs conveniently.