1

I am encountering an up-arrow in pseudocode examples of balanced binary search trees. What is the author intending to denote by the use of such a symbol which can either follow or precede a variable?

type data = ....;
  Tree = ↑node;
  node = record
    left, right: Tree;
    level: integer;
    key: data;
  end;
var bottom, deleted, last: Tree;

procedure InitGlobalVariables;
begin
  new (bottom);
  bottom↑.level := 0;
  bottom↑.left := bottom;
  bottom↑.right := bottom;
  deleted := bottom;
end;

This pseudocode is a reference to building Red-Black-Trees found here written by Arne Andersson.

Friendly-Robot
  • 1,124
  • 14
  • 24

1 Answers1

1

The up-arrow is not a standard. In fact pseudo-code is not really a standard either so each author has some liberty in what notations they use.

The author should have made a legend for the pseudo-code explaining what the up-arrow means.

My interpretation is that it is intended to show that Tree is a pointer to a data structure of type node. The notation is somewhat reminiscent of Pascal.

And the up-arrow following a variable is intended to denote that the pointer variable is being dereferenced .

Community
  • 1
  • 1
Mike Dinescu
  • 54,171
  • 16
  • 118
  • 151
  • Since the arrow is pointing up, it could refer to the parent of the current node – jcpennypincher Feb 10 '16 at 00:14
  • @jcpennypincher while possible, it's unlikely; more likely it's used to denote a pointer, and later to denote a pointer dereference – Mike Dinescu Feb 10 '16 at 00:19
  • By that logic it could be anything you want it to be. It's psuedocode which means it doesn't have a defined syntax. Whoever wrote it should be more explicit and perhaps leave a comment. since we are talking about a balanced binary search tree I would assume it is the pointer to the parent node which is always above the child node, up above. I would bet $50 that is what the author meant. – jcpennypincher Feb 11 '16 at 20:51
  • 1
    @jcpennypincher I'm not a gambling man myself but I'll take you up on the $50 dollars - perhaps we can track down Arne Andersson, the author, and get some closure (no pun intended) – Mike Dinescu Feb 12 '16 at 04:19