平衡二叉树键

Question

我试图找出如何在二叉树中输入存储“线段”的元素。我正在读的计算几何书上说

更详细地说，我们存储与平衡二叉树T中的叶中排列的扫描线相交的段。沿扫描线的从左到右的顺序对应于T中叶的从左到右的顺序。

假设键是事件点的x/y值(这里是A或B)，那么在以下情况下，状态结构如何保持线段的正确顺序(虚线是扫描线)。

​

​

B明显地击中A之前的扫描行，但是如果B的段是由它添加的x/y值，则在状态行中它将在A之后。

因此，在我看来，状态线段的键不能是像点的x/y值那样的静态值，但是书中对于树是如何在这方面构造的非常安静。我见过一些例子，把键作为(m，b)的元组，其中m是直线梯度，b是y-截距，但我不太清楚它是如何工作的。

Answer 1

您需要在当前时刻以与它们相交的扫描线相同的顺序存储段。二进制搜索树是可能的，因为它的性质:左节点包含较低的键，右节点-更大的键。

由于结构的动态性，关键也将是动态的。每次在BST (二进制搜索树)中添加一个段时，您都需要在其Y坐标下比较键，该键是扫描线上交点的X分量。

在扫描线与B段或B段起始点交点的时刻，A段已经添加到A段起始点处的BST中。因此，按照BST项插入规则，如果B段的键大于或低于BST项的键，则需要检查B段的键，即Y处的X坐标。很明显，B在Y处的X坐标小于A在Y处的X坐标，所以B段将被添加到BST的左侧节点

      A
    /   \
   B     null
  / \
null null