algorithm - 平衡二叉搜索树键
问题描述
我试图弄清楚如何键入存储“线段”的二叉搜索树的元素。我正在阅读的计算几何书说
更详细地说,我们将与扫描线相交的线段存储在平衡二叉搜索树 T 的叶子中。沿着扫描线的线段从左到右的顺序对应于叶子的从左到右的顺序在 T
假设关键是事件点的 x/y 值(此处为 A 或 B),在以下情况下状态结构将如何保持线段的正确顺序(虚线是扫描线)。
B 显然在 A 之前击中扫描线,但如果 B 的段加上它的 x/y 值,它将在状态行中的 A 之后。
因此,在我看来,状态行各段的键不能是静态值,例如点的 x/y 值——但是这本书在这方面如何构建树时非常安静。我已经看到了一些示例,将键作为 (m,b) 的元组,其中m
线条渐变和b
y 截距,但我不太清楚它是如何工作的。
解决方案
您需要以与当前时刻与扫描线相交的相同顺序存储线段。由于其性质,二叉搜索树是可能的:左节点包含较低的键,右节点 - 较大的键。
由于结构的动态特性,键也将是动态的。每次将段添加到 BST(二叉搜索树)中时,您都需要在其 Y 坐标处比较键,该键将是扫描线上交点的 X 分量。
在扫描线与 B 线段或 B 线段起点相交的时刻,A 线段已经在 A 线段起点添加到 BST 中。所以按照 BST 项目插入的规则,你需要检查 B 段的键,即 Y 处的 X 坐标,它是否大于或低于 BST 项目的键。很明显 B 的 Y 处的 X 坐标小于 A 的 Y 处的 X 坐标,所以 B 段将被添加到 BST 的左节点
A
/ \
B null
/ \
null null
推荐阅读
- java - 计算值的总和后如何将数组传递给 main 方法?
- c# - 将值插入外键记录
- javascript - Ionic cordova 按钮在 IOS 模拟器中不可点击
- scala - 如何使用 Spark/Scala 在窗口上做 approxQuantile?
- java - 如何将字符串与另一个字符串进行比较并获取索引?
- javascript - useSelector 中的“减少”
- typescript - 有什么方法可以用 Typescript 中的新成员进行递归部分
- android - kotlin string 有没有像 Objc static NSString kUrl = @"users/%@/profile"; 这样的程序员?
- javascript - 如何让我的 Javascript“动画”更好地工作?
- javascript - getDisplayMedia“无法启动音频源”