Converting a BST set (values only) to a BST map (keys and values) video (21 minutes) (Spring 2021)
The previously shown implementation of a BST was similar to an std::set in that, nodes in the BST only had values. There was no concept of a key-value pair. Values were used to sort the BST, comparisons were based on the value, etc. In a set, the value "is its own key".
However, there are use cases for having a key/value relationship; where a value is stored, and updated/output as needed, but the key is used for comparison, sorting, lookup, etc. One example of this could be using the name of a color as a key to its hex value. For example, colors_bst["black"] = "#000000", colors_bst["white"] = "#ffffff", etc. Another example of this could be values of some complex object type (e.g. a contact in your phone who has a name, email address, phone number, etc.), where a single property of the object type like 'name' could be used as the key.
Complete example code is at the bottom.
The template class now accepts two types, Key and Value. All references to T in the template code were updated to reflect the new Key and Value types. (In general, the Key type is used for comparisons in the tree, eg, contains, < or >, and Value type is used as the value contained in each node.)
template <typename Key, typename Value>
class BinarySearchTree {...}
The Node struct now has key and value properties (of type Key and Value, respectively), and its constructors have been updated to reflect that. There is a new Node constructor, that only accepts a key. This constructor will result in a value created by the default constructor of its type.
struct Node {
Key key;
Value value;
Node *left, *right;
Node(const Key& key) : key(key), left(nullptr), right(nullptr) {}
Node(const Key& key, const Value& value)
: key(key), value(value), left(nullptr), right(nullptr) {}
// ... more Node member functions below....
}
As mentioned above, keys are used for comparison, sorting, etc in the tree. The value is what is actually stored in nodes, and output or inserted as needed.
The two insert functions below demonstrate the use of key and value in code.
bool insert(const Key& key, const Value& value) {
if (root == nullptr) {
root = new Node(key, value);
return true;
} else {
return root->insert(key, value);
}
}
bool insert(const Key& new_key, const Value& new_value) {
if (new_key == key) {
return false;
} else if (new_key < key) { // Need to insert to the left
if (left == nullptr) {
left = new Node(new_key, new_value);
return true;
} else {
return left->insert(new_key, new_value);
}
} else { // if (new_key > key) Need to insert to the right
if (right == nullptr) {
right = new Node(new_key, new_value);
return true;
} else {
return right->insert(new_key, new_value);
}
}
}
This operator is present on both the BinarySearchTree class and the Node struct. It uses the same pattern as other functions; called on the root node in the BinarySearchTree class, then recursively called on left/right child as needed, in Node::operator[]
The [] operator returns a value, given a key.
The [] operator is used for someBinarySearchTree[someKey] = someValue syntax
Similarly to std::map, if a nonexistent key is passed in, a new node at that key will be added, containing a default-constructed value.
Value& operator[](const Key& key) {
if (root == nullptr) {
root = new Node(key);
return root->value;
} else {
return (*root)[key];
}
}
Value& operator[](const Key& k) {
if (k == key) {
return value;
} else if (k < key) { // Need to insert to the left
if (left == nullptr) {
left = new Node(k);
return left->value;
} else {
return (*left)[k];
}
} else { // if (k > key) Need to insert to the right
if (right == nullptr) {
right = new Node(k);
return right->value;
} else {
return (*right)[k];
}
}
}
These are the complete files after the set to map refactor, which added the concept of a key that maps to a value.
#ifndef BST_H_
#define BST_H_
#include <iostream>
using std::cout;
using std::endl;
template <typename Key, typename Value>
class BinarySearchTree {
struct Node {
Key key;
Value value;
Node *left, *right;
Node(const Key& key) : key(key), left(nullptr), right(nullptr) {}
Node(const Key& key, const Value& value)
: key(key), value(value), left(nullptr), right(nullptr) {}
void print() {
if (left != nullptr) {
left->print();
}
cout << key << ": " << value << endl;
if (right != nullptr) {
right->print();
}
}
bool contains(const Key& k) {
if (k == key) {
return true;
} else if (k < key) {
if (left == nullptr) {
return false;
} else {
return left->contains(k);
}
} else { // if (k > key)
if (right == nullptr) {
return false;
} else {
return right->contains(k);
}
}
}
bool insert(const Key& new_key, const Value& new_value) {
if (new_key == key) {
return false;
} else if (new_key < key) { // Need to insert to the left
if (left == nullptr) {
left = new Node(new_key, new_value);
return true;
} else {
return left->insert(new_key, new_value);
}
} else { // if (new_key > key) Need to insert to the right
if (right == nullptr) {
right = new Node(new_key, new_value);
return true;
} else {
return right->insert(new_key, new_value);
}
}
}
Value& operator[](const Key& k) {
if (k == key) {
return value;
} else if (k < key) { // Need to insert to the left
if (left == nullptr) {
left = new Node(k);
return left->value;
} else {
return (*left)[k];
}
} else { // if (k > key) Need to insert to the right
if (right == nullptr) {
right = new Node(k);
return right->value;
} else {
return (*right)[k];
}
}
}
};
Node *root;
public:
BinarySearchTree() : root(nullptr) {}
~BinarySearchTree() {
delete root;
}
void print() {
if (root != nullptr) {
root->print();
}
}
bool insert(const Key& key, const Value& value) {
if (root == nullptr) {
root = new Node(key, value);
return true;
} else {
return root->insert(key, value);
}
}
bool contains(const Key& key) {
if (root == nullptr) {
return false;
} else {
return root->contains(key);
}
}
Value& operator[](const Key& key) {
if (root == nullptr) {
root = new Node(key);
return root->value;
} else {
return (*root)[key];
}
}
};
#endif /* BST_H_ */#include <iostream>
#include <string>
#include "bst.h"
using namespace std;
int main() {
BinarySearchTree<int, string> bst;
bst[11] = "eleven";
bst[55] = "fifty five";
bst[99] = "ninety nine";
cout << "bst before using operator[]:" << endl;
bst.print();
cout << endl;
for (int x : {0, 11, 33, 55, 88, 99, 1000}) {
cout << "bst[" << x << "] == " << bst[x] << endl;
}
cout << endl;
cout << "bst after using operator[]:" << endl;
bst.print();
return 0;
}$ clang++ -pedantic -Wall -lm -std=c++20 -o bst_set_to_map_demo bst_set_to_map_demo.cpp
$ ./bst_set_to_map_demo
bst before using operator[]: 11: eleven 55: fifty five 99: ninety nine bst[0] == bst[11] == eleven bst[33] == bst[55] == fifty five bst[88] == bst[99] == ninety nine bst[1000] == bst after using operator[]: 0: 11: eleven 33: 55: fifty five 88: 99: ninety nine 1000:
Thanks to Brian Foster for typing up the rough draft of these notes based on the lecture video.