# 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 $\langle k,x\rangle$ such that $hash(k) = i$. A counter n maintains the number of keys that belong to the dictionary.

The average cost analysis is stated under two assumptions:

1. Given a key k, hash(k) returns a natural number in time $\O(1)$.

2. 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)$.

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

using namespace std;

template <typename Key, typename Info>
class Dictionary {

private:

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

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

#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);
}

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;
}   }

};


# Fòrum Lliçons.jutge.org
Jordi Petit
Universitat Politècnica de Catalunya, 2020

Prohibit copiar. Tots els drets reservats.