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:
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)$.
#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$.
#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);
}
/** 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;
} }
};
Lliçons.jutge.org
Jordi Petit
Universitat Politècnica de Catalunya, 2023
Prohibit copiar. Tots els drets reservats.
No copy allowed. All rights reserved.