-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
Hi everyone,
I have a first version Binary B-Tree implementation (in our countries traditionally denoted as 2-3-Trees).
Because I had quite foggy ideas of how these kind of things are working (though it is so easy to describe it informally), I have decided to complete my own implementation. It is a delicate problem and I am quite unsure that the way how I implemented it is the best (the clearest, the simplest etc) way. I have looked into Wirth's Algorithms and Data Structures, but it did not helped me much. I will try to ask people around me if they tried it and if so, how did they managed it.
Apart from operations for addition and removal of elements, the rest code should be readable. I almost like it.
Anyone willing to play with this new collection can install it this way: - - install the `COND' package (unfortunatelly, this is necessary) - - install the `BBTree' package
I have found out that sorted-collection are more effective than BB-trees when there are fewer elements in the collection (1000 or so). But as number of elements in the collection increases (to 100000 or so), it is evident that BB-tree rulez. There is an example method
BBTree example1
which - - creates new BB-tree - - adds 100000 intergers (could be any other objects which could be totally ordered) in some (random) order to the BB-tree - - removes those object (at different, also random) order from the BB-tree
It is possible to observe (there is a progress-bar) that addition and removal operations virtually do not depend on the number of elements in the collection (or if, then very "little", because height of the tree grows very "slowly")
On the other hand, there is an example
BBTree example2
which does the same as `example1' but not with BB-tree but ordinary SortedCollection. It is observable that the addition/removal operations depend on the number of elements in the collection. It is also visible that removal is much more expensive than addition.
As I mentioned, addition and removal operations are bad. It is straightforward realization of non-trivial operation. I am not sure if I could rewrite it in a simpler way soon. But if I find out how, I will do it. But there might be also other things I have forgotten to do or could be done better. So comments are welcome.
Regards - -- Matej Košík