Dictionaries

Implementation with a hash table.

This implementation arranges the elements of the dictionary into M lists implemented with vectors. The $i$ -th list contains all the key/info pairs $⟨ k, x ⟩$ such that $‘ h a s h ‘ (k) = i$ . A counter n maintains the number of keys that belong to the dictionary.

The average cost analysis is stated under two assumptions:

Given a key k, hash(k) returns a natural number in time $O (1)$ .
The hash function hashes uniformly at every new call with a different key.

Implicit copy constructor, assignment operator and destructor do the job; no need to implement them. Their worst-case and average-case cost is $O (n + M)$ .

c++


#include <utility>
#include <vector>
#include <cassert>

using namespace std;


template <typename Key, typename Info>
class Dictionary {

private:

    /** Special integer value for "not found". */
    const int None = -1;

    /** A Pair wraps a Key and an Info together. */
    using Pair = pair<Key, Info>;

    /** A List is a vector (a list would also do) of Pairs. */
    using List = vector<Pair>;

    /** Hash table */
    vector<List> t;

    /** Number of keys */
    int n;

    /** Number of positions */
    int M;

public:

    /** Creates an empty dictionary. Cost: O(M). */
    Dictionary (int M = 1009)
    :   t(M),
        n(0),
        M(M)
    {   }

    /** Assigns info to key. If the key already belongs
        to the dictionary, its associated information is
        modified.

        Worst-case cost: O(n). Average-case cost: O(1+n/M).
    */
    void assign (const Key& key, const Info& info) {
        const int h = hash(key) % M;
        const int p = position(key, t[h]);
        if (p != None) {
            t[h][p].second = info;
        } else {
            t[h].push_back({key, info});
            ++n;
    }   }

    /** Erases key and its associated information from the
        dictionary. If the key does not belong to the dictionary,
        nothing changes.

        Worst-case cost: O(n). Average-case cost: O(1+n/M).
    */
    void erase (const Key& key) {
        const int h = hash(key) % M;
        const int p = position(key, t[h]);
        if (p != None) {
            t[h][p] = t[h].back();
            t[h].pop_back();
            --n;
    }   }

    /** Returns a reference to the information associated to key.
        Prec: the dictionary contains key.

        Worst-case cost: O(n). Average-case cost: O(1+n/M).
    */
    Info& query (const Key& key) {
        const int h = hash(key) % M;
        const int p = position(key, t[h]);
        assert (p != None);
        return t[h][p].second;
    }

    /** Returns a constant reference to the information associated to key.
        Prec: the dictionary contains key.

        Worst-case cost: O(n). Average-case cost: O(1+n/M).
    */
    const Info& query (const Key& key) const {
        const int h = hash(key) % M;
        const int p = position(key, t[h]);
        assert (p != None);
        return t[h][p].second;
    }

    /** Determines if the dictionary contains a given key.

        Worst-case cost: O(n). Average-case cost: O(1+n/M).
    */
    bool contains (const Key& key) const {
        const int h = hash(key) % M;
        return position(key, t[h]) != None;
    }

    /** Returns the size (i.e. number of keys) of the dictionary.

        Worst-case cost: O(1). Average-case cost: O(1).
    */
    int size () const {
        return n;
    }

private:

    /** Returns the position of key in L, or None if it is not there. */
    static int position (const Key& key, const List& L) {
        const int s = L.size();
        for (int i = 0; i < s; ++i) {
            if (L[i].first == key) return i;
        }
        return None;
    }

};

Dictionary with a binary search tree (BST).

This implementation assumes that Key is of a comparable type.

A BST is a binary tree whose nodes store key/info pairs satisfying the property that, for every node $u$ , the key stored at $u$ is bigger than all the keys stored at the left subtree of $u$ and smaller than all the keys stored at the right subtree of $u$ .

This implementation represents the BST through a pointer root to a Node which contains: a key, the associated information, a pointer to the root of the left subtree, and a pointer to the root of the right subtree. Empty trees are represented by the null pointer. A counter n is maintained with the number of keys in the dictionary. In the following, $h$ denotes the height of the BST and we state the costs as a function of $h$ whenever possible.

In a randomly generated BST (where keys are inserted at uniformly chosen positions in the order of the keys and never deleted), we have $h = O (\log n)$ in expectation. Thus, a worst-case cost of $O (h)$ translates to an average-case cost of $O (\log n)$ (under this random model). In the worst-case scenario we have $h = n$ .

c++

#include <cassert>
using namespace std;


template <typename Key, typename Info>
class Dictionary {

private:

    /** Node structure with constructor. */
    struct Node {
        Key key;        // The key
        Info info;      // Its associated information
        Node* left;     // Pointer to left child
        Node* right;    // Pointer to right child

        Node (const Key& k, const Info& i, Node* l, Node* r)
        :   key(k), info(i), left(l), right(r)
        {   }
    };

    /** Number of keys. */
    int n;

    /** Pointer to the root of the BST. */
    Node* root;

public:

    /** Creates an empty dictionary. Cost: O(1). */
    Dictionary ()
    :   n(0),
        root(nullptr)
    {   }

    /** Copy constructor. Cost: O(n). */
    Dictionary (const Dictionary& d)
    :   n(d.n),
        root(copy(d.root))
    {   }

    /** Assignment operator. Cost: O(n+d.n). */
    Dictionary& operator= (const Dictionary& d) {
        if (&d != this) {
            free(root);
            n = d.n;
            root = copy(d.root);
        }
        return *this;
    }

    /** Destructor. Cost: O(n). */
    ~Dictionary () {
        free(root);
    }

º
private:

    /** Deletes the tree pointed by p.

        Cost: O(s) where s is the number of nodes in the tree pointed by p.
    */
    static void free (Node* p) {
        if (p) {
            free(p->left);
            free(p->right);
            delete p;
    }   }

    /** Returns a pointer to a copy of the tree pointed by p.

        Cost: O(s) where s is the number of nodes in the tree pointed by p.
    */
    static Node* copy (Node* p) {
        return p ? new Node(p->key, p->info, copy(p->left), copy(p->right)) : nullptr;
    }

    /** Returns a pointer to the node of the tree pointed by p that contains key,
        or nullptr if the key is not there.

        Cost: O(h) where h is the height of the tree pointed by p.
    */
    static Node* find (Node* p, const Key& key) {
        if (p) {
            if (key < p->key) {
                return find(p->left, key);
            } else if (key > p->key) {
                return find(p->right, key);
        }   }
        return p;
    }

    /** Assigns info to key if the key belongs to
        the tree pointed by p. Otherwise adds a new node into
        the tree pointed by p with the key and the associated
        information.

        Cost: O(h) where h is the height of the tree pointed by p.
    */
    void assign (Node*& p, const Key& key, const Info& info) {
        if (p) {
            if (key < p->key) {
                assign(p->left, key, info);
            } else if (key > p->key) {
                assign(p->right, key, info);
            } else {
                p->info = info;
            }
        } else {
            p = new Node(key, info, nullptr, nullptr);
            ++n;
    }   }

    /** Deleting a node with at least one
        empty child is easy. When both children are non-empty, calls
        extract_minimum(), which extracts the minimum of the
        right child and returns a pointer to it. This node is placed
        where the node that should disappear was, which is finally
        deleted.

        Cost: O(h) where h is the height of the tree pointed by p.
    */
    void erase (Node*& p, const Key& key) {
        if (p) {
            if (key < p->key) {
                erase(p->left, key);
            } else if (key > p->key) {
                erase(p->right, key);
            } else {
                Node* q = p;
                if (!p->left) p = p->right;
                else if (!p->right) p = p->left;
                else {
                    Node* m = extract_minimum(p->right);
                    m->left = p->left;
                    m->right = p->right;
                    p = m;
                }
                delete q;
                --n;
    }   }   }

    /** Extracts the node that contains the minimum element from the
        tree pointed by p. Returns a pointer to it.

        Cost: O(h) where h is the height of the tree pointed by p.
    */
    static Node* extract_minimum (Node*& p) {
        if (p->left) {
            return extract_minimum(p->left);
        } else {
            Node* q = p;
            p = p->right;
            return q;
    }   }

};

Dictionary with an Adel'son-Vel'skiĭ-Landis tree (AVL).

This implementation contains no documentation yet. Check the documentation for BSTs and Jordi Petit's notes.

The height of the null pointer is $- 1$ and the height of a leaf is $0$ .

c++

#include <cassert>
using namespace std;


template <typename Key, typename Info>
class Dictionary {

private:

    /** Node structure with constructor. */
    struct Node {
        Key key;        // The key
        Info info;      // Its associated information
        Node* left;     // Pointer to left child
        Node* right;    // Pointer to right child
        int height;     // Height of the tree

        Node (const Key& c, const Info& i, Node* l, Node* r, int h)
        :   key(c), info(i), left(l), right(r), height(h)
        {   }
    };

    /** Number of keys in the dictionary. */
    int n;

    /** Pointer to the root of the AVL of the dictionary. */
    Node* root;


public:

    /** Creates an empty dictionary. Cost: O(1). */
    Dictionary ()
    :   n(0),
        root(nullptr)
    {   }

    /** Copy constructor. Cost: O(n). */
    Dictionary (const Dictionary& d)
    :   n(d.n),
        root(copy(d.root))
    {   }

    /** Assignment operator. Cost: O(n+d.n). */
    Dictionary& operator= (const Dictionary& d) {
        if (&d != this) {
            free(root);
            n = d.n;
            root = copy(d.root);
        }
        return *this;
    }

    /** Destructor. Cost: O(n). */
    ~Dictionary () {
        free(root);
    }

    /** Assign info to key. Cost: O(h). */
    void assign (const Key& key, const Info& info) {
        assign(root, key, info);
    }

    /** Erases key and its associated information. If the
        key does not belong to the dictionary, nothing changes.

        Cost: O(log n).
    */
    void erase (const Key& key) {
        erase(root, key);
    }

    /** Returns a reference to the information associated to key.
        Prec: key belongs to the dictionary.

        Cost: O(log n).
    */
    Info& query (const Key& key) {
        Node* p = find(root, key);
        assert(p);
        return p->info;
    }

    /** Returns a reference to the information associated to key.
        Prec: key belongs to the dictionary.

        Cost: O(log n).
    */
    const Info& query (const Key& key) const {
        Node* p = find(root, key);
        assert(p);
        return p->info;
    }

    /** Determines if the dictionary contains key. Cost: O(log n). */
    bool contains (const Key& key) {
        return find(root, key);
    }

    /** Returns the size (i.e. number of keys) of the dictionary. Cost: O(1). */
    int size () {
        return n;
    }

private:

    /** Deletes the tree pointed by p.

        Cost: O(s) where s is the number of nodes in the tree pointed by p.
    */
    static void free (Node* p) {
        if (p) {
            free(p->left);
            free(p->right);
            delete p;
    }   }

    /** Returns a pointer to a copy of the tree pointed by p.

        Cost: O(s) where s is the number of nodes in the tree pointed by p.
    */
    static Node* copy (Node* p) {
        return p ? new Node(p->key, p->info, copy(p->left), copy(p->right), p->height) : nullptr;
    }

    /** Returns a pointer to the node of the tree pointed by p that contains key,
        or nullptr if the key is not there.

        Cost: O(h) where h is the height of the tree pointed by p.
    */
    static Node* find (Node* p, const Key& key) {
        if (p) {
            if (key < p->key) {
                return find(p->left, key);
            } else if (key > p->key) {
                return find(p->right, key);
        }   }
        return p;
    }

    /** Returns the height of a tree through its pointer (which may be null). Cost: O(1). */
    static int height (Node* p) {
        return p ? p->height : -1;
    }


    /** Updates the height of a node using the height of its subtrees. Cost: O(1). */
    static void update_height (Node* p) {
        p->height = 1 + max(height(p->left), height(p->right));
    }

    /** Applies a LL simple roration to a node. Cost: O(1). */
    static void LL (Node*& p) {
        Node* q = p;
        p = p->left;
        q->left = p->right;
        p->right = q;
        update_height(q);
        update_height(p);
    }

    /** Applies a RR simple roration to a node. Cost: O(1). */
    static void RR (Node*& p) {
        Node* q = p;
        p = p->right;
        q->right = p->left;
        p->left = q;
        update_height(q);
        update_height(p);
    }

    /** Applies a LR double roration to a node. Cost: O(1). */
    static void LR (Node*& p) {
        RR(p->left);
        LL(p);
    }

    /** Applies a RL double roration to a node. Cost: O(1). */
    static void RL (Node*& p) {
        LL(p->right);
        RR(p);
    }


    /** Assigns info to key if the key belongs to
        the tree pointed by p. Otherwise adds a new node into
        the tree pointed by p with the key and the associated
        information. Rebalances the tree after the insertion
        of necessary.

        Cost: O(log n).
    */
    void assign (Node*& p, const Key& key, const Info& info) {
        if (p) {
            if (key < p->key) {
                assign(p->left, key, info);
                if (height(p->left) - height(p->right) == 2) {
                    if (key < p->left->key) LL(p);
                    else LR(p);
                }
                update_height(p);
            } else if (key > p->key) {
                assign(p->right, key, info);
                if (height(p->right) - height(p->left) == 2) {
                    if (key > p->right->key) RR(p);
                    else RL(p);
                }
                update_height(p);
            } else {
                p->info = info;
            }
        } else {
            p = new Node(key, info, nullptr, nullptr, 0);
            ++n;
    }   }

    /** Algorithm to delete a key from a AVL tree.
        Cost: O(log n).
    */
    void erase (Node*& p, const Key& key) {
        if (p) {
            if (key < p->key) {
                erase(p->left, key);
                rebalance_left(p);
            } else if (key > p->key) {
                erase(p->right, key);
                rebalance_right(p);
            } else {
                Node* old = p;
                if (p->height == 0) {
                    p = 0;
                } else if (!p->left) {
                    p = p->right;
                } else if (!p->right) {
                    p = p->left;
                } else {
                    Node* q = extract_minimum(p->right);
                    q->left = p->left;  q->right = p->right;
                    p = q;
                    rebalance_right(p);
                }
                delete old;
                --n;
    }   }   }


    static void rebalance_left (Node*& p) {
        if (height(p->right) - height(p->left) == 2) {
            if (height(p->right->left) - height(p->right->right) == 1) {
                RL(p);
            } else {
                RR(p);
            }
        } else {
            update_height(p);
    }   }


    static void rebalance_right (Node*& p) {
        if (height(p->left) - height(p->right) == 2) {
            if (height(p->left->right) - height(p->left->left) == 1) {
                LR(p);
            } else {
                LL(p);
            }
        } else {
            update_height(p);
    }   }


    static Node* extract_minimum (Node*& p) {
        if (p->left) {
            Node* q = extract_minimum(p->left);
            rebalance_left(p);
            return q;
        } else {
            Node* q = p;
            p = p->right;
            return q;
    }   }

};

Dictionaries ​

Implementation with a hash table. ​

Dictionary with a binary search tree (BST). ​

Dictionary with an Adel'son-Vel'skiĭ-Landis tree (AVL). ​

Dictionaries

Implementation with a hash table.

Dictionary with a binary search tree (BST).

Dictionary with an Adel'son-Vel'skiĭ-Landis tree (AVL).