Binary Search Tree
Binary Search Tree (BST) was invented by P.F. Windley, A.D. Booth, A.J.T. Colin, and T.N. Hibbard in 1960. In computer science, BST, sometimes called ordered tree. BST is a binary tree where each node has a Comparable key (and an associated value) and satisfies the restriction that the key in any node is larger than the keys in all nodes in that node's left subtree and smaller than the keys in all nodes in that node's right subtree [1].
The implementation below uses smart pointers to hold the left and right child but the parent node is refereed by weak pointer. A marked node called root hold the whole tree and its parent is a null pointer. The inner nodes have one child at least. On the lowermost level the leaf nodes located. Leaf nodes have't any child, so their left and right child pointers are null pointers.
#include <atomic>
#include <memory>
namespace DataStructure {
template<typename T>
class BinarySearchTree {
struct Node {
std::weak_ptr<Node> _parent = nullptr;
std::shared_ptr<Node> left = nullptr;
std::shared_ptr<Node> right = nullptr;
T key = nullptr;
std::shared_ptr<Node> parent() { if (auto spt = _parent.lock()) return spt; }
Node(const T& _k, std::shared_ptr<Node> _p) : key(_k), _parent(_p) {};
};
std::shared_ptr<Node> root = nullptr;
// helper functions
auto _min(std::shared_ptr<Node>) const -> decltype(root);
auto _max(std::shared_ptr<Node>) const -> decltype(root);
auto _next(std::shared_ptr<Node>) const -> decltype(root);
auto _prev(std::shared_ptr<Node>) const -> decltype(root);
std::ostream& _inorder(std::shared_ptr<Node>, std::ostream&);
std::ostream& _preorder(std::shared_ptr<Node>, std::ostream&);
std::ostream& _postorder(std::shared_ptr<Node>, std::ostream&);
size_t _size(std::shared_ptr<Node>) const;
public:
BinarySearchTree() = default;
~BinarySearchTree() { destroy(); }
// non - copyable, non - movable
BinarySearchTree(const BinarySearchTree&) = delete;
BinarySearchTree& operator=(const BinarySearchTree&) = delete;
BinarySearchTree(const BinarySearchTree&&) = delete;
BinarySearchTree& operator=(const BinarySearchTree&&) = delete;
size_t size() const { return _size(root); }
bool isempty() { return (_size(root) == 0) ? true : false; }
bool find(const T&) const;
void insert(const T&);
void remove(const T&);
void destroy();
std::ostream& inorder(std::ostream&);
std::ostream& preorder(std::ostream&);
std::ostream& postorder(std::ostream&);
};
};
The destructor calls the destroy method what sets the root null pointer. It is an elegant and safe way to deallocate the memory. If we set the root null all the other node will be deleted because of smart pointer methodology.
template<class T>
void DataStructure::BinarySearchTree<T>::destroy() {
root = nullptr;
}
_min and _max functions find the minimum and the maximum element of a subtree while _next and _prev find the next and the previous element comparing the keys.
template<class T>
auto DataStructure::BinarySearchTree<T>::_min(std::shared_ptr<Node> _node) const -> decltype(root) {
auto tmp = _node;
while (tmp->left != nullptr)
tmp = tmp->left;
return tmp;
}
template<class T>
auto DataStructure::BinarySearchTree<T>::_max(std::shared_ptr<Node> _node) const -> decltype(root) {
auto tmp = _node;
while (tmp->right != nullptr)
tmp = tmp->right;
return tmp;
}
template<class T>
auto DataStructure::BinarySearchTree<T>::_next(std::shared_ptr<Node> _node) const -> decltype(root) {
if (_node->right != nullptr)
return _min(_node->right);
auto tmp = _node->parent();
while (tmp != nullptr && _node == tmp->right) {
_node = tmp;
tmp = tmp->parent();
}
return tmp;
}
template<class T>
auto DataStructure::BinarySearchTree<T>::_prev(std::shared_ptr<Node> _node) const -> decltype(root) {
if (_node->left != nullptr)
return _max(_node->left);
auto tmp = _node->parent();
while (tmp != nullptr && _node == tmp->left) {
_node = tmp;
tmp = tmp->parent();
}
return tmp;
}
_size function returns back the number of the nodes. It is a recursive algorithm and calls itself while the actual node is not null pointer.
template<class T>
size_t DataStructure::BinarySearchTree<T>::_size(std::shared_ptr<Node> _node) const {
if (_node == nullptr)
return 0;
else
return _size(_node->left) + _size(_node->right) + 1;
}
We can search for an element in the tree by key using the find method.If the tree is empty, we have a search miss; if the search key is equal to the key at the root, we have a search hit. Otherwise, we search (recursively) in the appropriate subtree.
template<class T>
bool DataStructure::BinarySearchTree<T>::find(const T& k) const {
auto tmp = root;
while (tmp != nullptr && (k < tmp->key || tmp->key < k))
if (k < tmp->key)
tmp = tmp->left;
else
tmp = tmp->right;
if (tmp == nullptr)
return false;
return true;
}
Insert [1] is not much more difficult to implement than search. Indeed, a search for a key not in the tree ends at a null link, and all that we need to do is replace that link with a new node containing the key. If the tree is empty, we return a new node containing the key and value; if the search key is less than the key at the root, we set the left link to the result of inserting the key into the left subtree; otherwise, we set the right link to the result of inserting the key into the right subtree.
template<class T>
void DataStructure::BinarySearchTree<T>::insert(const T& k) {
std::shared_ptr<Node> y = nullptr;
auto x = root;
// find the key position in the tree
while (x != nullptr && (k < x->key || x->key < k)) {
y = x;
if (k < x->key)
x = x->left;
else
x = x->right;
}
// if node with key k exitst, do nothing
if (x != nullptr)
return;
// create new node with key k and parent y
x = std::make_shared<Node>(k, y);
// if x is first element, then set root to x
if (y == nullptr)
root = x;
else if (x->key < y->key)
y->left = x;
else
y->right = x;
y = nullptr;
x = nullptr;
}
If we want to remove an element from the tree, first we have to find it. The simplest case if the delete node has not any child. We have to set its parent left or right child pointer to null. If it has only one child we have to link the parent with the grandchild. Int the third case the delete node has two children so we have to find the next node of the delete node and set the link between the next and the parent node.
template<class T>
void DataStructure::BinarySearchTree<T>::remove(const T& k) {
// find the key position in the tree
auto z = root;
while (z != nullptr && (k < z->key || z->key < k))
if (k < z->key)
z = z->left;
else
z = z->right;
// if element with key k doesn't exsist, then return
if (z == nullptr)
return;
// remove the element from tree
std::shared_ptr<Node> y = nullptr;
if (z->left == nullptr || z->right == nullptr)
y = z;
else
y = _next(z);
std::shared_ptr<Node> x = nullptr;
if (y->left != nullptr)
x = y->left;
else
x = y->right;
if (x != nullptr)
x->parent() = y->parent();
if (y->parent() == nullptr)
root = x;
else if (!(y < y->parent()->left || y->parent()->left < y))
y->parent()->left = x;
else
y->parent()->right = x;
if (y < z || z < y)
z->key = y->key;
y = x = nullptr;
}
The pre, in and post -order methods traverse the tree in a preorder, inorder and postorder way and print the value to the given stream.
template<class T>
std::ostream& DataStructure::BinarySearchTree<T>::preorder(std::ostream& o) {
if (isempty()) {
throw std::exception("Missing element!\n");
}
return _preorder(root, o);
}
template<class T>
std::ostream& DataStructure::BinarySearchTree<T>::postorder(std::ostream& o) {
if (isempty()) {
throw std::exception("Missing element!\n");
}
return _postorder(root, o);
}
template<class T>
std::ostream& DataStructure::BinarySearchTree<T>::inorder(std::ostream& o) {
if (isempty()) {
throw std::exception("Missing element!\n");
}
return _inorder(root, o);
}
template<class T>
std::ostream& DataStructure::BinarySearchTree<T>::_preorder(std::shared_ptr<Node> i, std::ostream& o) {
o << i->key << ", ";
if (i->left != nullptr) {
_preorder(i->left, o);
}
if (i->right != nullptr) {
_preorder(i->right, o);
}
return o;
}
template<class T>
std::ostream& DataStructure::BinarySearchTree<T>::_postorder(std::shared_ptr<Node> i, std::ostream& o) {
if (i->left != nullptr) {
_postorder(i->left, o);
}
if (i->right != nullptr) {
_postorder(i->right, o);
}
o << i->key << ", ";
return o;
}
template<class T>
std::ostream& DataStructure::BinarySearchTree<T>::_inorder(std::shared_ptr<Node> i, std::ostream& o) {
if (i->left != nullptr) {
_inorder(i->left, o);
}
o << i->key << ", ";
if (i->right != nullptr) {
_inorder(i->right, o);
}
return o;
}
The main demonstrates the BS tree.
#include <iostream>
#include <random>
#include <functional>
#include <ctime>
#include <exception>
std::cout << "Testing data structure Binary Tree ...\n\n";
////////// Using random generator engine //////////
std::default_random_engine gen((unsigned int)std::time(0));
std::uniform_int_distribution<int> distribution(1, 20);
auto randInt = std::bind(distribution, gen); // using randInt() generate integer number between (1-20)
try {
std::cout << "\n*** Inserted element: ***\n";
DataStructure::BinarySearchTree<int> myShort;
for (int i = 0; i < 15; ++i)
myShort.insert( randInt() );
std::cout << "Preorder: ";
myShort.preorder(std::cout);
std::cout << "\n";
std::cout << "Inorder: ";
myShort.inorder(std::cout);
std::cout << "\n\n";
std::cout << "*** Removing element: ***\n";
for (int i = 0; i < 5; ++i)
myShort.remove( randInt() );
std::cout << "Preorder after removing: ";
myShort.preorder(std::cout);
std::cout << "\n\n";
myShort.destroy();
}
catch (const std::exception& e) {
std::cout << "Error: " << e.what() << std::endl;
}