C++ and Java, tree question

You can store a binary tree in an array as mentioned here:

http://en.wikipedia.org/wiki/Binary_tree#Methods_for_storing_binary_trees

Edit: Cool thing about doing that is you can do a level-order traversal by just walking the array. =)

thanks, looks good

Edit: That's a cool extra option, but isn't the use of trees to be able to reduce the problem space? An array might be friendly on the cache though, I should time that ( Or did anyone else already do that? )

In C# you have reference types. So:
public class Node
{
public Node lch;
public Node rch;
public int value;
}

could be the node. Basically with reference types the assignment operator makes the lhs point to the instance of the rhs.

Node n = new Node();

Node m = n;

So modifying the instance that m references will modify the instance n is referring to.

Quote:

Original post by Dolf I'm a C++ programmer and I was wondering how you could ever implement a tree structure in a language without pointers?

In the case of Java, variables don't hold objects, but rather hold references to objects. Basically, in Java, every non-primitive variable IS a pointer (but without pointer arithmetic).

Ok cool.

What would you advise for tool development? Whats in demand? Java or C# or something else?

To implement a tree, you need reference semantics. Pointers are one of the ways used by C and C++ to implement reference semantics (they also implement iteration semantics and option semantics, which makes them kind of ugly and dangerous and needlessly complicated). This means that you can implement trees with pointers, but you don't need pointers to implement trees. In fact, the whole manual memory management issue in C and C++ makes trees harder to implement than in other languages.

It is usually considered that the easiest way to create a tree is to use a recursive variant type with reference semantics. Objective Caml, among others, provides the required functionality to do so, as illustrated by this expression tree example:

type expression =   | Value of int  | Add of expression * expression   | Subtract of expression * expression(* 10 - 20 + 30 *)let test = Add (Subtract (Value 10, Value 20), Value 30) (* Evaluation *)let rec eval = function   | Value v -> v  | Add (left, right) -> eval left + eval right  | Subtract (left, right) -> eval left - eval rightlet _ = eval test

The equivalent tree in C++ would look like:

class expression{public:  virtual ~expression() {}  virtual int eval() const = 0;};typedef boost::shared_ptr<const expression> expression_ptr;class value : public expression{  int v;public:  value(int v) : v(v) {}  int eval() const { return v; }};class add : public expression{  expression_ptr left, right;public:  add(expression_ptr left, expression_ptr right)     : left(left), right(right) {}  int eval() const { return left->eval() + right->eval(); }};class subtract : public expression{  expression_ptr left, right;public:  subtract(expression_ptr left, expression_ptr right)    : left(left), right(right) {}  int eval() const { return left->eval() - right->eval(); }};expression_ptr p10(new value(10)),               p20(new value(20)),               p30(new value(30)),               sub(new subtract(p10, p20)),               test(new add(sub, p30));test -> eval();

As for storing in an array, it wastes memory if the tree is not balanced.

Wrong, the equivalent C++ code would be http://www.boost.org/doc/libs/1_38_0/doc/html/variant/tutorial.html#variant.tutorial.recursive

As for how to do manual memory management in garbage collected language (which is quite often necessary since those languages are quite inefficient with locality etc.) you indeed allocate a big array of some primitive type like int, which is exactly the same thing as memory, and you can recreate C-style like code, with indexes in the array being equivalent to pointers.
This however ends up being less efficient than direct memory management, in particular due to the need to use serialization/deserialization to store elements in your array etc.

Quote:

Original post by ToohrVyk As for storing in an array, it wastes memory if the tree is not balanced.

True, and you waste memory storing pointers (references) when the tree is balanced! Anyways, I always see pointers and references just different names (and potentially syntax) for the same concept. When he said "implement a tree structure in a language without pointers" I figured he was ruling out references too, since using a reference would be functionally equivalent to using pointers and an obvious choice.

Pointers and references are pretty much the same ye. My question was about how you can program a tree in a higher level language than C++.

Quote:

Original post by loufoque Wrong, the equivalent C++ code would be http://www.boost.org/doc/libs/1_38_0/doc/html/variant/tutorial.html#variant.tutorial.recursive

Yes, but I decided to post a shorter and simpler example, because I didn't want C++ to appear worse than it really is. What with the forum bias against C++ and all [wink]

Quote:

(which is quite often necessary since those languages are quite inefficient with locality etc.)

In my experience, "often" means in this case "once or twice every seven years". If it happens to you more often than that, and a high-level refactoring doesn't solve the issue outright by taking advantage of GC behavior, you should seriously question your language choice, and move to a language that's more adapted.

Quote:

you indeed allocate a big array of some primitive type like int, which is exactly the same thing as memory, and you can recreate C-style like code, with indexes in the array being equivalent to pointers.

This would border on the insane. If you need C pointer functionality, write the code in C and use bindings.

Quote:

Original post by Dolf Pointers and references are pretty much the same ye. My question was about how you can program a tree in a higher level language than C++.

You would use whatever the language uses to implement recursive variant types. Your performance may suffer if they don't have reference semantics, though.

Quote:

Original post by Dolf Pointers and references are pretty much the same ye. My question was about how you can program a tree in a higher level language than C++.

Java:

public class Node<E> {  List<Node<E>> children;  E value;  };

As for languages without pointers or references, I'm having hard time imagining one.

Pointers or references can be represented with array indices, so any language that supports some form of arrays or dictionaries can be used to implement any ADT with cursors.

Quote:

Original post by Dranith Anyways, I always see pointers and references just different names (and potentially syntax) for the same concept. When he said "implement a tree structure in a language without pointers" I figured he was ruling out references too, since using a reference would be functionally equivalent to using pointers and an obvious choice.

But then you cannot use arrays either, because arrays are also reference types:

Foo a[] = new Foo[100]; // <-- a is a reference to an array

Quote:

Original post by ToohrVyk Quote: you indeed allocate a big array of some primitive type like int, which is exactly the same thing as memory, and you can recreate C-style like code, with indexes in the array being equivalent to pointers. This would border on the insane. If you need C pointer functionality, write the code in C and use bindings.

I take it you've never had to develop in J2ME with devices supporting a maximum 64Kb JAR size. (But then, I won't disagree that it borders on the insane to do it at all :) )

Quote:

You would use whatever the language uses to implement recursive variant types. Your performance may suffer if they don't have reference semantics, though.

What real-world languages don't offer reference semantics in some form? o_O

But anyway, to drive the point home: reference semantics are a different issue from 'references' as understood by C++ (and C#, which understands them differently, for that matter). We are talking about the abstract functionality that pointers provide, other than pointer arithmetic and the unified treatment of scalar and array values. :) (Some people also exclude possible-null-ness from their understanding of reference semantics. It isn't really necessary in a surprising percentage of cases.) Some languages provide this functionality implicitly. (In Java's case, only for object types; primitive types still have value semantics. C#, similarly, distinguishes between 'class' and 'struct' types.)

Quote:

Original post by DevFred Quote: Original post by Dranith Anyways, I always see pointers and references just different names (and potentially syntax) for the same concept. When he said "implement a tree structure in a language without pointers" I figured he was ruling out references too, since using a reference would be functionally equivalent to using pointers and an obvious choice. But then you cannot use arrays either, because arrays are also reference types: Foo a[] = new Foo[100]; // <-- a is a reference to an array

But (a) we're still talking about a theoretical language here; and (b) the ensuing code wouldn't really use the fact of 'a' being a reference anyway. :)

Quote:

Yes, but I decided to post a shorter and simpler example, because I didn't want C++ to appear worse than it really is. What with the forum bias against C++ and all

It's not longer, it's shorter.
It's also the direct translation of sum types in functional languages, since it's the exact same thing.

And it's not "worse", it's very elegant. That's what real good modern C++ is like. That's like you should program in C++.
The code you posted looks more like the Java or C# way.

Quote:

Your performance may suffer if they don't have reference semantics, though.

Reference semantics are pure evil and lead to lots of problems due to aliasing.
Also, I don't really see the link between semantics (which only defines how the program behaves) and performance.

Quote:

As for languages without pointers or references, I'm having hard time imagining one.

References and reference semantics aren't the same thing.

Take a language without mutability. There are neither value nor reference semantics, since the objects are not mutable.

Quote:

Original post by loufoque Also, I don't really see the link between semantics (which only defines how the program behaves) and performance.

Because semantics also describes how long certain operations take. For instance, whether computing the length of a string takes constant-time or linear-time [smile]

Quote:

Take a language without mutability. There are neither value nor reference semantics, since the objects are not mutable.

Oh, really?

Suppose I write, in a pure functional fashion:

let a = ["a"; "b"; ...; "zzy"; "zzz" ] let b = "foo" :: a let c = "bar" :: alet _ = frobnicate b c

If the language uses reference semantics, the definition of b and c is guaranteed to be constant-time. If it doesn't use reference semantics, the definition may involve a copy of a and therefore take linear time. So, even if a certain language makes no decision about whether it uses reference semantics or not, the notion still exists for languages without mutability.

Quote:

Original post by Dolf Pointers and references are pretty much the same ye.

C++ pointers and Java references are somewhat comparable, yes.
C++ pointers and C++ references, on the other hand... ;)

Quote:

Original post by Dolf My question was about how you can program a tree in a higher level language than C++.

Haskell example:

data Tree a = Leaf a            | Branch (Tree a) (Tree a)leaf  (Leaf x)     = xleft  (Branch x _) = xright (Branch _ x) = xexample = Branch (Branch (Leaf 1) (Leaf 2)) (Branch (Leaf 3) (Leaf 4))