# Shamos-Hoey Line segment intersection runtime

In the Shamos-Hoey algorithm for finding whether or not any two of $n$ line segments intersect, which is available at this site: http://geomalgorithms.com/a09-_intersect-3.html, there is use of "nearest line above" and "nearest line below". The algorithm is supposed to run in time $O(n\log n)$. Here is their pseudocode:

Initialize event queue EQ = all segment endpoints;
Sort EQ by increasing x and y;
Initialize sweep line SL to be empty;

While (EQ is nonempty) {
Let E = the next event from EQ;
If (E is a left endpoint) {
Let segE = E's segment;
Let segA = the segment Above segE in SL;
Let segB = the segment Below segE in SL;
If (I = Intersect( segE with segA) exists)
return TRUE;   // an Intersect Exists
If (I = Intersect( segE with segB) exists)
return TRUE;   // an Intersect Exists
}
Else {  // E is a right endpoint
Let segE = E's segment;
Let segA = the segment above segE in SL;
Let segB = the segment below segE in SL;
Delete segE from SL;
If (I = Intersect( segA with segB) exists)
return TRUE;   // an Intersect Exists
}
remove E from EQ;
}
return FALSE;      // No  Intersections


If one studies the C++ code provided at the bottom of the webpage, we see that this is simply a "next" and "previous" in a BST, however, I can't seem to tell which information is being used as the BST key.

My issue is the following: if we are considering all $y$-values at the current $x$-value of the sweep line, this is not merely a check for next or previous endpoint value in a BST, and can not take $O(\log n)$ time. However, if we are checking per endpoint coordinate, this could not possibly be correct, since the following situation would lead to an incorrect execution:

The algorithm should find that $B$ and $C$ intersection on insertion of $B$ into the search tree ("SweepLine" / "SL") while sweeping. However, if we are ordering by endpoint coordinates, $A$ is $B$'s previous, $C$ is not, and this would run into problems.