13 Estruturas associativas
Conjuntos e mapas ordenados (árvores) e não ordenados (hashing)
13.1 Árvores Binárias de Busca
template <typename K, typename V> class bstree
{
struct node_data;
using node = std::shared_ptr<node_data>;
struct node_data {
K key;
V value;
node left_child = nullptr;
node right_child = nullptr;
};
public:
void insert(const K& key, const V& value) {
root = insert_recursive(root, key, value);
}
void remove(const K& key) {
root = remove_recursive(root, key);
}
auto search(const K& key) const -> std::optional<V> {
const auto pos = search_recursive(root, key);
if (pos != nullptr)
return pos->value;
return std::nullopt;
}
private:
node root = nullptr;
static auto insert_recursive(
node root, const K& key, const V& value) -> node
{
if (root == nullptr)
return node(new node_data{key, value});
if (key < root->key)
root->left_child = insert_recursive(root->left_child, key, value);
else if (key > root->key)
root->right_child = insert_recursive(root->right_child, key, value);
return root;
}
static auto remove_recursive(node root, const K& key) -> node {
if (root == nullptr)
return nullptr;
if (key < root->key) {
root->left_child = remove_recursive(root->left_child, key);
return root;
}
if (key > root->key) {
root->right_child = remove_recursive(root->right_child, key);
return root;
}
if (root->left_child == nullptr && root->right_child == nullptr)
return nullptr;
if (root->left_child != nullptr && root->right_child != nullptr) {
const auto child = left_most(root->right_child);
std::swap(root->key, child->key);
root->right_child = remove_recursive(root->right_child, child->key);
return root;
}
return root->left_child != nullptr ? root->left_child : root->right_child;
}
static auto left_most(node root) -> node {
return root->left_child == nullptr ? root : left_most(root->left_child);
}
static auto search_recursive(node root, K key) -> node {
if (root == nullptr)
return nullptr;
if (key < root->key)
return search_recursive(root->left_child, key);
if (key > root->key)
return search_recursive(root->right_child, key);
return root;
}
};