Can i use binary search tree in an unordered array?

Hi there,

I have unordered array content and i want to have a search on that. So is it true that i have to sort my array first, "before" populating the tree?

Regards.
LVL 12
jazzIIIloveAsked:
Who is Participating?
 
CEHJConnect With a Mentor Commented:
It is true. Binary ordering/searching functionality has to be performed on sorted objects
0
 
d-glitchConnect With a Mentor Commented:
No.  In a binary search, every test should reduce the search range by half.
If the array is unordered, your test doesn't tell you which way to go.
0
 
AndyAinscowConnect With a Mentor Freelance programmer / ConsultantCommented:
I agree with CEHJ - yes, you need to sort it first.
0
Cloud Class® Course: Amazon Web Services - Basic

Are you thinking about creating an Amazon Web Services account for your business? Not sure where to start? In this course you’ll get an overview of the history of AWS and take a tour of their user interface.

 
d-glitchCommented:
I agree with CEHJ as well.

The No in my comment refers to the question in the title.
0
 
jazzIIIloveAuthor Commented:
Thanks, but a question,
http://www.youtube.com/watch?v=a0o7AWhKKCM
 In 0.06 of the video, the elements in the array are not presorted. I am a little confused.

Regards.
0
 
CEHJConnect With a Mentor Commented:
The video i see is solely devoted to showing the ordering of the numbers
0
 
ValeriConnect With a Mentor Commented:
This video shows only the right way to build the binary tree, nothing more! :-)
You dont need to order the source array at the begining, but it's good to do that in order to choose the right element to put as a root of the tree. In the video root element "5" is chosen as a root "randomly" but it is very important because the rest 6 elemnts are : 3 bigger than 5 and 3 less than 5, so the tree is BALANCED by default.
If your array is not sorted at the beginning, you will be able to build the tree, but after that you need to balance it, in orer to have best performance for search operation.
see this: http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
Btw, Java offers implementatio of this structure, but yes, it's good to know how it works.
0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

All Courses

From novice to tech pro — start learning today.