Messages in this thread | | | Date | Sat, 27 Nov 1999 23:29:33 -0600 (CST) | From | Oliver Xymoron <> | Subject | Re: AVL trees vs. Red-Black trees |
| |
On Sun, 28 Nov 1999, Andrea Arcangeli wrote:
> On Sat, 27 Nov 1999, Kevin O'Connor wrote: > > >I was a little surprised to see that the MM code uses an AVL tree - my old > >textbooks are of the opinion that Red-Black trees are superior. > > You basically do a query for each page fault and an insert for each mmap > and a remove for each munmap thus AVL gives better performances. > > >Implementing the code to create a stack for performing "bottom-up" > >insertions/deletions seems like a pain to me. I would think the "top-down" > >approach of a Red-Black tree would be more efficient and probably simpler > >to implement. > > I just implemented RB trees in the kernel with a reusable implementation > exactly like include/linux/list.h for the lists. > > If somebody find this interesting I can provide a patch to add the > include/linux/rbtree.h and lib/rbtree.c that will provde rbtree support.
I'd like to take a look at this, I've been looking at putting some more uniform tree structures in the kernel (post 2.4).
-- "Love the dolphins," she advised him. "Write by W.A.S.T.E.."
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |