Assume that a Binary Search Tree is constructed by repeatedly inserting exact values in to the tree. Argue that the number of nodes examined in searching for a value in the tree is one + the number of nodes determined when the value was first inserted in to the tree

Let us take an element x to insert in a binary search tree. So for inserting the 

 

 

element x first at level 0,then level 1 and assume upto level (d-1). While determine at (d-1) level, x may have less or more in comparison to element at (d-1). The we enter x either left or right. In both cases no of determined code will be d. Now Assume we require to search for x, this time again traverses the similar path as we traverse. Whereas inserting the element, we stop at (d-1) the level but for searching we determine node at dth level also i.e. the node  having x. Thus number of node determine while inserting are d while     incase  of searching it is d+1 i.e. one more than whereas inserting, as the result.

 

 

Posted Date: 5/3/2013 3:40:58 AM | Location : United States

Ask an Expert

Related Discussions:- Binary search tree is constructed by repeatedly, Assignment Help, Ask Question on Binary search tree is constructed by repeatedly, Get Answer, Expert's Help, Binary search tree is constructed by repeatedly Discussions

Write discussion on Binary search tree is constructed by repeatedly
Your posts are moderated

Write your message here..

Related Questions

Data structure, convert BST into sorted doubly linked list convert BST into sorted doubly linked list

Define name mangling in c++??, A: The procedure of encoding the parameter t... A: The procedure of encoding the parameter types along with the function/method name into a unique name is called as name mangling. The inverse procedure is called demangling. F

How do i allocate multidimensional arrays by new?, How do I allocate multid... How do I allocate multidimensional arrays by new? A: There are several ways to do this, based on how flexible you wish the array sizing to be. On one acute, if you know all the

Monolithic stucture, what is a monolithic structure? what is a monolithic structure?

#include , volume of a sphere volume of a sphere

#accept 3 digit number, Write a ''C'' program to accept any 3 digit integer... Write a ''C'' program to accept any 3 digit integer number from the keyboard and display the word equivalent representation of the given number

Destructor , How can I handle a destructor that fails? Need help please pro... How can I handle a destructor that fails? Need help please provide example also.

Heating and thermodynamic, i want software to calculate heating or use ther... i want software to calculate heating or use thermodynamic equation , pleas help me

C programing forcalculating savings of an employee, c programing forcalcula... c programing forcalculating savings of an employee

Explain the function of five elements that are on a, explain the function o... explain the function of five elements that are found on a motherboard#