What is balanced binary search tree in c plus plus?
#include<iostream>
template<typename T>
class bin_tree
{
class node
{
T data;
node* left {nullptr};
node* right {nullptr};
public:
node (const T&);
node (const node&);
node (node&&);
node& operator= (const node&);
node& operator= (node&&);
~node ();
void insert (const T&);
bool exists (const T&) const;
std::ostream& depth_first_print (std::ostream&)
const;
};
node* root {nullptr};
public:
bin_tree ();
bin_tree (const T[], const size_t);
bin_tree (const bin_tree&);
bin_tree (bin_tree&&);
bin_tree& operator= (const bin_tree&);
bin_tree& operator= (bin_tree&&);
~bin_tree ();
void clear ();
void insert (const T&);
bool exists (const T&) const;
std::ostream& depth_first_print (std::ostream&)
const;
};
// node output stream insertion operator (depth-first
traversal)
template<typename T>
std::ostream& operator<< (std::ostream& os,
typename const bin_tree<T>& t)
{
return t.depth_first_print (os);
}
// node default/conversion constructor (construct a node from a
type T)
template<typename T>
bin_tree<T>::node::node (const T& value)
: data {value}
{}
// node copy constructor
template<typename T>
bin_tree<T>::node::node (typename const
bin_tree<T>::node& rhs)
: data {rhs.data}
, left {rhs.left ? new node {*rhs.left} : nullptr}
, right {rhs.right ? new node {*rhs.right} : nullptr}
{}
// node move constructor
template<typename T>
bin_tree<T>::node::node (typename
bin_tree<T>::node&& rhs)
: data {std::move(rhs.data)}
, left {std::move(rhs.left)}
, right {std::move(rhs.right)}
{
rhs.left = nullptr;
rhs.right = nullptr;
}
// node copy assignement operator overload
template<typename T>
typename bin_tree<T>::node&
bin_tree<T>::node::operator= (typename const
bin_tree<T>::node& rhs)
{
delete left;
delete right;
data = rhs.data;
left = rhs.left ? new node (*rhs.left) : nullptr;
right = rhs.right ? new node (*rhs.right) : nullptr;
}
// node move assignment operator overload
template<typename T>
typename bin_tree<T>::node&
bin_tree<T>::node::operator= (typename
bin_tree<T>::node&& rhs)
{
delete left;
delete right;
data = std::move (rhs.data);
left = rhs.left;
right = rhs.right;
rhs.left = nullptr;
rhs.right = nullptr;
}
// node destructor
template<typename T>
bin_tree<T>::node::~node ()
{
delete left;
delete right;
}
// node print method (depth first traversal)
template<typename T>
std::ostream&
bin_tree<T>::node::depth_first_print(std::ostream& os)
const
{
if (left) left->depth_first_print (os);
os << data << ' ';
if (right) right->depth_first_print (os);
return os;
}
// node exists method
template<typename T>
bool bin_tree<T>::node::exists (const T& value)
const
{
return value == data ? true :
value < data && left ? left->exists (value) :
value > data && right ? right->exists (value)
:
false;
}
// node insertion method
template<typename T>
void bin_tree<T>::node::insert (const T& value)
{
if (value < data)
{
if (left)
left->insert (value);
else
left = new node {value};
}
else
{
if (right)
right->insert (value);
else
right = new node {value};
}
}
// tree default constructor (construct an empty tree)
template<typename T>
bin_tree<T>::bin_tree ()
{}
// tree overloaded constructor (construct a tree from an
array)
template<typename T>
bin_tree<T>::bin_tree (const T arr[], const size_t
size)
{
for (size_t index=0; index<size; ++index)
insert (arr[index]);
}
// tree copy constructor
template<typename T>
bin_tree<T>::bin_tree (const bin_tree<T>&
rhs)
{
*this = rhs;
}
// tree move constructor
template<typename T>
bin_tree<T>::bin_tree (bin_tree&& rhs):
root{rhs.root}
{
rhs.root=nullptr;
}
// tree copy assignment operator overload
template<typename T>
bin_tree<T>& bin_tree<T>::operator= (const
bin_tree<T>& rhs)
{
if (root)
delete root;
if (rhs.root)
{
root = new node {*rhs.root};
}
return *this;
}
// tree move assignment operator overload
template<typename T>
bin_tree<T>& bin_tree<T>::operator=
(bin_tree&& rhs)
{
if (root)
delete root;
root=rhs.root;
rhs.root=nullptr;
return *this;
}
// tree destructor
template<typename T>
bin_tree<T>::~bin_tree ()
{
clear();
}
// tree print method (depth first traversal)
template<typename T>
std::ostream&
bin_tree<T>::depth_first_print(std::ostream& os)
const
{
return root ? root->depth_first_print (os) : os <<
"{empty}";
}
// tree clear method
template<typename T>
void bin_tree<T>::clear ()
{
delete root;
root = nullptr;
}
// tree insertion method
template<typename T>
void bin_tree<T>::insert (const T& value)
{
if (!root)
root = new node {value};
else
root->insert (value);
}
// tree exists method
template<typename T>
bool bin_tree<T>::exists (const T& value) const
{
return root ? root->exists (value) : false;
}
int main()
{
int arr[10] = {42, 56, 30, 5, 12, 60, 40, 8, 1, 99};
std::cout << "Test default constructor:\n";
bin_tree<int> a {}; // {} is implied if omitted
std::cout << "a: " << a << std::endl;
std::cout << "\nTest overloaded constructor:\n";
bin_tree<int> b {arr, 10};
std::cout << "b: " << b << std::endl;
std::cout << "\nTest tree copy constructor (c{b}):\n";
bin_tree<int> c {b};
std::cout << "b: " << b << std::endl;
std::cout << "c: " << c << std::endl;
std::cout << "\nTest tree move constructor
(d{move(b)}):\n";
bin_tree<int> d {std::move(b)};
std::cout << "b: " << b << std::endl;
std::cout << "c: " << c << std::endl;
std::cout << "d: " << d << std::endl;
std::cout << "\nTest insertion into c:\n";
c.insert (41);
std::cout << "b: " << b << std::endl;
std::cout << "c: " << c << std::endl;
std::cout << "d: " << d << std::endl;
std::cout << "\nTest search:\n";
if (c.exists (41))
std::cout << "Value 41 exists in c" <<
std::endl;
else
std::cout << "Value 41 does not exist in c" <<
std::endl;
if (d.exists (41))
std::cout << "Value 41 exists in d" <<
std::endl;
else
std::cout << "Value 41 does not exist in d" <<
std::endl;
std::cout << "\nTest copy assignment (c=d):\n";
c = d;
std::cout << "b: " << b << std::endl;
std::cout << "c: " << c << std::endl;
std::cout << "d: " << d << std::endl;
std::cout << "\nTest move assignment (d=move(c)):\n";
d = std::move (c);
std::cout << "b: " << b << std::endl;
std::cout << "c: " << c << std::endl;
std::cout << "d: " << d << std::endl;
std::cout << "\nTest clear method (d.clear()):\n";
d.clear();
std::cout << "b: " << b << std::endl;
std::cout << "c: " << c << std::endl;
std::cout << "d: " << d << std::endl;
}
