kd树的原理简述

1️⃣定义：给定一个二叉树与点集 P = { x 1 , x 2 , . . . , x N } ⊆ R 2 P=\{x_1,x_2,...,x_N\}\subseteq{}\mathbb{R}^2 P={x1​,x2​,...,xN​}⊆R2

1. 对应关系：$\{\begin{array}{l}叶结点i\stackrel{一一对应}{\leftrightarrow }点x_i\\ \\ 中间结点u\stackrel{一多对应}{\leftrightarrow }以u为根子树的叶结点(P_u)\stackrel{一一对应}{\leftrightarrow }包住P_u所有点的矩形{\Delta }_u\\ \\ 根结点r\stackrel{一一对应}{\leftrightarrow }所有点(P_r=P)\end{array}$
2. 分割操作：从$u$开始下降$\to \{\begin{array}{l}\text{level}(u)为偶数\to 将原矩形竖切\\ \\ \text{level}(u)为奇数\to 将原矩形横切\end{array}$

2️⃣示例：