1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
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
|
