Binary Search Tree Algorithm

Question

Search(T,k)
x<- root[T]
while x != NULL and k != key[x] 
do 
  if k<key[x]
    then x <- left[x]
  else x <- right[x]
    return x

I just started with algorithms and I often see "<-" this and key[x] terminology can someone tell me what is key is it an array ? x was getting the root value and then it is used as an index ? I fail to understand this. Please explain.

The notation here is a bit different. x in key[x] is not an index. It actually means "the value of key at node x". Similarly with left[x] and right[x], they mean "the left and right nodes of x. <-` is simply an assignment statement. — Aziz
– Aziz, Commented Nov 1, 2012 at 3:44
If you're more familiar with object-oriented notation, you can read key[x] as x.key, left[x] as x.left and so on. — hammar
– hammar, Commented Nov 1, 2012 at 3:46
@hammar, dont'you mean C-style notation under object-oriented notation? — Vovanium
– Vovanium, Commented Nov 1, 2012 at 12:32

James · Accepted Answer · 2012-11-01 03:45:52Z

4

It's pseudocode (not a real language).

In this case <- means 'is assigned' and can be thought of as doing what = does in modern languages. key[x] is shorthand for the key property of structure/object x (this doesn't mean it's a member of the x class necessarily, it could be retrieved from a data structure such as a map. The actual implementation is left up to the algorithm implementer.

So the above algorithm could be written in C as:

Node* Search(Tree* T, Key k)
{
    Node* x = T->Root();
    while ((x != NULL) && (k != x->Key())
    {
        if (k < x->Key())
            x = x->Left();
        else
            x = x->Right();
    }

    return x;
}

answered Nov 1, 2012 at 3:45

James

9,3173 gold badges37 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

rchanley · Accepted Answer · 2012-11-01 03:48:07Z

0

This looks like psuedo-code. Think of the <- as the assignment operator = in Java. You also sometimes see is as := in other psuedo-code variations.

x is used as a pointer to a node in the tree. The key is the value you usually find in a circle when the tree is drawn out, and left and right is the node's two children.

Edit: That psuedo-code is a little off as well. James' example is good.

answered Nov 1, 2012 at 3:48

rchanley

4592 silver badges7 bronze badges

Collectives™ on Stack Overflow

Binary Search Tree Algorithm

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related