I have been looking into the sweep line algorithms of finding intersection of line segments and polygon partitioning using monotone polygons. The algorithms require a dynamically balanced binary tree which stores the sorted sequence of the elements in the leaves of the tree.I am familiar with Balanced Binary trees like AVL trees where the elements are stored in the inner leaves too. I am confused on how to implement such a data structure which only stores the data in the leaves and uses the inner nodes as splitter nodes.Please explain the data structure for storing the data in the leaves and it is helpful if any reference links are given.Thank you.
Data Structure for storing the Sweep Line Status in Sweep Line Algorithms
computational geometry