What is balanced binary search tree in c plus plus?

Question

Wiki User · Answer

#include template 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 std::ostream& operator<< (std::ostream& os, typename const bin_tree& t) { return t.depth_first_print (os); } // node default/conversion constructor (construct a node from a type T) template bin_tree::node::node (const T& value) : data {value} {} // node copy constructor template bin_tree::node::node (typename const bin_tree::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 bin_tree::node::node (typename bin_tree::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 bin_tree::node& bin_tree::node::operator= (typename const bin_tree::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 bin_tree::node& bin_tree::node::operator= (typename bin_tree::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 bin_tree::node::~node () { delete left; delete right; } // node print method (depth first traversal) template std::ostream& bin_tree::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 bool bin_tree::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 void bin_tree::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 bin_tree::bin_tree () {} // tree overloaded constructor (construct a tree from an array) template bin_tree::bin_tree (const T arr[], const size_t size) { for (size_t index=0; index bin_tree::bin_tree (const bin_tree& rhs) { *this = rhs; } // tree move constructor template bin_tree::bin_tree (bin_tree&& rhs): root{rhs.root} { rhs.root=nullptr; } // tree copy assignment operator overload template bin_tree& bin_tree::operator= (const bin_tree& rhs) { if (root) delete root; if (rhs.root) { root = new node {*rhs.root}; } return *this; } // tree move assignment operator overload template bin_tree& bin_tree::operator= (bin_tree&& rhs) { if (root) delete root; root=rhs.root; rhs.root=nullptr; return *this; } // tree destructor template bin_tree::~bin_tree () { clear(); } // tree print method (depth first traversal) template std::ostream& bin_tree::depth_first_print(std::ostream& os) const { return root ? root->depth_first_print (os) : os << "{empty}"; } // tree clear method template void bin_tree::clear () { delete root; root = nullptr; } // tree insertion method template void bin_tree::insert (const T& value) { if (!root) root = new node {value}; else root->insert (value); } // tree exists method template bool bin_tree::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: "; bin_tree a {}; // {} is implied if omitted std::cout << "a: " << a << std::endl; std::cout << " Test overloaded constructor: "; bin_tree b {arr, 10}; std::cout << "b: " << b << std::endl; std::cout << " Test tree copy constructor (c{b}): "; bin_tree c {b}; std::cout << "b: " << b << std::endl; std::cout << "c: " << c << std::endl; std::cout << " Test tree move constructor (d{move(b)}): "; bin_tree d {std::move(b)}; std::cout << "b: " << b << std::endl; std::cout << "c: " << c << std::endl; std::cout << "d: " << d << std::endl; std::cout << " Test insertion into c: "; c.insert (41); std::cout << "b: " << b << std::endl; std::cout << "c: " << c << std::endl; std::cout << "d: " << d << std::endl; std::cout << " Test search: "; 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 << " Test copy assignment (c=d): "; c = d; std::cout << "b: " << b << std::endl; std::cout << "c: " << c << std::endl; std::cout << "d: " << d << std::endl; std::cout << " Test move assignment (d=move(c)): "; d = std::move (c); std::cout << "b: " << b << std::endl; std::cout << "c: " << c << std::endl; std::cout << "d: " << d << std::endl; std::cout << " Test clear method (d.clear()): "; d.clear(); std::cout << "b: " << b << std::endl; std::cout << "c: " << c << std::endl; std::cout << "d: " << d << std::endl; }

Wiki User · Answer

#include #include template class BinTree { private: template struct Node { Node* m_left; Node* m_right; T m_data; Node (const T& data): m_left (nullptr), m_right (nullptr), m_data (data) {} ~Node() { delete m_right; delete m_left; } void print () const { if (m_left) m_left->print(); std::cout << m_data << std::endl; if (m_right) m_right->print(); } Node* search (const T& data) { if (data==m_data) return this; if (datasearch(data); } else { if (m_right) return m_right->search(data); } return nullptr; } Node* insert (const T& data) { if (datainsert(data); return m_left = new Node(data); } else { if (m_right) return m_right->insert(data); return m_right = new Node(data); } return nullptr; } }; Node* m_root; size_t m_size; // count of nodes public: BinTree (): m_root (nullptr) {} ~BinTree () { delete m_root; } void print () { if (m_root) m_root->print(); } Node* search (const T& data) { return m_root ? m_root->search(data):nullptr; } Node* insert (const T& data) { return m_root?m_root->insert(data):(m_root=new Node(data)); } }; int main() { srand((unsigned)time(nullptr)); BinTree int_tree; int last = 0; for (size_t i=0; i<16; ++i) { int val = rand(); while (int_tree.search(val)!=nullptr) val = rand(); int_tree.insert (val); last = val; } int_tree.print(); for (size_t i=0; i<16; ++i) { int val = rand(); if (int_tree.search(val) != nullptr) std::cout << "The value " << val << " exists! "; else std::cout << "The value " << val << " does not exist! "; } if (int_tree.search(last) != nullptr) std::cout << "The value " << last << " exists! "; else std::cout << "The value " << last << " does not exist! "; }

Wiki User · Answer

The following program makes use of a binary search tree to store integers. The program generates 10 random numbers which are then inserted into the tree. it then generates random numbers until it locates three which are in the tree, and three which are not in the tree. #include #include class tree { private: struct node { node(int num): data(num), left(NULL), right(NULL) {} ~node(){ delete(left); delete(right); } int data; node* left; node* right; void insert(int num) { if( numinsert(num); } else { if( !right ) right = new node(num); else right->insert(num); } } void print() { if( left ) left->print(); std::coutinsert(num); } void print() { if( m_root ) { std::cout

Wiki User · Answer

Consider a binary tree with node structure as follows:typedef struct node{

int data;

node *left, *right;//where the left and right refer to the left and right child of the tree

}node;

There are three types of binary tree traversal. Their order of traversal for a tree with the above node structure would be:

1. Inorder traversal - left child, node, right child

The code for this would be like:

void inorder( node *temp){

if( temp != NULL){

inorder(temp->left);

printf("%d\t", temp->data);

inorder(temp->right);

}

2. Preorder Traversal - node, left child, right child

void preorder( node *temp){

if( temp != NULL){

printf("%d\t", temp->data);

preorder(temp->left);

preorder(temp->right);

}

3. Postorder Traversal - left child, right child, node

void postorder( node *temp){

if( temp != NULL){

postorder(temp->left);

postorder(temp->right);

printf("%d\t", temp->data);

}

The functions are initially called by passing the root.

For other node structure, the basic traversal remains the same, only change takes place in the printing of the data. You can use printf and scanf in c++. Just remember to include cstdio library. The above codes will thus work both in c and c++.

Wiki User · Answer

The best way to imagine a balanced binary search tree is with a sorted array. When searching for a value, you start in the middle of the array. If the middle element is equal to the value you seek, you're done. If the value is less than the middle element, you start a new search using the left portion of the array, otherwise you use the right portion of the array, starting with the middle element. Thus every time you fail to find the value, you reduce the number of remaining elements you need to search by half. If you end up searching an array of less than 2 elements, the value does not exist. This is known as a depth first search and is the fastest way to search a sorted array.

A balanced binary search tree is similar to a normal binary search tree except that nodes are added according to depth-first search. Thus the middle element forms the root, while its left node is the middle element of the lower elements, and the right node is the middle element of the upper elements. Repeating this process for each node gradually builds the balanced tree.

Balanced trees are identified by the fact that all the leaf nodes reside on no more than two levels of the tree (the ideal is to have all leafs on one level). This ensures the depth of search to the left and right of any node is as close to equal as possible, thus ensuring optimal search times.

Building a balanced search tree from a normal binary search tree is a complex process, thus you will typically build the entire tree first and then recursively rotate the nodes to create a balanced tree. However, if new nodes are subsequently inserted into the balanced search tree, you must re-rotate all the nodes upon each insertion, which naturally increases insertion time. A simpler approach is to use a self-balancing tree, such as a red/black tree. Nodes must still be rotated upon each insertion but the algorithm is greatly simplified.

What is balanced binary search tree in c plus plus?

Add your answer:

Which is faster binary tree or binary search tree?

What is the difference between extended binary tree and a binary search tree?

IS AVL-Tree IS binary tree?