binary trees in tcl (re: whitepaper)
Author Message
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.
--

Tue, 28 Sep 1999 03:00:00 GMT
binary trees in tcl (re: whitepaper)

Quote:

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

It wasn't the white paper thread, it was the OO thread.  It's a white paper
because you print it on white paper :^).

Quote:
>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.

A generic tree was implemented, not a binary-tree.

--

Software Engineer, Oregon R&D          office: 541.683.7891
URL: http://www.cs.uoregon.edu/~jhobbs/

Wed, 29 Sep 1999 03:00:00 GMT
binary trees in tcl (re: whitepaper)

Quote:

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

>It wasn't the white paper thread, it was the OO thread.  It's a white paper
>because you print it on white paper :^).