We help IT Professionals succeed at work.

building a binary search tree

ervinloh
ervinloh asked
on
Medium Priority
397 Views
Last Modified: 2008-02-01
does anyone knows how to build a binary seach tree using visual basic? any sample codes or tutorials are appreciated.

Comment
Watch Question

May i ask why u are trying to build a binary search tree? If it is to increase search speeds by being able to do a binary search, then all you need to do is to sort that data, and then u can binary search it.

If so let me know  and i'll whip up the code for doing a binary search.

Regards,

CERTIFIED EXPERT
Top Expert 2014
Commented:
A crude approximation would require an array whose size is a power of 2.  In the following example, your starting location is (0).

Dim strBinTree(-16 To 16) As String
Dim intLowerLimit as Integer
Dim intUpperLimit as Integer
Dim boolFound as Boolean
intLowerLimit = LBound(strBinTree)
intUpperLimit = UBound(strBinTree)
intSearch = 0
Do
  Select Case strSearch
    Case < strBinTree(intSearch)
      intUpperLimit = intSearch - 1
    Case < strBinTree(intSearch)
      intLowerLimit = intSearch + 1
    Case = strBinTree(intSearch)
      boolFound = True
      Exit Do
  End Select

Loop Until boolFound Or (intUpperLimit - intLowerLimit <=1)
If boolFound Then
  'process found condition
Else
  'process not found condition
End If
Ok here is the code i whipped up, with comments just to guide u thru it.
As Previously Mentioned, the data u r searching needs to be sorted for the binary searh to work.
So as an example i have used a list type control with sorted = true
The general idea is this: you keep slicing your data up into sub trees depending on whether the middle value is greater or lesser (alphabetically).
If the searchstring is alphabetically greater than the middle then you know that you need to search the right half of the original tree.
So then you end up with another set of 2 subtrees below the original right tree
etc, and u keep doing this until the searchstring is found.

You do not need a list to the power of 2 items.

The above code as the author suggests is crude.

Private Function BinarySearch(SearchString As String, SearchControl As Control) As Integer

Dim intLeftPointer As Integer
Dim intRightPointer As Integer
Dim intMiddle As Integer
Dim intResult As Integer
Dim blFound As Boolean

On Error Resume Next

intLeftPointer = 0
intRightPointer = SearchControl.ListCount - 1

Do While blFound = False
  intMiddle = (intLeftPointer + intRightPointer) \ 2
  intResult = StrComp(SearchString, SearchControl.List(intMiddle), vbTextCompare)
  If intResult = 0 Then
    BinarySearch = Middle
    blFound = True
  Else
    If intResult = 1 then
       intLeftPointer = intMiddle + 1
    Else
       intRightPointer= intMiddle - 1
    End If
  End If
Loop

End Function

Cheers,

CERTIFIED EXPERT
Top Expert 2014

Commented:
I appologize for omitting the calculation of the next intSearch value (= (intUpperLimit - intUpperLimit) \2) in the loop.  If you tried it, it would always check the same item in the array, never terminating (oops).

Also, the second "Case < strBinTree(intSearch)" should actually be "Case > strBinTree(intSearch)".  I forgot to edit the line after my copy/paste.

Although it is not necessary to have a power of 2 for the upper and lower bounds of the array, it is easier to visualize for most programmers.  Also, you get better performance from a balanced tree than an unbalanced tree.

I should warn you that cybermoonlight's code (as shown) will not stop looping if the search string is not in the array.
oops thanks for pointing that out..so instead of
do while blfound = false
change it 2:
do while blFound = False OR i >= searchcontrol.listCount -1
i = i +1

regards,
And excuse me, but a balanced tree will not give improved performance !!!
sorry once again. that was
do while blFound=False And i<= searchControl.listcount - 1

I must have been tired

Regards,
CERTIFIED EXPERT
Top Expert 2014

Commented:
I still don't think the Do While construct will terminate properly, since the intLeftPointer and intRightPointer values are approaching each other, not listcount-1.

It will terminate after listcount-1 iterations, but the problem is supposed to be a binary, not a "linear" search.
i'm really not on the ball today am i!!
you are correct, the search is of course binary..but becasue of the loop, when the whole tree has been searched it will continue until listcount- 1..very bad indeed.
instead you would check for blfound= fasle or i<= log2Listcount-1

Sorry once again
ok once more..
i wish EE had a way to edit comments!

right so
this is how you would initiate the loop

Do while blFound = False And i <= sqr(SearchControl.ListCount) + 1
i = i + 1

There you have it, finally a perfect sample of a binary search.

Regards,
Mike McCrackenSenior Consultant
CERTIFIED EXPERT
Most Valuable Expert 2011
Top Expert 2013

Commented:
great..EE is really annoying me ! :(

Author

Commented:
hello everbody!

it seemed that you guys are giving me a binary search function. i need to build a binary search tree and not binary search.

the reason for building a binary search tree is not for increasing the speed of searching. this binary search tree contains special nodes that will be used by a graph for processing. we have an priority engine over here. we'll need to build a tree so that we knows which are the priorities that we are going to process during run time.
CERTIFIED EXPERT
Top Expert 2014

Commented:
check out a binary tree class download
http://www.freevbcode.com/ShowCode.Asp?ID=1602

or a balanced binary tree class download
http://www.freevbcode.com/ShowCode.Asp?ID=3309

or a self-balancing AVL Tree Container Class
http://www.vbwm.com/art_2001/avltree08/

If you want to develop your own binary tree object that you can see, use the treeview control (Windows Common Controls component).  Under the root, add a left child and a right child.  You would then add left and right children as needed.  You could use the .Child and .FirstSibling and .LastSibling to traverse the tree.  It would also be available for user editing.
ADMINISTRATION WILL BE CONTACTING YOU SHORTLY.  Moderators Computer101 or Netminder will return to finalize these if still open in seven days.  Please post closing recommendations before that time.

Question(s) below appears to have been abandoned. Your options are:
 
1. Accept a Comment As Answer (use the button next to the Expert's name).
2. Close the question if the information was not useful to you, but may help others. You must tell the participants why you wish to do this, and allow for Expert response.  This choice will include a refund to you, and will move this question to our PAQ (Previously Asked Question) database.  If you found information outside this question thread, please add it.
3. Ask Community Support to help split points between participating experts, or just comment here with details and we'll respond with the process.
4. Delete the question (if it has no potential value for others).
   --> Post comments for expert of your intention to delete and why
   --> YOU CANNOT DELETE A QUESTION with comments; special handling by a Moderator is required.

For special handling needs, please post a zero point question in the link below and include the URL (question QID/link) that it regards with details.
http://www.experts-exchange.com/jsp/qList.jsp?ta=commspt
 
Please click this link for Help Desk, Guidelines/Member Agreement and the Question/Answer process.  http://www.experts-exchange.com/jsp/cmtyHelpDesk.jsp

Click you Member Profile to view your question history and please keep them updated. If you are a KnowledgePro user, use the Power Search option to find them.  

Questions which are LOCKED with a Proposed Answer but do not help you, should be rejected with comments added.  When you grade the question less than an A, please comment as to why.  This helps all involved, as well as others who may access this item in the future.  PLEASE DO NOT AWARD POINTS TO ME.

To view your open questions, please click the following link(s) and keep them all current with updates.
http://www.experts-exchange.com/questions/Q.20097814.html
http://www.experts-exchange.com/questions/Q.20157997.html
http://www.experts-exchange.com/questions/Q.20172047.html
http://www.experts-exchange.com/questions/Q.20182228.html
http://www.experts-exchange.com/questions/Q.20239927.html
http://www.experts-exchange.com/questions/Q.20260177.html
http://www.experts-exchange.com/questions/Q.20282477.html
http://www.experts-exchange.com/questions/Q.20282802.html


To view your locked questions, please click the following link(s) and evaluate the proposed answer.
http://www.experts-exchange.com/questions/Q.20113693.html
http://www.experts-exchange.com/questions/Q.20199046.html

*****  E X P E R T S    P L E A S E  ******  Leave your closing recommendations if this item remains inactive another seven (7) days.  If you are interested in the cleanup effort, please click this link http://www.experts-exchange.com/jsp/qManageQuestion.jsp?ta=commspt&qid=20274643 
POINTS FOR EXPERTS awaiting comments are listed here -> http://www.experts-exchange.com/commspt/Q.20277028.html
 
Moderators will finalize this question if in @7 days Asker has not responded.  This will be moved to the PAQ (Previously Asked Questions) at zero points, deleted or awarded.
 
Thank you everyone.
 
Moondancer
Moderator @ Experts Exchange

Explore More ContentExplore courses, solutions, and other research materials related to this topic.