Binary search trees

Can anyone please tell me that what are binary search trees. I mean algorithm.

Thanks
tparvaizAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

nietodCommented:
Typically, a binary search tree is implimented as a collection of 0 or more  classes or structures called nodes.  Each node stores a single value from the set of values stored in the tree.  Each node also stores two pointers to other nodes that are "farther down the tree".   One or both of these node pointers may be NULL, indicating that they do not refer to a node.  One of the pointers refer to a node that has a larger value than the current node and the other pointer refers to a node that has a smaller value than the current node.

continues.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
nietodCommented:
For a binary tree that stores ints a node might be declared as a structure like

Node
{
   int Value;
   Node *NextPtr; // -> node with higher value.
   Node *PrevPtr; // -> node with lower value.
};

The nodes in a binary tree are organized in a manner that is similar to a family tree.  At the top is the "root node"  This is the node that is the key to obtaining access to all the other nodes in the tree.  The root node points to 0, 1, or 2 other nodes.  The node that is refered to by the "NextPtr", if there is one, will contain a larger value than the root node.   The node that is refered to by the "PrevPtr" will contain a smaller value than the root node.  Then these node will each have 0, 1, or 2 child nodes below them and so on.

continues
0
nietodCommented:
If we draw the tree, so that the node that has the lesser value is shown below and to the left and the node with the higer value is shown below and to the right.  Then an example binary tree might look like

          5
      /       \
    2           7
  /    \      /    \
1      3   6      9

As  you can see, for any node, the pointer that leads down and to the left leads to a lower value and the pointe that leads down and to the right leads to a higher value.   Note that the 4 lowest nodes have no children nodes.  This means that there pointers are set to NULL.   Note that the reason this is called a "binary tree" is that at each node the tree "splits" into two branches (up to two branches).
0
nietodCommented:
In order to find a value in the tree, you start with the root node (you start with the root node for everything.)  Then you follow this procedure for ever node you encounter in the search (starting with the root node beign the first node you encouter.)  If the node stores the value you want, then you've found the value.  If not, if the value to be found is larger than the value in the node, look to see if there is a "next node" specified by the "nextPtr".  If so go to that node.  If not, the search is done and failed to find the value.  If the value to be found is lowe than the value in the node, then look to see if there is  "previous node" specified by the "PrevPtr",  If so, go to that node.  If not, the search is done and failed to find a value.

Questions?
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Software

From novice to tech pro — start learning today.