TODO ---- * Write `bare' no-rebalancing version for comparison purposes. * In avl_delete's D9 it may be faster to move the data instead of moving around all the pointers. Consider the situation carefully. * avl_traverse_{fwd,rev}; avl_find_traverse * Generalized testing framework; for instance, could compare with kazlib and avllib implementations. * Merge algorithm paper into documentation. ---------------------------------------------------------------------- From: Akim Demaille Subject: Re: libavl To: pfaffben@pilot.msu.edu Date: 25 Sep 1998 16:04:03 +0200 Sorry for the delays... Ben Pfaff writes: > Akim Demaille writes: > > And finaly, for the application I want to make of libavl, I have > sometimes to merge two avls, say the second into the first, while > specifying, when conflict, whether it is always the first or the > second that wins. > > I can easily make this using your api, nevertheless, I wanted to ask > you whether you know none brute-force approaches, or even whether > this kind of features might appear in the future. > > Knuth describes an elegant algorithm for merging two avls, but it only > works if all the values in one of them is smaller than all the values > in the other. > > If you do think of a clever algorithm for doing this, please let me > know and I'll incorporate it into the API. I know none. but looking on the web, I found one in haskell :) I didn't look whether it was smart or not. http://www.cs.chalmers.se/pub/haskell/library/avl-tree.lgs There is not much material. I think comp.compiler is a good place to ask for an algorithm... Akim ---------------------------------------------------------------------- From: David Kastrup Subject: Re: Your AVL tree page To: pfaffben@pilot.msu.edu Date: Mon, 23 Nov 1998 18:38:55 +0100 From: Ben Pfaff Date: 23 Nov 1998 12:12:31 -0500 David Kastrup writes: You might want to take a look at the texts at http://www-lsi.upc.es/www/dept/techreps/1998.html In particular the paper http://www-lsi.upc.es/dept/techreps/ps/R98-12.ps.gz might be interesting, as it gives an AVL-tree mechanism for multi-threaded, distributed access. Thanks for the pointers. It seems that connectivity to that machine is really slow from here, at least right now, so I'll try to take a look at them a little later. Currently there is no multithread support in libavl, but it might be nice to add it later. Well, the reference will probably not be what you think it is. It is intended to not properly balance the tree during the access when that would mean locking the entire tree. Instead, it does only local corrections that eventually probagate to the top. One can also let a "garbage collect" thread run that will optimize the data structures at idle times, but will let them deteriorate a bit rather than fix them up properly under stress. This is, of course, especially interesting for internal data structures of an operating system, where full balancing at the time of access will slow operations down, but there will be idle times when balancing can occur without overhead. David Kastrup Phone: +49-234-700-5570 Email: dak@neuroinformatik.ruhr-uni-bochum.de Fax: +49-234-709-4209 Institut für Neuroinformatik, Universitätsstr. 150, 44780 Bochum, Germany