diff options
Diffstat (limited to 'avl-1.4.0/TODO')
| -rw-r--r-- | avl-1.4.0/TODO | 92 |
1 files changed, 0 insertions, 92 deletions
diff --git a/avl-1.4.0/TODO b/avl-1.4.0/TODO deleted file mode 100644 index 0231395..0000000 --- a/avl-1.4.0/TODO +++ /dev/null @@ -1,92 +0,0 @@ -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 |