Re: [dev] Simple question

From: Dimitris Papastamos <dp_AT_spl9.org>
Date: Wed, 23 Jul 2014 20:10:09 +0100

On Wed, Jul 23, 2014 at 07:49:09PM +0200, Guillaume Quintin wrote:
> Hi,
>
> I was wondering if there was some program out there that uses
> algorithms such as red-black trees, B-trees, binomial heaps, fibonacci

rb-trees/avl trees can be found in many programs. Do a code search on
the macros defined in tree.h (originally a BSD header). A few years ago
I worked on a caching layer[0] using rb-trees (splay trees would have been
another choice but the kernel lacked an implementation).

In my experience B-trees are used much less frequently than rb-trees.
They are usually found in filesystem implementations.

binomial heaps are useful for implementing priority queues. Again look
up some standard interfaces to find examples of how to use them.

I've never seen a fibonacci heap in any of the projects I've worked on.

[0] http://lxr.free-electrons.com/source/drivers/base/regmap/regcache-rbtree.c
Received on Wed Jul 23 2014 - 21:10:09 CEST

This archive was generated by hypermail 2.3.0 : Wed Jul 23 2014 - 21:12:07 CEST