Open andrealorenzon opened 5 years ago
draft:
/**
* @brief Inserts a new node into the binary search tree
* @param key The key for the new node
* @return The the inserted node otherwise nullptr
*/
template <typedef K, typedef T>
const std::shared_ptr<node<K,T> > insert(const K key) {
std::shared_ptr<node <K,T> > current = root;
std::shared_ptr<node <K,T> > parent = nullptr;
while(current!=nullptr) {
parent = current;
if (key > current->key) {
current = current->right;
} else if (key < current->key) {
current = current->left;
} else {
return nullptr;
}
}
current = std::make_shared<node <key_t> >(key);
current->parent = parent;
if(parent == nullptr) {
root = current;
} else if (current->key > parent->key) {
parent->right = current;
} else if (current->key < parent->key) {
parent->left = current;
}
return current;
}
Accepts 2 arguments: a key and a value
If we choose self-balancing trees, the insert function should automatically balance the tree (in that case, there's no need to implement a balance function). See link below.
Returns (2 options): 1) 0 if successfully insterted, 1 otherwise 2) maybe better: a shared_ptr to the new node if successfully inserted, nullptr otherwise