binary search and search using binary tree

This is a discussion on binary search and search using binary tree within the C++ Programming forums, part of the General Programming Boards category; I have to implement binary search and search with binary tree. Suppose I have an array to be searched for ...

  1. #1
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712

    binary search and search using binary tree

    I have to implement binary search and search with binary tree.

    Suppose I have an array to be searched for value (for example int numbers to avoid complications).Binary search is not a problem. With binary search array must be first sorted,so for example when I
    have an array {2 1 4 8 1 5}, I first call some function for sorting. After that I have
    {1 1 2 4 5 8}. Then I call binary search that divides array into halfs until find
    specific element (if element exists).
    But, what is search with binary tree? I suppose first I have to create binary tree from
    array members. For example using some function Insert.
    Code:
    for(int i=0;i<length_array;i++)
    	Insert(array[i]);
    After that I have following structure:

    2

    1 4
    1 8 5
    And then I should use some function Find() to find element in the tree.
    If this is search with binary tree?
    Assumption is that I have to sort unsorted array. This way will work, but I wonder if
    this really search with binary tree. Significant amount of time is lost while creating
    tree calling Insert(), and after that, calling function Find is necessary.
    All advices are welcome
    Thanks

  2. #2
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    I don't know exactly what means searching using binary tree when I have unsorted array,
    maybe I have to create binary search tree first and then search for desired element, something like this:
    Code:
    #include <iostream>
    using namespace std;
    
    typedef struct Node
    {
    	int data;
    	struct Node* left;
    	struct Node* right;
    }node;
    node* create_tree(int[],int);
    void insert(node**,int);
    int *binary_tree_search(node*,int);
    void Show(node*);
    
    int main()
    {
    	int array[]={6,7,3,1,2,5,8,9,4,10};
    
    	int *x=binary_tree_search(create_tree(array,10),1);
    	Show(create_tree(array,10));
    	if(!x)
    		cout<<"Element not found!";
    	else
    		cout<<"element is "<<*x;
    }
    
    node* create_tree(int arr[],int len)
    {
    	node* head=new node();
    	head=0;
    	for(int i=0;i<len;i++)
    		insert(&head,arr[i]);
    	return head;
    }
    void insert(node**head,int data)
    {
    	if(!*head)
    	{
    		*head=new node;
    		(*head)->data=data;
    		(*head)->left=0;
    		(*head)->right=0;
    		return;
    	}
    	if((*head)->data>data)
    		insert(&(*head)->left,data);
    	else
    		insert(&(*head)->right,data);
    }
    int *binary_tree_search(node* head,int dat)
    {
    
    	if(!head)
    		return 0;
    	if(head->data==dat)
    		return &(head->data);
    	else
    	{
    		if(head->data>dat)
    			return binary_tree_search(head->left,dat);
    		else
    			return binary_tree_search(head->right,dat);
    	}
    	return 0;
    }
    void Show(node* root)
    {
    	if(root)
    	{
    		Show(root->left);
    		printf("%d ",root->data);
    		Show(root->right);
    	}
    }
    This seems to be unefficient because of allocating memory and creating tree.
    Maybe search array with binary tree is not about creating tree at all,but
    rearanging array to look like binary tree (!?!)
    Please help, I don't know what to do else.

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >But, what is search with binary tree?
    Just what you would think:
    Code:
    bool bt_search ( bt_node *root, int key )
    {
      if ( root == NULL )
        return false;
      else if ( key < root->data )
        return bt_search ( root->left, key );
      else if ( key > root->data )
        return bt_search ( root->right, key );
      else
        return true;
    }
    >This way will work, but I wonder if this really search with binary tree.
    Yes, it will work fine. But be sure not to sort the array before inserting the items into the tree. If you do you'll build a degenerate tree that gives you linear search times.

    >Significant amount of time is lost while creating tree calling Insert()
    Not as much as you would think. Building a binary search tree from a set of data is a useful technique for sorting and searching.
    My best code is written with the delete key.

  4. #4
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >This seems to be unefficient because of allocating memory and creating tree.
    Don't worry about it until you've profiled it and know that it is inefficient. Programmer's intuition is notoriously bad in matters of performance.

    >Maybe search array with binary tree is not about creating tree at all
    Yes, in this case it is.

    >but rearanging array to look like binary tree (!?!)
    What do you think binary search is?
    My best code is written with the delete key.

  5. #5
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    So, when I have array of numbers do I have to build tree and insert elements as nodes?
    Is this this code ok?
    I'm not sure about creating tree with functions such as Insert and Find?
    How would you solve this?
    My approach is code you see.
    Please if you have time, can you comment my code?
    Other technique such binary search (after I sort an array) or simple seqential search work directly with an array, but this technique first build binary tree (left is smaller right is bigger)
    and then search through tree.
    Last edited by Micko; 03-17-2004 at 12:11 PM.

  6. #6
    Registered User
    Join Date
    Mar 2002
    Posts
    1,595
    >So, when I have array of numbers do I have to build tree and insert elements as nodes?

    Yes, see pseudo code below which is based on your code, some of which has been corrected, and which I think is a better attempt at a possible solution

    Code:
    for(int i=0; i<len; i++)
      insert(head, arr[i]); 
      return head;
    
    void insert(node* head, int _data)
      create new node
      assign _data to new node data
      assign NULL to new node pointers
    
      declare a pointer to node called currentNode
      assign head to current node
    
      
      if tree is empty
        assign new node to current node
      else
        findInsertionSpot()
    
    void findInsertionSpot(node* , node*)
          
       //now compare data in current node to data in new node
       //and insert new node at the first left or right that is NULL
    
       if currentNode data greater than newNode data
         if currentNode left is NULL
            assign new node to currentNode left
         else
            assign currentNode left to currentNode
            call findInsertionSpot() again
       else if currentNode data less than newNode data
         if currentNOde right is NULL
            assign new node to currentNOde right
         else
            assign currentNode right to currentNode
            call findInsertionSPot() again
    Last edited by elad; 03-17-2004 at 02:34 PM.

  7. #7
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    Ok, thanks.
    Just to be sure my approach is good and actually this is way how search with binary tree is implemented?
    I'm sorry if this is annoying to someone, but this is I have to learn very quickly, I'll have it on exams
    Last edited by Micko; 03-17-2004 at 02:21 PM.

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >Just to be sure my approach is good and actually this is way how search with binary tree is implemented?
    If you have some reading time, I've written a basic binary search tree tutorial in the FAQ. It should help to solidify what you already know and help you build confidence in your code.
    My best code is written with the delete key.

  9. #9
    Registered User Micko's Avatar
    Join Date
    Nov 2003
    Posts
    712
    I have read the tutorial and I must say it's pretty much clear to me.
    I got homework to implement different search methods, one of them was to implement search with binary tree in addition to binary search.
    Basic problem was how to perform search with binary tree without having binary tree at all, just an array of some type, say integeres. So what I figure out is to make binary tree from unsortzed array and then to write some function Find() to search for the desired element.
    On the other hand I had choice to sort array first and then to perform binary search (dividing into halfs) until find the desired element. I don't know what method isfaster and more optimal:
    first sort array then binary search or
    first create binary tree and then search that tree.
    My only idea was to create tree from an array. Maybe I could also permute elements in the array (not creating structure and tree), but don't know how.
    Thanks for help, especially you prelude!

  10. #10
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    >I don't know what method isfaster and more optimal
    It really depends on the data. The sorting operation could very well be comparable to building a search tree, but that isn't very likely. If new data isn't going to be inserted or deleted then a sort/binary search combination on an array would probably be the more efficient method. If you'll be inserting or removing items regularly then the cost of resorting or maintaining a sorted array could easily outweigh the cost of handling a search tree and using an explicit tree structure would be more efficient.
    My best code is written with the delete key.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Replies: 0
    Last Post: 11-04-2006, 11:07 AM
  2. Binary Search Trees Part III
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 16
    Last Post: 10-02-2004, 04:00 PM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 09:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 10:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21