KD-Tree的2D平面简单实现

kd-tree也是一种二叉树，不过这种二叉树的Key不再局限于一维，而有可能是二维或三维，也可称作2d-tree或3d-tree
kd-tree非常适用于几何数据的处理，如平面或空间中的点等等，处理起来极为高效，那kd-tree是如何处理多维数据的呢？
如下所示，是一个简单的2d-tree示意图

2d-tree的每一个节点都具有一个标识符，用于判别该节点是通过哪一个维度的Key来进行比较的，几何意义就是该节点是如何划分2D平面空间的。 如图中的竖线表示在该点下将2D平面分为左右两个子平面，则将x坐标作为Key来进行比较两个点的大小， x较小的作为left child node，放在左半边平面， x 较大的作为right child node ，放在右半边平面；而横线又表示将2D平面分为上下两个子平面， 则将y坐标作为key来进行比较两个点的大小，y较小的作为left child node，放在下半部平面， 而y较大的作为right child node，放在上半部平面。

如下图所示，一个点一个点的插入kd-tree数据结构中

因此就可以在每次insert新的node的时候，自适应大小迭代的将空间一分为二，并将数据存放入其中，大大的提高了搜索、查找、取值的效率，甚至还可以对空间中的数据进行整体的操作。

如下图，3D空间中的点也是同样的道理，3维的空间可以根据x,y,z坐标分别将3D空间分为左右、前后、上下两个部分，并存取数据。

这里就简易实现了2d-tree的插入和搜索功能，代码如下：

首选是点类class Point2D

// 点类 class Point2D{ public: double x; double y; public: // 构造函数 Point2D(){} Point2D(double _x , double _y){ if(_x == DBL_MAX || _y == DBL_MAX || _x == DBL_MIN || _y == DBL_MIN ){ cout << "Error : coordinates should be finite !" << endl; } if(_x == NULL || _y == NULL){ cout << "Error : coordinates cannot be NULL !" << endl; } this->x = _x; this->y = _y; } Point2D(const Point2D &p){ this->x = p.x; this->y = p.y; } //返回x double _x(){ return this->x; } //返回y double _y(){ return this->y; } //欧氏距离 double distanceTo(Point2D that){ double dx = this->x - that.x; double dy = this->y - that.y; return sqrt(dx * dx + dy * dy); } // 欧氏距离的平方 double distanceSquaredTo(Point2D that){ double dx = this->x - that.x; double dy = this->y - that.y; return dx * dx + dy * dy; } // 比较大小： // 比较大小：X_order int compareTo_Xorder(Point2D that){ if(this->x < that.x){ return -1; }else if (this->x == that.x) { return 0; }else if (this->x > that.x) { return 1; } } // 比较大小：Y_order int compareTo_Yorder(Point2D that){ if(this->y < that.y){ return -1; }else if (this->y == that.y) { return 0; }else if (this->y > that.y) { return 1; } } //是否相等 bool equals(Point2D that){ if(this->x == that.x && this->y == that.y){ return true; } return false; } string toString(){ return "(" + to_string(this->x) + "," + to_string(this->y) + ")" ; } }; 

然后是Node类，Node类中增加一个变量bool direction, 宏定义VERTICAL = true , HORIZONTAL = false

#define VERTICAL 1
#define HORIZONTAL 0

//首先是kd-tree的Node


class Node{
public:

    // 节点Node里存储一个Point2D
    Point2D p ;
    Node * left;
    Node * right;

    //还有一个方向标识符：判断这个节点如何划分平面
    bool direction;

    int count; // 用于计数，该node下的child node 总数

    Node(Point2D & _p , int _count , bool _direction){
        this->p = _p;
        this->count = _count;
        this->direction = _direction;
        this->left = NULL;
        this->right = NULL;
    }



};

最后就是这个KdTree，由于思想和代码基本和二叉搜索树一致，这里就只简要写了搜索函数和查找函数，其他都和BSTs一样。

class KdTree{
private:
    // kd-tree的根节点
    Node * root;

    // 返回节点node的count
    int size(Node * x){
        return x->count;
    }


    // ***************************一些递归函数的实现**********************

    Node * insert(Node * x , bool parent_direction ,  Point2D p){
        if(x == NULL){
            // 如果当前节点为空了， 就可以创建一个新的节点了， 不过创建的新的节点的划分空间的方向是根据父节点的方向来决定的，与父节点相反
            return new Node( p , 1 , !parent_direction);
        }

        // 如果与当前节点完全相同， 则不插入了， 直接返回
        if(p.x == x->p.x && p.y == x->p.y){
            return x;
        }

        // 得到当前节点x的空间划分方向
        bool x_direction = x->direction;


        // 比较他们的大小
        int compare_result;

        if(x_direction == VERTICAL){

            // 如果以垂直划分， 则比较两个点的x坐标
            compare_result = p.compareTo_Xorder(x->p);
        }else if (x_direction == HORIZONTAL) {
            // 如果以水平划分 ， 则比较两个点的y坐标
            compare_result = p.compareTo_Yorder(x->p);
        }

        // 得到比较结果， 就可以根据比较结果决定插入left child node还是right child node了

        if(compare_result == -1){
            x->left = insert(x->left , x_direction , p);
        }else if (compare_result == 1) {
            x->right = insert(x->right , x_direction , p);
        }else if (compare_result == 0) {
            // 如果相等（只是代表这两个point的x坐标相等或y坐标相等， 并不代表x，y坐标都相等）
            // 此时都是往right subtree走
            x->right = insert(x->right , x_direction , p);
        }

        // 更新x节点的总数 ： left subtree的总数 + right subtree的总数+ 自己
        x->count = 1 + size(x->left) + size(x->right);
        return x;

    }



public:
    KdTree(){
        this->root = NULL;
    }

    bool isEmpty(){
        if(this->root == NULL){
            return true;
        }else{
            return false;
        }
    }

    int size(){
        return size(this->root);
    }

    // 插入一个点Point
    void insert(Point2D p){
        this->root = insert(this->root , HORIZONTAL , p);
    }


    // 看这个kd-tree是否包含某个Point p
    bool contain(Point2D p){

        Node * x = this->root;
        while (x != NULL) {

            // 如果这两个点相等， 则返回true
            if(p.x == x->p.x && p.y == x->p.y){
                return true;
            }

            // 否则继续去left child 或right child 找

            bool direction = x->direction;

            int compare_result ;

            if(direction == VERTICAL){
                compare_result = p.compareTo_Xorder(x->p);

            }else if (direction == HORIZONTAL) {
                compare_result = p.compareTo_Yorder(x->p);
            }

            if(compare_result == -1){
                x = x->left;
            }else if (compare_result == 1 || compare_result == 0) {
                x = x->right;
            }


        }

        return false;



    }


};