AVL Tree,Binary Tree,Sorting.. 
Author Message
 AVL Tree,Binary Tree,Sorting..

        Is there any reuseable package for these ??


Tue, 30 Nov 2004 22:51:25 GMT  
 AVL Tree,Binary Tree,Sorting..

Quote:

> Is there any reuseable package for these ??

None that I'm aware of. The usual way of doing this is to put it into a list and then
apply the lsort command.
As for a tree for storing, what exactly is the application you have in mind?

Greetings!
Volker



Fri, 03 Dec 2004 18:47:33 GMT  
 AVL Tree,Binary Tree,Sorting..


:       Is there any reuseable package for these ??
:

I don't know whether this has all you are seeking or not, but you might
check it out.

What: Containers
Where: <URL: http://pages.infinit.net/cclients/files/containers.htm >
Description: Small Tcl extension that implements basic container objects, such
        as bag, queue, tree, priority queue, random queue, struct, stack,
        hash, FIFO, LIFO, etc.  Code is in C++, using templates.
        Free for non-commercial use, written permission of author otherwise.
        Source available, as well as a binary distribution for Windows.
        Currently at version 1.1.
Updated: 05/2001

--
Support Internet Radio <URL: http://saveinternetradio.org/ >
Join Tcl'2002 in Vancouver http://www.tcl.tk/community/tcl2002/
Even if explicitly stated to the contrary, nothing in this posting
should be construed as representing my employer's opinions.



Sun, 05 Dec 2004 19:30:29 GMT  
 AVL Tree,Binary Tree,Sorting..

Quote:

> Is there any reuseable package for these ??

What's the purpose?  If you want a priority queue, look in a standard algorithms
book (red-black trees are acceptable alternatives to AVL trees, btw) and
implement what's there.  If you want just a general storage mechanism and are
not really that fussed about keeping things in order, use Tcl arrays (which are
implemented on top of hash tables and are pretty fast.)

Tcl 8.4 (in beta next week, hopefully) will include code for efficiently doing
binary searches on lists.

Donal.
--

-- If that's dead, sign me up for {*filter*} classes.



Mon, 06 Dec 2004 16:49:11 GMT  
 AVL Tree,Binary Tree,Sorting..


:> Is there any reuseable package for these ??
:
:What's the purpose?

In my mind, the purpose is to prevent thousands of Tcl programmers from
having to locate a standard algorithm book, converting the pseudo code into
Tcl, debugging the mistakes in said conversion, etc....

--
Support Internet Radio <URL: http://saveinternetradio.org/ >
Join Tcl'2002 in Vancouver http://www.tcl.tk/community/tcl2002/
Even if explicitly stated to the contrary, nothing in this posting
should be construed as representing my employer's opinions.



Wed, 08 Dec 2004 01:14:21 GMT  
 AVL Tree,Binary Tree,Sorting..

Quote:

>         Is there any reuseable package for these ??

I have used the red-black tree package, RBTree, with great success,  It
can be found on neosoft at:

http://www.neosoft.com/tcl/ftparchive/sorted/packages-8.0/misc/rbtree...

It was easy to use, worked under NT and LINUX, and was fast.  If I
recall, I was using TCL 8.2 or early 8.3

==============================================================

The readme file:
================
RBTree is a TCL extension which adds a new data type to TCL.

The new data type is a red-black tree.  Roughly speaking, this is a
cross
between an array and an ordered list.  It can efficiently find a value
in
the tree, like an array.  But it can also find the closest value to
value
that is not in the tree, or all the values between two values, like an
ordered list.  Most operations are O(log(n)).  It can provide an
alternative
to lsort which more appropriate in interactive programs.  The red-black
tree
works correctly with keys with embedded nulls; built in TCL arrays do
not.

This data type is implemented as a new TCL data type.  It may be stored
in a
variable, passed to or from a procedure, converted to a string, etc.

New procedures are added to access this data type.  They can give the
appearance of a map (i.e. an array, or a keyed list), a multimap, a set,
or
a multiset (i.e. a bag).

This package includes source, and a precompiled .DLL for MS Windows.  I
have
only tested it under Linux with gcc and under MS Windows with MS Visual
C++
5.0.

This software is free under the terms of the GNU public license.

Revision history:

    Version                               Comments
 1.0            Initial release.

 1.0.1          The source code is now more portable.  The distribution
now
                includes a precompiled .DLL for MS Windows.
                Added the ability to sort by integers, real numbers, or
                strings.  The source code is now written in C, not C++.

 1.1            The command tree::find was added.  The precompiled .DLL
is
                now built with the stubs library, and should work for
more
                versions of TCL.



Wed, 08 Dec 2004 07:43:51 GMT  
 AVL Tree,Binary Tree,Sorting..

Quote:

> In my mind, the purpose is to prevent thousands of Tcl programmers from
> having to locate a standard algorithm book, converting the pseudo code into
> Tcl, debugging the mistakes in said conversion, etc....

The really stupid thing is most of them should be using an array instead...

Donal.
--

"If RedHat are so purblind that they think computing is about ever fancier
 'desktop themes', they are in the interior design business, and as everyone
 knows, if you can{*filter*}you can paint."                     -- Steve Blinkhorn



Fri, 10 Dec 2004 21:37:21 GMT  
 AVL Tree,Binary Tree,Sorting..

Quote:

> The really stupid thing is most of them should be using an array instead...

Unless you need to keep it sorted, yeah.

--
Darren New
San Diego, CA, USA (PST). Cryptokeys on demand.
** http://home.san.rr.com/dnew/DNResume.html **
** http://images.fbrtech.com/dnew/ **

     My brain needs a "back" button so I can
         remember where I left my coffee mug.



Fri, 10 Dec 2004 23:00:57 GMT  
 AVL Tree,Binary Tree,Sorting..

Quote:


> > The really stupid thing is most of them should be using an array instead...

> Unless you need to keep it sorted, yeah.

Yes, but most of the time C-programmers want to keep something sorted to speed
up access. As a tcl programmer you don't need this, therefore there's much less
need for sorted data structures.
I suppose Donals answer was meant for all those people who learned C/C++ and want
to use the same techniques in tcl, therefore foregoing many advantages tcl offers
in the way of handling data.

Greetings!
Volker



Fri, 10 Dec 2004 23:50:12 GMT  
 AVL Tree,Binary Tree,Sorting..

Quote:

> Yes, but most of the time C-programmers want to keep something sorted to speed
> up access. As a tcl programmer you don't need this,

Well, except when you do, sure. :-)

Quote:
> therefore there's much less
> need for sorted data structures.

It sounds like what you're saying is "we don't do RB Trees in Tcl, because
if you need that, you shouldn't use Tcl." Um....

Quote:
> I suppose Donals answer was meant for all those people who learned C/C++ and want
> to use the same techniques in tcl, therefore foregoing many advantages tcl offers
> in the way of handling data.

Yes.

--
Darren New
San Diego, CA, USA (PST). Cryptokeys on demand.
** http://home.san.rr.com/dnew/DNResume.html **
** http://images.fbrtech.com/dnew/ **

     My brain needs a "back" button so I can
         remember where I left my coffee mug.



Sat, 11 Dec 2004 00:07:54 GMT  
 AVL Tree,Binary Tree,Sorting..

Quote:


> > Yes, but most of the time C-programmers want to keep something sorted to speed
> > up access. As a tcl programmer you don't need this,

> Well, except when you do, sure. :-)

> > therefore there's much less
> > need for sorted data structures.

> It sounds like what you're saying is "we don't do RB Trees in Tcl, because
> if you need that, you shouldn't use Tcl." Um....

Considering that the only reasonable RB tree application I can think of offhand is
real time performance, maybe you are right. I really wouldn't recommend writing
an interrupt routine in tcl.

Greetings!
Volker



Sat, 11 Dec 2004 01:07:28 GMT  
 AVL Tree,Binary Tree,Sorting..

Quote:

> Considering that the only reasonable RB tree application I can think of offhand is
> real time performance, maybe you are right.

Hmm... Well, um, no. There are any number of algorithms that require
maintenance of sorted lists that are being modified for good performance. I
mean, you're saying that all the research into B-trees and variants thereof
is only good for real-time performance? Bosh. That's just silly, and you
ought to know it. :-)

Anyway, since there *is* a RBTree extension, the whole conversation is
fairly rhetorical.

--
Darren New
San Diego, CA, USA (PST). Cryptokeys on demand.
** http://home.san.rr.com/dnew/DNResume.html **
** http://images.fbrtech.com/dnew/ **

     My brain needs a "back" button so I can
         remember where I left my coffee mug.



Sat, 11 Dec 2004 01:53:43 GMT  
 AVL Tree,Binary Tree,Sorting..

Quote:


>> The really stupid thing is most of them should be using an array instead...
> Unless you need to keep it sorted, yeah.

Of course, but most people don't really know when they need that.  The problem
(IMHO) is they've been on an Algorithms course that's taught them all about AVL
trees and multi-probe hashes, but hasn't actually mentioned a lot about the
sorts of bread-and-butter data-structures that really go about and save peoples'
bacon.

Discretion is the hardest part of programming, worse even than documentation and
regression testing.

Donal.
--

"[E]ven now, wars are fought and lost, people are killed and unkilled, toilet
 rolls are used and unused, pants are derwear and underwear, all because
 of the delicious velvety substance that is Marmite."         -- Nathan Weston



Sat, 11 Dec 2004 20:40:05 GMT  
 
 [ 13 post ] 

 Relevant Pages 

1. searching trees (AVL, 2-3-4 and red-black trees)

2. looking for balancing (binary/avl) tree programs

3. avl-2.0, a balanced binary tree extension

4. binary & AVL trees, regexp

5. Self-Adjusting Binary Search Trees (Splay Trees)

6. Self-Adjusting Binary Search Trees (Splay Trees)

7. AVL trees under OOP

8. AVL tree code

9. AVL trees in LISP

10. AVL Trees

11. splay and AVL tree code

12. AVL Trees

 

 
Powered by phpBB® Forum Software