kd-tree: 重复键和删除
kd-tree: duplicate key and deletion
在这些slides(13)中删除一个点在akd-tree中是这样描述的：表示左子树可以交换为右子树，如果被删除的节点有只有一个左子树。然后可以找到最小值并递归删除（就像右子树一样）。
这是因为kd-tree当前维度的等键应该在右边。
我的问题：为什么等键点一定要在parent点的右边children？另外，如果我的 kd-tree 算法 returns 左边有相同关键点的树会怎样？
例如：
假设数据集 (7,2), (7,4), (9,6)
结果 kd-tree 将是（相对于一个轴排序）：
(7,2)
/ \
(7,4) (9,6)
另一个陈述相同理论的来源是 this 一个（示例 15.4.3 上面的段落）
Note that we can replace the node to be deleted with the least-valued node from the right subtree only if the right subtree exists. If it does not, then a suitable replacement must be found in the left subtree. Unfortunately, it is not satisfactory to replace N's record with the record having the greatest value for the discriminator in the left subtree, because this new value might be duplicated. If so, then we would have equal values for the discriminator in N's left subtree, which violates the ordering rules for the kd tree. Fortunately, there is a simple solution to the problem. We first move the left subtree of node N to become the right subtree (i.e., we simply swap the values of N's left and right child pointers). At this point, we proceed with the normal deletion process, replacing the record of N to be deleted with the record containing the least value of the discriminator from what is now N's right subtree.
两者都指的是只有左子树的节点，但为什么会有什么不同？
谢谢！
没有硬性规定只在右边有相同的键。您也可以将其更新为左侧。
但是这样做，您还需要更新搜索和删除操作的算法。
查看这些链接：
https://www.geeksforgeeks.org/k-dimensional-tree/
https://www.geeksforgeeks.org/k-dimensional-tree-set-3-delete/
在这些slides(13)中删除一个点在akd-tree中是这样描述的：表示左子树可以交换为右子树，如果被删除的节点有只有一个左子树。然后可以找到最小值并递归删除（就像右子树一样）。
这是因为kd-tree当前维度的等键应该在右边。
我的问题：为什么等键点一定要在parent点的右边children？另外，如果我的 kd-tree 算法 returns 左边有相同关键点的树会怎样？
例如： 假设数据集 (7,2), (7,4), (9,6) 结果 kd-tree 将是（相对于一个轴排序）：
(7,2)
/ \
(7,4) (9,6)
另一个陈述相同理论的来源是 this 一个（示例 15.4.3 上面的段落）
Note that we can replace the node to be deleted with the least-valued node from the right subtree only if the right subtree exists. If it does not, then a suitable replacement must be found in the left subtree. Unfortunately, it is not satisfactory to replace N's record with the record having the greatest value for the discriminator in the left subtree, because this new value might be duplicated. If so, then we would have equal values for the discriminator in N's left subtree, which violates the ordering rules for the kd tree. Fortunately, there is a simple solution to the problem. We first move the left subtree of node N to become the right subtree (i.e., we simply swap the values of N's left and right child pointers). At this point, we proceed with the normal deletion process, replacing the record of N to be deleted with the record containing the least value of the discriminator from what is now N's right subtree.
两者都指的是只有左子树的节点，但为什么会有什么不同？ 谢谢！
没有硬性规定只在右边有相同的键。您也可以将其更新为左侧。
但是这样做，您还需要更新搜索和删除操作的算法。
查看这些链接：
https://www.geeksforgeeks.org/k-dimensional-tree/
https://www.geeksforgeeks.org/k-dimensional-tree-set-3-delete/