diff options
Diffstat (limited to 'avl-1.4.0/TODO')
| -rw-r--r-- | avl-1.4.0/TODO | 92 |
1 files changed, 92 insertions, 0 deletions
diff --git a/avl-1.4.0/TODO b/avl-1.4.0/TODO new file mode 100644 index 0000000..0231395 --- /dev/null +++ b/avl-1.4.0/TODO @@ -0,0 +1,92 @@ +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 <demaille@inf.enst.fr> +Subject: Re: libavl +To: pfaffben@pilot.msu.edu +Date: 25 Sep 1998 16:04:03 +0200 + + +Sorry for the delays... + +Ben Pfaff <pfaffben@pilot.msu.edu> writes: + +> Akim Demaille <demaille@inf.enst.fr> 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 <dak@neuroinformatik.ruhr-uni-bochum.de> +Subject: Re: Your AVL tree page +To: pfaffben@pilot.msu.edu +Date: Mon, 23 Nov 1998 18:38:55 +0100 + + From: Ben Pfaff <pfaffben@pilot.msu.edu> + Date: 23 Nov 1998 12:12:31 -0500 + + David Kastrup <dak@neuroinformatik.ruhr-uni-bochum.de> 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 |