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

Lua and C++ sprite animation, How would I use variables of a C++ object wit... How would I use variables of a C++ object within a Lua function, and then call the Lua function from C++ code?

Why php is also known as scripting language, Why PHP is also known as scrip... Why PHP is also known as scripting language? PHP is fundamentally a general purpose language, which is used to write scripts. Scripts are normal computer files which comprises

Program to calculate pie, This problem familiarizes you with using random n... This problem familiarizes you with using random numbers in C++. The program is to compute a good approximation of p using a simulation method called "Monte Carlo". The following fi

Described the order that objects in an array is destructed?, Described the ... Described the order that objects in an array is destructed?

Need help, how to make basics strong and best logic skills what are the bes... how to make basics strong and best logic skills what are the best way to be a expert programmer ? what counts a lot knowledge or practice?

ASCII, A string S is said to be "Super ASCII", if it contains the character... A string S is said to be "Super ASCII", if it contains the character frequency equal to their ascii values. String will contain only lower case alphabets (''a''-''z'') and the asci

C++ code??, Write a program to find the area under the curve y = f(x) betwe... Write a program to find the area under the curve y = f(x) between x = a and x = b, integrate y = f(x) between the limits of a and b. The area under a curve between two points can b

Solve, solve for radius(R) of a circle of its area is to be inputted by a u... solve for radius(R) of a circle of its area is to be inputted by a user. also display compute the circle diameter hint: area= pir21 pi=2.1416

Dynamic constructor, dynamic initialization of object using constructor in ... dynamic initialization of object using constructor in C++

Usb photobackup, Project Description: Prepare software that will work with ... Project Description: Prepare software that will work with our USB hardware that easily lets you backup all the pictures in your computer into the USB stick in one single step. Once