基于二维坐标点构建二叉树，应选用何种比较键？

选择比较键的核心是匹配你的二叉树用途和数据访问需求，以下是几种实用方案：

普通二叉搜索树（BST）场景 #

普通BST需要全序关系，得把二维坐标映射为一维键：

• 字典序组合：优先比较x坐标，x相等时再比较y坐标。比如点(2,3)小于(2,4)，小于(3,1)。这种方式能保证严格的全序，适合需要按坐标顺序遍历、排序输出的场景。
• 坐标合并值：用公式x * M + y生成单一数值（M要大于y的最大可能取值，避免不同(x,y)生成相同值），或者直接用点的哈希值。适合对有序性要求不高、只需要快速插入查找的场景，但哈希可能存在冲突风险。

多维查询优化场景（KD树） #

如果需要做范围查询、最近邻搜索这类多维操作，别用普通BST，改用KD树，此时比较键是交替使用x和y坐标：

• 根节点用x坐标划分：左子树存放x小于根节点x值的点，右子树存放x大于的点；
• 下一层节点切换为y坐标划分，再下一层回到x，以此类推；
• 这种分层交替的键选择，能让树更好地适配二维空间的划分，大幅提升多维查询效率。

特定场景定制键 #

• 极坐标键：选定一个原点，计算每个点的极角（或极角+距离）作为比较键。适合需要围绕原点做辐射状遍历、查询的场景。

选择依据总结 #

• 需全序遍历/排序：选字典序组合键；
• 需多维空间查询：用KD树的交替坐标键；
• 特定空间关系需求：定制对应键（如极坐标）。

内容的提问来源于stack exchange，提问作者Newtron Malayalam