This is a cross-post from stackoverflow. I did not recieve a good answer, I guess it is because the question is more theoretical.
I have to implement Fortunes algorithm for constructing Voronoi diagrams.
Important part of the algorithm is a data structure called "Beach Line Data Structure".
It is a binary balanced tree, similar to AVL, but different in a way that data is stored only on the leafs (there are other differences, but are unimportant for the question).
I am not sure how to implement it. Obviously using AVL "as is" will not work because when balancing AVL tree leaf node can become inner node and vice versa.
I also tried to look at some other known data structures at wikipedia, but none suits the needs. I have seen some implementations that do this with a linked list, but this is not good because searching linked list is O(n), and it needs to be O(log n) for the algorithm to be efficient.
I would like to take a look at a description of such data structure. I have no problem in implementing, but inventing a new structure of balanced tree is too much for me.