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