binary trees in tcl (re: whitepaper)

Recently someone (say A) made the point that tcl was perhaps NOT the language

of choice to implement a (binary) tree data structure. I believe this

was part of the JO whitepaper thread. [Why do they call them whitepapers?]

Someone else (say B) implemented a tree in tcl, and A observed it

was `hard' for others to understand what was going on in B's implementation.

I think A made his point, but later I though maybe not. Yes I am going

to offer my own implementation of a tree. But first I am going to

try to avoid the problem altogether.

Point 1. Binary Trees are hard to implement in Tcl.

Answer 1. So what? Whereas a binary tree is a fundamental data

structure, it is not a natural occuring object. The tree was

created to solve problems related to run time speed and not

because our mind naturally works that way. [I can't believe I am

saying this, my mind has accepted trees as natural, but I claim

it is a learned behavoir.] As evidence for this point of view

note that STL (the standard template library for C++) has lists,

vectors, and maps but no trees.

Point 2. One could use a binary tree here to speed up this

algorithm, but tcl does not do trees well.

Answer 2. What are you trying to do? Perhaps you are overlooking

another solution to your problem which is easy to do in tcl. For

example, if you are using the tree as a dictionary, a tcl array

[hash table] is usually a better answer. As evidence, note that

SGI has added hash sets to STL, so one is not limited to the

red-black tree version in the HP STL version of sets.

Of course, if you are trying to use a tree as a map then

you might have a point. Although I do not think anyone would use

a raw binary tree here (some way of balancing the tree needs to

be added), a red-black tree is a binary tree. I am

not sure that tcl has a good way to implement a map. Does anyone

have a map implementation for tcl. [Map has O(logN) insert

delete and transversals (in sorted order) in O(N).]

Point 3. Tcl is not good for everything, for example try writing

a easily understandable binary tree.

Answer 3. I agree, but no language is good for everything. But

with a little thought, I claim that the following is not too hard

to understand and provides a binary tree in tcl.

Theory: Every node in a binary tree is uniquely identified by a

positive integer. The root is 1 and for each node n, the left

child is 2n, the right child is 2n+1 and the parent is floor(n/2).

[If you think of a tree as growing down, then this is the ordering

one gets counting left to right from the top down.]

Like 1

2 3

4 5 6 7

8 9 10 11 12 13 14 15

Implementation: The tree is really just an associative array say key.

Each node is just an integer, and the data at node n is just key(n).

The root is 1, left_node(n) returns 2*n, etc and for example a sorted

list could be obtained by

inorder { node } {

if key(node) is defined {

inorder left_node ( node )

visit node

inorder right_node ( node )

}

Quote:

}

Cop Out: Of course, this tree is not good enough. Balancing this

tree could cost many more than O(logN) node changes. But it is

a good static (that is one with no rotations allowed) binary tree.

--