Peter Zijlstra wrote: > On Thu, 2008-02-21 at 15:12 +0530, Balbir Singh wrote: >> Peter Zijlstra wrote: >>> On Thu, 2008-02-21 at 15:01 +0530, Balbir Singh wrote: >>> >>>> I have an alternate approach in mind (that I need to find time for), >>>> threaded-rbtrees. Walking the tree is really efficient, specially finding >>>> successor of a node. >>> Threading the rbtrees would be even more expensive, it would require a >>> list_head in each node and a full list operation for every tree >>> operation. >>> >> Peter, when I say threaded, I don't mean threaded as in tasks. Please see >> http://www.nist.gov/dads/HTML/threadedtree.html and >> http://datastructures.itgo.com/trees/tbt.htm > > I'm quite aware of the meaning of threaded in the context of data > structures.
Oh! I did not mean to assume anything. Just wanted to make sure we are talking of the same thing They usually require additional list data and operations to > implement. > >From the definition A Threaded Binary Tree is a binary tree in which every node that does not have a right child has a THREAD (in actual sense, a link) to its INORDER successor. You use the empty pointer (missing right child), so why do we need a list. May be I am missing something. > Look at how the latter link you provided grows the rb_node with one > pointer to provide a single linked list. > Yes, that's a bad example I suppose. Look at http://www.cs.rutgers.edu/~kaplan/503/thread.html -- Warm Regards, Balbir Singh Linux Technology Center IBM, ISTL -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [EMAIL PROTECTED] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/