Binary Search Tree 
Author Message
 Binary Search Tree

A sorted array of integers containing 20 elements, what is the maximum
number of search tests that would be
done, using a binary search techique on the array to find a particular
element.

am I right if I use this formular??    log2n

if so, how to calculate??

if not, can you tell me which formular should I use ?? and how to calculate
it??

thanks ..



Fri, 15 Sep 2000 03:00:00 GMT  
 Binary Search Tree

Quote:

> A sorted array of integers containing 20 elements, what is the maximum
> number of search tests that would be
> done, using a binary search techique on the array to find a particular
> element.

> am I right if I use this formular??    log2n
> if so, how to calculate??

Yep, you're right, and an outline of the proof goes something
like this:

let S(n) be the number of search tests needed to find an element
in a sorted list of n elements. Clearly S(1) =1

If you look at element n/2, three alternatives are possible:
- it's the element your're looking for;
- it's larger than the element you're looking for; or,
- it's smaller than the element you're looking for.

If the second or third alternative apply, check the appropriate
half of the list of elements. This yields:

        S(n)= 1+S(n/2) -->
        S(n)= 1+1+S(n/4) -->
        S(n)= 1+1+ ... +1+S(1)= 2logn

does this clarify things a bit?

kind regards,




Sat, 16 Sep 2000 03:00:00 GMT  
 Binary Search Tree

(PART A)

If the input values given are :

                       12, 23, 4, 74, 9, 15, 17

Please 'draw' the resulting binary search tree, if each of the input values
is assigned to the'data' field of
a new BTREENODE data item, and the data items are inserted in the order
shown above.

typedef struct btreenode {
   int data;
   struct btreenode *left, *right

Quote:
}

(PART B)

Given the resulting tree from part a, what would the following print_tree
function output if called with 'root' ptr
of the tree??

void print_tree(BTREE root)
{
   if (root->left!=NULL) print_tree(root->left);
   if (root->right!=NULL) print_tree(root->right);
   printf("%d\n", root->data);

Quote:
}

If you guyz know the answer, please write me back .. thanks


Sat, 16 Sep 2000 03:00:00 GMT  
 Binary Search Tree

[yet another homework assignment that I mersifully snipped]

Hey Keith,

Would you please stop posting all your homework to this group.
We try to discuss C here, help other with their specific problems,
but do not provide homework solutions for lazy pupils.

Homework has a reason, and that's not to find somebody who'll do
it for you. You are supposed to *LEARN* something !

Stephan
(initiator of the campaign against grumpiness in c.l.c)



Mon, 18 Sep 2000 03:00:00 GMT  
 
 [ 5 post ] 

 Relevant Pages 

1. Binary Search Trees

2. Binary Search Trees

3. Binary search tree

4. binary search tree problem

5. Binary Search Tree using dynamic memory allocation (URGENT request for example)

6. What is the algorithm of binary search tree?

7. Binary search tree doesn't work properly

8. Adding to a binary search tree

9. Help... Binary Search Tree

10. algorythm to balance a binary search tree

11. Binary search trees

12. Binary Search Trees

 

 
Powered by phpBB® Forum Software