FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

intrusive red-black tree...

 
Post new topic   Reply to topic     Forum Index -> Nova
View previous topic :: View next topic  
Author Message
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Thu Oct 19, 2006 9:25 am    Post subject: intrusive red-black tree... Reply with quote

I have some questions...

1) What is the difference of an intrusive RB Tree vs a regular one?

2) Can you show an example of how to use your RB tree? does it have a foreach iterator?

Thanks.

~ Clay
Back to top
View user's profile Send private message AIM Address
KlausO



Joined: 16 Feb 2006
Posts: 27
Location: Germany

PostPosted: Fri Oct 20, 2006 5:53 am    Post subject: Reply with quote

Quote:
1) What is the difference of an intrusive RB Tree vs a regular one?


In intrusive data structures the pointers/references which form the data structure (list, tree, ...) are introduced into the application node classes.

A good article about the benefits of instrusive data structures could be found here:
http://www.codefarms.com/publications/intrusiv/intr.htm

Quote:
2) Can you show an example of how to use your RB tree? does it have a foreach iterator?


A usage example is in the unittest file:
http://www.dsource.org/projects/nova/browser/trunk/NOVA/DS/intrusive/unittests/redblacktree.d

But unfortunately it seems that I forgot to implement opApply Crying or Very sad
I will try to add it this weekend.
Back to top
View user's profile Send private message
clayasaurus



Joined: 21 May 2004
Posts: 857

PostPosted: Mon Oct 23, 2006 3:50 pm    Post subject: Reply with quote

Alright. I have some questions about the new non-intrusive implementation that you posted in the d.learn newsgroup.

I just want to know about the key. My guess is that the binary tree does its 'sorting' based on the key value, is this correct?

So, if I had a set of numbers, and I wanted the tree to search by numbers, then I would use...

tree[7].insert(7);
tree[3].insert(3);
tree[9].insert(9);

Which will print in order

3, 7, 9 ?

Also, it seems in your example you use tree.key, but in your tree code you declare nkey(), so I have to use tree.nkey .

[edit]: The following tree example removes 26, even though 26 was never called to be removed.

Code:

import redblacktree;

int main()
{
   RedBlackTree!(int, int) tree = new RedBlackTree!(int, int);

   tree.insert(11,11);
   tree.insert(9,9);
   tree.insert(12,12);
   tree.insert(8,8);
   tree.insert(9,9);
   tree.insert(10,10);
   tree.insert(11,11);
   tree.insert(19,19);
   tree.insert(30,30);
   tree.insert(26,26);

   foreach(v; tree)
      writefln(v.nvalue);

   tree.remove(30);
   tree.remove(11);

   writefln(" ");

   foreach(v; tree)
      writefln(v.nvalue);

   return 0;
}



Thanks.
~ Clay
Back to top
View user's profile Send private message AIM Address
KlausO



Joined: 16 Feb 2006
Posts: 27
Location: Germany

PostPosted: Thu Oct 26, 2006 4:25 pm    Post subject: Reply with quote

Quote:
I just want to know about the key. My guess is that the binary tree does its 'sorting' based on the key value, is this correct?


Correct.

Quote:
So, if I had a set of numbers, and I wanted the tree to search by numbers, then I would use...

tree[7].insert(7);
tree[3].insert(3);
tree[9].insert(9);

Which will print in order

3, 7, 9 ?


Yes.

Quote:
Also, it seems in your example you use tree.key, but in your tree code you declare nkey(), so I have to use tree.nkey


Oh my, it was late ! I had to rename this because of name clashes.


Quote:
[edit]: The following tree example removes 26, even though 26 was never called to be removed.


Mmm, must be a bug, I will check.

In the meantime I had a look at your implementation and must admit it looks cleaner as mine. The only thing I would do is renaming the link members (link[LEFT/RIGHT]) to "left" or "right".

Klaus
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> Nova All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group