[Lemon-devel] Various trees' implementation

[Balazs Dezso]

Hi

Sorry for the late answer, but I was not on the internet for a while.

First of all we should decide, what you should implement in the lemon. There 
are lot of applications of search trees, which should be take attention before 
deciding the interface of these trees. I would give two examples:
 - creating such ordered set, which can give back the rank of an item in 
O(log(n)) time, and each operation is O(log(n))
 - creating the splay tree which is used in the dynamic tree of Sleator and 
Tarjan

In my opinion the ordered set interface (like std::map) is not enough for this 
purpose, it needs some callback possibility (item addition, item removing, 
rotatings). I recommend to see the traits and visitor based implementations in 
lemon, you could benefit from these.

Additionally, the different search trees should have similar interface, and the 
common concept would be a good solution.

Best, Balazs 

On Friday 08 August 2008 18:23:28 Zsolt Dollenstein wrote:
> Hello,
>
> First of all I am pretty new to this project, so please forgive me my
> first (hopefully) few missteps; I hope this is the correct list to
> write to.
> I am currently working on implementing AVL/Red-Black/Splay trees in
> C++, and was wondering if Lemon could benefit from it. I would happily
> make the code more "Lemonish" and commit it to the repository, if you
> could show me where to start with basic concepts, principles about the
> library. I've already skimmed through the "CodingStyle" and
> "CommitGuide" part of the webpage and have a fully working version of
> the Red-Black tree, so I am mainly interested in principles concerning
> for example if I should write a separate concept for BSTs and such.
> That is, of course, if you think the above three containers are useful
> to add to the library.
>
> Cheers,
> Zsolt