Proposal: Red Black Tree

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Proposal: Red Black Tree

Athul George Appadan
Hi everyone,

I am working on red black tree implementation on Julia. Can I send a PR once the code is ready,or should I make all the changes in docs, README etc. before pushing it?
Waiting for a reply.


Athul George Appadan
Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Red Black Tree

Stefan Karpinski
There was some discussion of this on the DataStructures package:


Red-Black trees might make an addition to that package but would not go into the Julia standard library.

On Tue, Apr 5, 2016 at 6:27 AM, Athul George Appadan <[hidden email]> wrote:
Hi everyone,

I am working on red black tree implementation on Julia. Can I send a PR once the code is ready,or should I make all the changes in docs, README etc. before pushing it?
Waiting for a reply.


Athul George Appadan

Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Red Black Tree

Kevin Squire
Just to add a little bit to this:

DataStructures.jl contains a concrete implementation of an AVL tree, which is then used to back a SortedDict Abstract Data Type (ADT) (as well as other related ADTs).

There was some minor discussion a while back as to whether AVL trees or red-black trees would generally be faster.  I think in the literature, the jury is out--it probably comes down to implementation, but the author of the current code chose to use AVL trees simply because they were easier to understand and implement (for him).

It would be great to see an implementation of red-black trees implemented with a similar interface, and see how the two compare.

As an aside, for the AVL tree and SortedDict (et al.) that are currently in DataStructures.jl, the author drew ideas heavily from the C++ map data structure, and perhaps because of this, there's a lot going on there.  The SortedDict ADT, in particular, could probably use a little bit of simplification--don't feel obliged to copy/implement it fully when comparing to it.

Cheers,
   Kevin

On Tue, Apr 5, 2016 at 1:18 PM, Stefan Karpinski <[hidden email]> wrote:
There was some discussion of this on the DataStructures package:


Red-Black trees might make an addition to that package but would not go into the Julia standard library.

On Tue, Apr 5, 2016 at 6:27 AM, Athul George Appadan <[hidden email]> wrote:
Hi everyone,

I am working on red black tree implementation on Julia. Can I send a PR once the code is ready,or should I make all the changes in docs, README etc. before pushing it?
Waiting for a reply.


Athul George Appadan


Reply | Threaded
Open this post in threaded view
|

Re: Proposal: Red Black Tree

Páll Haraldsson
On Wednesday, April 6, 2016 at 2:50:12 AM UTC, Kevin Squire wrote:
Just to add a little bit to this:

DataStructures.jl contains a concrete implementation of an AVL tree, which is then used to back a SortedDict Abstract Data Type (ADT) (as well as other related ADTs).

I remember from some time back seeing red-black tree. I guess this is it:

https://github.com/pygy/RedBlackTrees.jl


This is the most interesting tree-structure to me (if you want to look at or need a tree to implement..):

https://en.wikipedia.org/wiki/Fractal_tree_index


https://en.wikipedia.org/wiki/B-tree

is not only useful for databases. Because of cache, memory is more like disk now. B-trees have a flaw (for disks) that the above solves.

-- 
Palli.