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

[Stefan Karpinski]

There was some discussion of this on the DataStructures package:

https://github.com/JuliaLang/DataStructures.jl/issues/154

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

[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

[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.