View previous topic :: View next topic |
Author |
Message |
clayasaurus
Joined: 21 May 2004 Posts: 857
|
Posted: Thu Oct 19, 2006 9:25 am Post subject: intrusive red-black tree... |
|
|
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 |
|
|
KlausO
Joined: 16 Feb 2006 Posts: 27 Location: Germany
|
Posted: Fri Oct 20, 2006 5:53 am Post subject: |
|
|
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
I will try to add it this weekend. |
|
Back to top |
|
|
clayasaurus
Joined: 21 May 2004 Posts: 857
|
Posted: Mon Oct 23, 2006 3:50 pm Post subject: |
|
|
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 |
|
|
KlausO
Joined: 16 Feb 2006 Posts: 27 Location: Germany
|
Posted: Thu Oct 26, 2006 4:25 pm Post subject: |
|
|
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 |
|
|
|
|
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
|