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,

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

 Page 1 of 1 [ 5 post ]

Relevant Pages