0
How do you write c plus plus program to insert an element into a binary search tree?
Wiki User
∙ 9y ago
Binary Search is an algorithm that finds an element by successively halving the search space. Typically, pointers are used, one for the beginning of an array, one for the end. Then a midpoint pointer is chosen, and a test is performed. You either find the element, or you discover that the target element is before or after the midpoint. You then adjust either the start pointer or the end pointer and you iterate. When you reach the point where the pointers are out of order, you conclude that the target is not found, and you also know where to insert it. Binary Search is best implemented with an ordered array, because you want to make "random" access to each element. The problem with arrays is that they are typically fixed size, and must be dynamically adjusted when they need to grow, a potentially "expensive" operation. You can also implement a Binary Tree, but there is cost in development and processing. Even trees have issues because, when inserting and deleting elements, you must use a rebalancing algorithm, otherwise the tree might degrade to a linked list, which is not efficient when used as a search space. In C++, it is possible to declare and define a class of elements that you can add to, subtract from, and search. If you do this correctly, you could start with a static or dynamic array, and then upgrade if need be to a binary tree, and then upgrade if need be to a balanced binary tree, all the while without requiring change to the public interface. That is perhaps the most important value of an Object Oriented Language such as C++.
Wiki User
∙ 14y ago
Wiki User
∙ 9y ago#include<iostream>
template<typename T>
struct node
{
T data;
node* left {nullptr};
node* right {nullptr};
node (const T& value): data (value) {}
~node () { delete left; delete right; }
void 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);
}
}
};
template<typename T>
struct bin_tree
{
node<T>* root {nullptr};
~bin_tree () { delete root; }
void insert (const T& value)
{
if (!root)
root = new node<T> (value);
else
root->insert (value);
}
};
template<typename T>
std::ostream& operator<< (std::ostream& os, const node<T>& n)
{
if (n.left) os << (*n.left);
os << n.data << ' ';
if (n.right) os << (*n.right);
return os;
}
template<typename T>
std::ostream& operator<< (std::ostream& os, const bin_tree<T>& t)
{
if (t.root)
return os << (*t.root);
return os;
}
int main()
{
int arr[10] = {42, 56, 30, 5, 12, 60, 40, 8, 1, 99};
bin_tree<int> tree;
for (size_t e=0; e!=10; ++e)
tree.insert (arr[e]);
std::cout << tree << std::endl;
}
Wiki User
∙ 9y agoBinary search can be achieved with a sorted array. By recursively checking the middle element of the array, you can reduce the array by half until you either locate the element or you have an empty an array. This achieves the same end as a binary tree but with less memory overhead. The middle element represents the root, with its left node pointing to the middle element of the left portion of the array and the right node pointing to the middle element of the right portion of the array.
Wiki User
∙ 9y ago#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;
}
Wiki User
∙ 11y agoLinear search involves scanning through the entire array and finding the element. Here is the code:
#include
using namespace std;
int main(){
int i, arr[100], n, elem,pos, flag = 0;
cout<<"Enter the number of elements:\t";
cin>>n;
cout<<"Enter the array elements:\t";
for( i=0; i cin>>arr[i]; cout<<"Enter the element to be searched:\t"; cin>>elem; for( i=0; i if( arr[i] == elem){ flag = 1; pos = i; } } if( flag) cout<<"Element was at position "< else cout<<"Element was not found in the array"< return 0; }
Wiki User
∙ 9y ago#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
{
return t.depth_first_print (os);
}
// node default/conversion constructor (construct a node from a type T)
template
bin_tree
: data {value}
{}
// node copy constructor
template
bin_tree
: 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
: 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
{
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
{
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
{
delete left;
delete right;
}
// node print method (depth first traversal)
template
std::ostream& bin_tree
{
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
{
return value == data ? true :
value < data && left ? left->exists (value) :
value > data && right ? right->exists (value) :
false;
}
// node insertion method
template
void bin_tree
{
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
{}
// tree overloaded constructor (construct a tree from an array)
template
bin_tree
{
for (size_t index=0; index insert (arr[index]); } // tree copy constructor template bin_tree { *this = rhs; } // tree move constructor template bin_tree { rhs.root=nullptr; } // tree copy assignment operator overload template bin_tree { if (root) delete root; if (rhs.root) { root = new node {*rhs.root}; } return *this; } // tree move assignment operator overload template bin_tree { if (root) delete root; root=rhs.root; rhs.root=nullptr; return *this; } // tree destructor template bin_tree { clear(); } // tree print method (depth first traversal) template std::ostream& bin_tree { return root ? root->depth_first_print (os) : os << "{empty}"; } // tree clear method template void bin_tree { delete root; root = nullptr; } // tree insertion method template void bin_tree { if (!root) root = new node {value}; else root->insert (value); } // tree exists method template bool bin_tree { 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 std::cout << "a: " << a << std::endl; std::cout << "\nTest overloaded constructor:\n"; bin_tree std::cout << "b: " << b << std::endl; std::cout << "\nTest tree copy constructor (c{b}):\n"; bin_tree std::cout << "b: " << b << std::endl; std::cout << "c: " << c << std::endl; std::cout << "\nTest tree move constructor (d{move(b)}):\n"; bin_tree 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; }
Add your answer:
Earn +20 pts
Best first search program in c?
The best search programs to attempt writing in C are the following: Linear search (simplest), Binary search (faster) Hash search (fastest).
Which are the searching algorithm always compare the middle element with the searching elements in the given array?
binary search system
What assumption about the list is made when binary search is conducted?
Binary search requires that the list be in search key order.
What is the binary search tree worst case time complexity?
Binary search is a log n type of search, because the number of operations required to find an element is proportional to the log base 2 of the number of elements. This is because binary search is a successive halving operation, where each step cuts the number of choices in half. This is a log base 2 sequence.
Why would you write a program using array processing linear search and binary search of an array?
A linear search is effective when the order of elements in an array are not sorted by the value you are looking for. A binary search is effective when the order of elements is sorted by the value you are looking for.Linear search sample data: 8 3 9 12 4 10 38 2 1 93 56 34Binary search sample data: 1 2 3 4 8 9 10 12 34 38 56 93In the first set of data, unsorted data cannot be searched using binary search. To find the value 38, a program must go through each element until it locates the 7th element; this is a total of 7 iterations. This method is effective when data is constantly being added and removed, and the overhead of a sorting algorithm would be less efficient than a binary search.In the second set of data, the value 38 can be found by binary search. In the first iteration, a binary halfway point is found (we will choose element 6). Since 9 is less than 38, we know we need to go up. There are six remaining values, so we look at the 9th element (starting from the 6th element, there are six more, so we go half-way, 3 more, a total of 9). Here, we see the value is 34, still less than 38. There are three values remaining, so we go up 2 more. For the third iteration, the value is 56, which is more than our target of 38. Since we advanced 2 last time, we will decrease by 1 this time, and our fourth iteration will find the value 38.As a matter of fact, in this data set, we will always find our answer in at most 4 iterations, while in the linear search, only the first 4 elements have a chance of being more efficient than the binary search. The problem then comes to down to if the sorting and binary search combined is faster than the linear search. For large data sets that are mostly static, binary searching is preferred. For rapidly changing data sets that would need constant sorting, a linear search may be preferred.Note that if the data insertion algorithm maintains the sort order (by inserting each element at the correct index in memory), binary searching will likely be faster in the majority of cases. One can use a binary search for data insertion points, keeping the cost of data insertion minimized (but not as efficient as simply appending to the end) while maximizing search capabilities.
Does binary search tree take much time than the list to delete or insert an element?
No. Binary search tree will take less time to delete or insert an element. While deleting from list, more time will be required to search for the element to be deleted but BST will work faster if the no. of elements are more. Plus it depends upon which element is to be deleted and where the element is to be added. But the average time to perform these operations will be less in BST as compared to lists
How can one perform a binary search?
One can perform a binary search easily in many different ways. One can perform a binary search by using an algorithm specifically designed to test the input key value with the value of the middle element.
Where to insert an element in binary tree if two nodes are equal in size?
Same as if two nodes are NOT equal in size. Size of nodes has nothing to do where to insert a new element. The insertion should be applying the search algorithm of that binary tree (so the new inserted element maybe found later). For balanced (in size) binary tree, the above still applied, because 50% of the time the tree is unbalanced (a binary tree with even number of elements is not balanced). Plus, those 2 nodes, may not be the "right" and "left" nodes of a given one, so 2 nodes equals in size has nothing to do with the way the elements being inserted into a binary tree.
How do you compare elements of a linked list. e.g an element should not be input when the same value already exists..?
In a linked list, if you want to prevent elements with the same key from being inserted twice, then you need to search the list prior to insert for that key. Iterate through the list, comparing elements with the element being inserted. If you encounter end-of-list, then insert the new element, otherwise throw whatever exception or indicate whatever error desired. Note that this is a full linear search. Statistically, if an element is to be found, it will be found at the halfway point, assuming uniformly random distribution of data. In the worst case, if the element is not found, it will always take a full search to prove that. This is not a very efficient use of a linked-list. It would be better to use some kind of ordered list, perhaps a dynamic array with binary search, or a balanced binary tree, which has similar search performance but one with the most cost to design and implement. You could keep the linked list in order, by inserting each element before the element that has higher key value. This would reduce search time to half, but that is still proportional to list size, not log 2 of list size like binary search is. Sorry, every answer has its tradeoffs.
Best first search program in c?
The best search programs to attempt writing in C are the following: Linear search (simplest), Binary search (faster) Hash search (fastest).
Which are the searching algorithm always compare the middle element with the searching elements in the given array?
binary search system
When is it not recommended to perform the operation of binary search?
In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input "key") in an array sorted[1][2] into order on the values of the key. At each stage, the algorithm compares the sought key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index is returned. Otherwise, if the sought key is less than the middle element's key, then the algorithm repeats its action on the subarray to the left of the middle element or, if the input key is greater, on the subarray to the right. If the array span to be searched is reduced to zero, then the key cannot be found in the array and a special "Not found" indication is returned.A binary search halves the number of items to check with each iteration, so locating the an item (or determining its absence) takes logarithmic time. A binary search is a dichotomic divide and conquer search algorithm.Next AnswerA binary search method requires that the list of items being search should be sorted in ascending (or descending) order. If the search list is not sorted, the binary search method will not work and other search methods will be needed.
How you can run a c program in Linux 2.4?
if it is n already compiled binary program: ./program-name if it is a code, gcc program-code.c -o program-name if gcc is not installed, on debian: search for a deb package and install it, or, apt-get install gcc on redhat: search for an rpm package and install it.
What assumption about the list is made when binary search is conducted?
Binary search requires that the list be in search key order.
What is the binary search tree worst case time complexity?
Binary search is a log n type of search, because the number of operations required to find an element is proportional to the log base 2 of the number of elements. This is because binary search is a successive halving operation, where each step cuts the number of choices in half. This is a log base 2 sequence.
Implementation of binary search algorithm using ASM assembler in 8086?
Hi, I hope this is useful http://www.indiastudychannel.com/projects/2748-Assembly-language-program-for-Binary-search.aspx good luck!
What is the output of C programming of binary searching?
The output of a binary search routine is either (usually) the address of the element that matched the search term, or, if there was no match, the address of where the new element should be placed. Of course, this means that there are two outputs, one, an address, and two, whether or not the search term was found; which means that a single valued function will not suffice - it is necessary that one of the parameters be an address, perhaps of the flag variable.
