GIS空间数据库（12）KD树索引（二叉树索引）

KD树定义

KD树的每个内部结点都包含一个点，每个结点表示k维空间中的一个点，并且和一个矩形区域相对应，树的根结点和整个研究区域相对应。KD树要求用平行于坐标轴的纵横分界线将平面分为若干区域，使每个区域中的点数不超过给定值。树中奇数层次上的点的x坐标和偶数层次上的点的y坐标把矩形区域分成两部分。分界线仅起分界的作用，它的选取没有硬性的限制。一般选用通过某点的横向线或者纵向线。分界线上的点，对左右分界线来说属于右部，对上下分界线来说属于上部。 如图:

KD树查找

伪代码

Algorithm KD_Search（R，P）
/*在根结点为R的KD树（子树）中查找点P。找到则返回结点，否则返回NULL*/
Begin
  If R=NULL Then Return NULL；//Not Found
  If R. Point=P Then Return R；//Found；
Else
  Begin
    d：=Discriminator of R；
    If P[d] <R Point[d] Then /*比较P点与R结点的第D维的值*/
      KD_Search（R.Lchild，P）//在左子树继续查找
    Else
      KD_Search（R.Rchild，P）//在右子树继续查找
  End
End.

KD树插入

伪代码

Algorithm KD_Insert（R,P,F）
/*在根结点为R的KD树（子树）中插入点P，F为R的父结点*/
Begin
  If R=NULL Then
    Begin
      Create a Node P；
      If F=NULL Then //KD树为空
        Root：=P//P成为根结点
      Else
        If R Is the Left child of F Then
          F.Lchild：=P//P作为F的左孩子
        Else F.Rchild：=P//P作为F的右孩子
    End
    Else
      Begin
        d：=Discriminator of R；
        If P[d]R.Point[d] Then/*比较P点与R点的第D维的值*/
          KD_Insert（R.Lchild,P,R）//插入到左子树中
        Else
         KD_Insert（R.Rchild,P,R）// 插入到右子树中
     End;
End;

KD树删除

Algorithm KD_Delete（R,P）
/*在根结点为R的KD树（子树）中点P，删除成功返回True，否则返回False */
Begin
      Q：= KD_Search（R,P）；//Q为要删除的对象
      LABEL；
      If Q=NULL Then Return False；//Not found
      If （Q.Lchild=NULL） And （Q.Rchild=NULL） Then
        Begin//第一种情况
          F：=Q is Father Node；
          If Q is the left Child of F then
            F.Lchild：=NULL
          Else F.Rchild：NULL；
            Delete Node Q；
          Return True；
       End
    Else
      Begin
         If （Q.Rchild=NULL） Then第三种情况转化为第二种情况处理
            Q.Rchild：=Q.Lchild；
         M：=FindMin（Q.Rchild）；
      （Q）←（M）；//将M结点的值赋给Q结点
        Q：=M；//让Q指向M结点
        GOTO LABEL；//继续删M结点
    End
end