3 Replies - 955 Views - Last Post: 17 January 2009 - 05:40 AM Rate Topic: -----

#1 KaloyanBeshev  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 17-January 09

Some help with binary search trees

Posted 17 January 2009 - 03:55 AM

Hi all,

First of all - I am new here, so sorry for any mistakes I might have made while posting a new topic.
So, down to business: I just can't find enought info about those search trees or how to wright one :blink: . Could you give me some tips on how and where to start :) ? I can't seem to write my last homework for this semester and there is no one that can help me :( . So, any ideas where should I start, but the explanation should be made for "idiots"... in other words - step by step to help me write my first tree :D ?

Thank you in advance for the help.

Is This A Good Question/Topic? 0
  • +

Replies To: Some help with binary search trees

#2 KaloyanBeshev  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 2
  • Joined: 17-January 09

Re: Some help with binary search trees

Posted 17 January 2009 - 03:56 AM

Hi all,

First of all - I am new here, so sorry for any mistakes I might have made while posting a new topic.
So, down to business: I just can't find enought info about those search trees or how to wright one :blink: . Could you give me some tips on how and where to start :) ? I can't seem to write my last homework for this semester and there is no one that can help me :( . So, any ideas where should I start, but the explanation should be made for "idiots"... in other words - step by step to help me write my first tree :D ?

Thank you in advance for the help.

P.S.: Do you know a program in c++ for creating a binary search tree?

This post has been edited by KaloyanBeshev: 17 January 2009 - 04:14 AM

Was This Post Helpful? 0
  • +
  • -

#3 born2c0de  Icon User is offline

  • printf("I'm a %XR",195936478);
  • member icon

Reputation: 180
  • View blog
  • Posts: 4,667
  • Joined: 26-November 04

Re: Some help with binary search trees

Posted 17 January 2009 - 05:15 AM

Topics merged.
Was This Post Helpful? 0
  • +
  • -

#4 Gloin  Icon User is offline

  • Expert Schmexpert...
  • member icon

Reputation: 235
  • View blog
  • Posts: 4,489
  • Joined: 04-August 08

Re: Some help with binary search trees

Posted 17 January 2009 - 05:40 AM

Are you familliar with the binary search algorithm?
You have a series (array) of sorted numbers (smallest to largest)and you want to find a specific number among those.

What you could do is start from the first element and go through the array until you find that number (in which case you're done) or you find a number that is larger (in which case you know the number was not in the series.

There is however a 'better' way. If you start in the middle of the array and compare the numbers (the middle number and the number you search for) you'll see if they're equal (in which case you're done) or if it's smaller or larger. If the number in the array is smaller than the one you're looking for, you know that if the number is in the array it has to be on the half that comes after the middle element, this means you have limited the searchspace to 50% of the original searchspace (which was the whole array). The opposite case is identical in theory. You repeat this action until you find the element or until you can no longer divide the searchspace.

A comparison of these 2 methods yield that it takes linear time to find the element using the first method and logarithmic time to find the element with the later method. I.e the later is the preferred method.

A binary search tree is a representation of this search algorithm. The first (root) element of the tree is equal to the first element you'd compare with in the search algorithm, I.e the middle element. From this element you have two choices, go bigger or go smaller. The natural way of implementing this (struct) would be to have nodes with (a value and) two (references/pointers) edges (one to each child node and there are two of them, hence the name binary search tree).
You can however implement it using the array and put the elements into the tree in the order described above.


Quote

In computer science, a binary search tree (BST) is a binary tree data structure which has the following properties:

* Each node (item in the tree) has a distinct value.
* Both the left and right subtrees must also be binary search trees.
* The left subtree of a node contains only values less than the node's value.
* The right subtree of a node contains only values greater than or equal to the node's value.

Source Wikipedia

This post has been edited by Gloin: 17 January 2009 - 05:48 AM

Was This Post Helpful? 0
  • +
  • -

Page 1 of 1