数据结构中 树（重点kdtree）

时间：2021-03-19 12:38:42

                                                                      （一）树

一）树的定义

树（Tree）是n个（n>=0）个结点的有限集。 n=0时称之为空树。在任意一个非空树中：

（1）有且仅有一个特定的称为根（Root）的结点；

（2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,T3...Tm，其中每个集合本身就是一棵树，并且称为根的子树（Subtree）

注：n>0时，树根仅为1，不可能存在多个根结点；m>0时，子树的个数没有限制，但是他们互不相交（相交及为图）。

数据结构中 树（重点kdtree）

1.1 结点分类

树的结点包含一个数据元素及若干个指向其子树的分支。

结点拥有的子树称之为结点的度。 

度为0的结点称之为叶子结点（Leaf）或终端结点；度不为0的节点称之为非终端结点或分支结点。

除根节点外，分支结点也称之为内部结点。树的度是树内各结点度的最大值；

数据结构中 树（重点kdtree）

1.2结点间的关系

结点的子树的根称之为该结点的孩子(Child），相应的，该结点称之为还在的双亲（Parent）.

同一个双亲的孩子之间互称兄弟（Sibling）。结点的祖先是从根到该结点所经分支上所有结点。

以某一结点为根的子树中，任意结点都称为该结点的子孙。

数据结构中 树（重点kdtree）

1.3树的其他相关概念

结点的层次（level）从根开始定义起，根为第一层，根的孩子为第二层。

双亲在同一层的结点，互称之为堂兄弟。树中结点最大的层次称之为树的深度（Depth）或者高度。

数据结构中 树（重点kdtree）

如果将树中结点的各个子树看成从左向右，不能互换的，则称该树为有序树，否则为无序树。


森林（Forest）是m个（m>=0）棵不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。


线性结构和树形结构对比

线性结构： 第一个元素：无前驱；最后一个元素：无后继； 中间元素：一个前驱，一个后继

树形结构： 根结点：无双亲，唯一； 叶子结点：无孩子，可以多个； 中间结点：一个双亲，多个孩子


                                                           

二）树的存储结构

2.1 双亲表示法

假设以一组连续控件存储树的结点，同时在每个结点中，附设一个指示器指向其双亲结点到链表中的位置。

data是数据域，存储结点的数据信息。而parent是指针域，存储结点的双亲在数组中的下标。


结点结构定义代码：

[cpp]  view plain copy
  1. // 树的双亲表示法结点定义  
  2. #define MAX_TREE_SIZE 100  
  3. typedef int TElemType;  
  4.   
  5. typedef struct PTNode               //结点结构  
  6. {  
  7.     TElemType data;                 //结点数据  
  8.     int parent;                     //双亲位置  
  9. }PTNode;  
  10.   
  11. typedef struct                      //树结构  
  12. {  
  13.     PTNode node [MAX_TREE_SIZE]；    //结点数组  
  14.     int r,n;                        //根的位置和结点树  
  15. }PTree;  

由于根结点没有双亲，则约定根节点的位置域设置为 -1 。


数据结构中 树（重点kdtree）


对于这种存储结构，我们可以根据结点的parent域来很容易的找到它的双亲结点，所以时间复杂度为O(1)。直到parent为-1为止，表示找到了树结点的根。

但是对于找到结点孩子是谁时，需要遍历整个结构才行。可以通过增加域来增加这种结构的灵活性。


2.2孩子表示法

每个结点有多个指针域，其中每个指针指向一棵子树的根节点，这种方法叫多重链表表示法。


把每个结点的孩子排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点，则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。

数据结构中 树（重点kdtree）

为此需要准备两种数据结构，一种是孩子链表的结点，其中child为数据域，用来存储某个结点在表头数组中的下标。next是指针域，用来存储指向某结点的下一个孩子结点指针。

另外一种是表头数组的表头结点。data为数据域，存储某结点的数据信息，firstchild是头指针域，存储该结点孩子链表的头结点。


[cpp]  view plain copy
  1. // 树的孩子表示法结构定义  
  2.   
  3. #define MAX_TREE_SIZE 100  
  4.   
  5. typedef struct CTNode       //孩子结点  
  6. {  
  7.     int child;  
  8.     struct CTNode *next;  
  9. } *ChildPtr;  
  10.   
  11. typedef struct              //表头结构  
  12. {  
  13.     TElemType data;  
  14.     ChildPtr firstchild;  
  15. } CTBox;  
  16.   
  17. typedef struct              // 树结构  
  18. {  
  19.     CTBox nodes[MAX_TREE_SIZE]； //结点数组  
  20.     int r,n;                    //跟的位置和结点数  
  21. }CTree;  

这种结构对于我们查找某个结点的孩子，或者某个结点的兄弟，只需要查找这个结点的孩子链表即可。对于遍历整个树也是很方便，对头结点的数组循环即可。

但是如果要找某个结点的双亲，则需要遍历整个树才行。 但是可以把双亲标识法和孩子表示法综合起来。

数据结构中 树（重点kdtree）



2.3孩子兄弟表示法

任意一棵树，他的结点的第一个孩子如果存在就是唯一的，他的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一孩子和此结点的右兄弟。

data为数据域，firstchild为指针域，存储结点的第一个孩子结点的存储地址，rightsib指针域，存储该结点的有兄弟结点存储地址


[cpp]  view plain copy
  1. // 树的孩子兄弟表示法结构定义  
  2. typedef struct CSNode  
  3. {  
  4.     TElemType data;  
  5.     struct CSNode *firstchild, *rightsib;  
  6. }CSNode, *CSTree;  

数据结构中 树（重点kdtree）


                                                             （ 二）二叉树

                                                                  2.1 二叉树的定义

二叉树（Binary Tree） 是n（n>=0）个结点的有线集合，该集合或者为空集（称空二叉树），或者由一个根结点和两颗互不相交的，分别称之为根结点的左子树和右子树的二叉树构成。


数据结构中 树（重点kdtree）


2.1.1二叉树特点

1，每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。

2，左子树和右子树是有顺序的，次序不能任意颠倒。

3，即使树中某个结点只有一棵子树，也要区分它是左子树还是右子树。


五种基本形态：

1，空二叉树；

2，只有一个根结点；

3，根结点只有左子树；

4，根节点只有右子树；

5，根节点既有左子树又有右子树。


对于三个结点的树，若只考虑形态，只有两种状况，但是二叉树是区分左右的，所以就演变成五种形态。

数据结构中 树（重点kdtree）


2.1.2 特殊二叉树

1，斜树

所有的结点只有左子树的二叉树叫做左斜树，所有结点只有右子树的二叉树叫做右斜树。

特点，每层只有一个结点，结点的个数与二叉树的深度相同


2，满二叉树

在一棵二叉树中，如果所有的分支都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

数据结构中 树（重点kdtree）


单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有的叶子结点都在同一层上，这样做到了整棵树的平衡。


满二叉树的特点：

1，叶子只能出现在最下面一层。

2，非叶子结点的度一定是2。

3，在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。


3，完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号i (1<=i<=n)的结点与同样深度的满二叉树序号为i的结点在二叉树中的位置完全相同，则这个二叉树为完全二叉树。

数据结构中 树（重点kdtree）


满二叉树一定是一棵完全二叉树，但是完全二叉树不一定是满二叉树。

完全二叉树的所有结点与同样深度的满二叉树，他们按层序号的结点，是一一对应的。


完全二叉树的一些特点：（判断方法）

1，叶子结点只能出现在最下面两层；

2，最下层的叶子一定集中在左边连续位置；

3，倒数两层，若有叶子结点，一定都在右部连续位置；

4，如果结点度为1，则该结点只有左孩子，不可能存在只有右子树的情况；

5，同样结点树的二叉树，完全二叉树的深度最小。


                                                               2 .2 二叉树的性质

二叉树性质1

性质1： 在二叉树的第i层上至多有2^(i-1)个结点。（i>=1）


二叉树性质2

性质2：深度为k的二叉树至多有2^k-1个结点（k>=1）

注：是2^k -1


二叉树性质3

性质3：对任何一棵二叉树T, 如果其终端结点(叶子结点)数为n0, 度为2的结点数为n2,则 n0 = n2 +1;


二叉树性质4

性质4：具有n个结点的完全二叉树的深度为[log2n] + 1.


二叉树性质5

性质5：如果对一棵有n个结点的完全二叉树（其深度为[log2n] + 1）的结点按层序号，对任一结点i (1<= i<=n)有：

1，如果i =1, 则结点i是二叉树的根，无双亲；如果i>1, 则其双亲是结点[i/2];

2，如果2i > n, 则结点i 无左孩子（结点i为叶子结点）；否则其左孩子是结点2i;

3，如果2i + 1 > n,则结点 i无右孩子； 否则其有孩子是结点 2i+1;



2.2.2 二叉树的存储结构

二叉树顺序存储结构

二叉树的顺序存储结构就是用一维数组存储二叉树中的结点，并且结点的存储位置，也就是数组的下标需要体现结点间的逻辑关系。

数据结构中 树（重点kdtree）


这只是对于完全二叉树，但是对于一般二叉树，尽管层序编号不能反映逻辑关系，但是可以将其按完全二叉树编号，只不过，把不存在的几点设置为”/\“。

数据结构中 树（重点kdtree）

对于极端情况，一棵深度为K的右斜树，他只有K个几点，却要分配2^k -1个存储单元的空间。这显然是对存储空间的浪费。 所以对于顺序存储，一般只用在完全二叉树结构。


数据结构中 树（重点kdtree）



2.2.3  二叉链表

二叉树每个结点最多有两个孩子，所以为他涉及一个数据域和两个指针域，称这样的链表叫做二叉链表。

数据结构中 树（重点kdtree）

其中data是数据域，lchild 和 rchild 都是指针域。分别存放指向左孩子和有孩子的结点。

[cpp]  view plain copy
  1. // 二叉树的二叉链表结点结构定义  
  2. typedef struct BiTNode  
  3. {  
  4.     TELemType data;  
  5.     struct BiTNode *lchild,*rchild;  
  6. }BiTNode, *BiTree;  

                                                                      2.3遍历二叉树

二叉树遍历原理

二叉树的遍历，是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅仅被访问一次。


二叉树遍历方法：

二叉树的遍历方式很多：

1，前序遍历：

规则是若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

数据结构中 树（重点kdtree）


2，中序遍历

若树为空，则空操作返回，否则从根节点开始（并不是先访问根节点），中序遍历根节点的左子树，然后访问根节点，最后中序遍历右子树。

数据结构中 树（重点kdtree）


3，后序遍历

若树为空，则空操作返回，否则从左到右先叶子后根结点的方式遍历访问左右子树，最后是访问根结点。

数据结构中 树（重点kdtree）


4，层序遍历

若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。

数据结构中 树（重点kdtree）


前序遍历算法

二叉树定义是用递归的方式，所以，实现遍历算法也可以采用递归方式

[cpp]  view plain copy
  1. // 二叉树的先序遍历算法  
  2.   
  3. void PreOrderTraverse(BiTree T)  
  4. {  
  5.     if（T == NULL）  
  6.         return;  
  7.   
  8.     printf("%c",T->data);   //显示结点数据  
  9.   
  10.     PreOrderTraverse(T->lchild);    //先序遍历左子树  
  11.     PreOrderTraverse(T->rchild);    //最后先序遍历右子树  
  12. }  

非递归方式：

[cpp]  view plain copy
  1. void PreOrderTraverseNo(BiTree T)  
  2. {  
  3.     BiTree p,q;  
  4.     *p = T;  
  5.     int top;       // 栈顶索引  
  6.   
  7.     BiTree stack[MAX_SIZE] = {0};   //初始化栈  
  8.   
  9.   
  10.     if(T == NULL)  
  11.     {  
  12.         return NULL:  
  13.     }  
  14.     else  
  15.     {  
  16.         while(p != NULL)              
  17.         {  
  18.             cout<< p->data;         //访问结点  
  19.   
  20.             q = p->rchild;          //取其右子树结点  
  21.   
  22.             if(q != NULL)           //不空，压栈  
  23.                 stack[++top] = q;  
  24.   
  25.             p = p->lchild;          //遍历左子树  
  26.   
  27.             if(p == NULL)           //为空弹栈，找右子树  
  28.                 p = stack[top--];  
  29.         }  
  30.     }  
  31. }  


中序遍历算法

[cpp]  view plain copy
  1. // 二叉树的中序遍历算法  
  2.   
  3. void InOrderTraverse(BiTree T)  
  4. {  
  5.     if(T == NULL)  
  6.         return;  
  7.   
  8.     InOrderTraverse(T->lchild); //中序遍历左子树  
  9.     printf("%c",T->data);       // 显示结点数据，可以更改为其他的对结点操作  
  10.     InOrderTraverse(T->rchild); //最后中序遍历右子树  
  11. }  

后序遍历算法

[cpp]  view plain copy
  1. // 二叉树的后序遍历算法  
  2.   
  3. void PostOrderTraverse(BiTree T)  
  4. {  
  5.     if(T == NULL)  
  6.         return;  
  7.   
  8.     PostOrderTraverse(T->lchild); //后序遍历左子树      
  9.     PostOrderTraverse(T->rchild); //后序遍历右子树  
  10.     printf("%c",T->data);       // 显示结点数据，可以更改为其他的对结点操作  
  11. }  

二叉树遍历的性质：

已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。

已知后续遍历序列和中序遍历序列，可以唯一确定一棵二叉树。


但是，已知前序和后序遍历，是不能确定一棵二叉树的。


                                                                    2.4二叉树的建立

为了简历一棵树，为了让每个结点确认是否有左右孩子，我们对他进行了扩展，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一个特定值，如”#“。这种处理后的二叉树叫做原二叉树的扩展二叉树。扩展二叉树就可以做到一个遍历确定一棵二叉树，如下树的前序遍历为：AB#D##C##

数据结构中 树（重点kdtree）


[cpp]  view plain copy
  1. // 按前序输入二叉树中的结点值，#标识空树，构造二叉链表表示的二叉树  
  2.   
  3. void CreatBiTree(BiTree* T)  
  4. {  
  5.     TElemType ch;  
  6.     scanf("%c",&ch);  
  7.   
  8.     if(cd == '#')  
  9.         *T = NULL;  
  10.     else  
  11.     {  
  12.         *T = (BiTree)malloc(sizeof(BiTree));  
  13.         if(!*T)  
  14.         {  
  15.             exit(OVERFLOW);  
  16.         }  
  17.   
  18.         (*T)->data = ch; //生成根结点  
  19.         CreatBiTree(&(*T)->lchild); //构造左子树  
  20.         CreatBiTree(&(*T)->rchild); //构造右子树  
  21.     }  
  22.   
  23. }  

可看到构造子树时是用到了先序方式，也可以根据需要用中序或者后序方式构造。


                                                           （三）二叉排序树

二叉排序树（Binary Sort Tree）,又称为二叉查找树。他或者是一棵空树，或者是具有如下性质的二叉树。

  • 如它的左子树不为空，则左子树上的所有结点都小于他的根结构的值。
  • 如它的右子树不为空，则右子树上的所有结点都大于他的根结构的值。
  • 它的左右子树也分别为二叉排序树。

当我们对二叉排序树进行中序遍历的时候，我们就可以得到一个有序序列。


构造二叉排序树的目的，其实不是为了排序，而是为了提高查找和删除关键字的速度。


二叉排序树的查找操作

[cpp]  view plain copy
  1. // 二叉树二叉链表结点的结构定义  
  2. typedef struct BiTNode  
  3. {  
  4.     int data;  
  5.     struct BiTNode *lchild,*rchild;  
  6. }BiTnode, *BiTree;  
  7.   
  8. // 递归查找二叉排序树T中是否存在key  
  9. // 指针f指向T的双亲，其初始化为NULL  
  10. // 若查找成功，则指针p指向该节点，并返回TRUE  
  11. // 否则指针p指向查找路路径*问的最后一个结点并返回FLASE  
  12.   
  13. Status SearchBiTree(BiTree T, int key, BiTree f, BiTree *p)  
  14. {  
  15.     if(!T)              //查找不成功  
  16.     {  
  17.         *p = f;  
  18.         return FLASE:  
  19.     }  
  20.     else if( key == T->data)    //查找成功  
  21.     {  
  22.         *p =f;  
  23.         return TRUE;  
  24.     }  
  25.     else if(key < T->data)  
  26.         return SearchBiTree(T->lchild,key,T,p); //在左子树继续查找  
  27.     else  
  28.         reutrn SearchBiTree(T->rchild,key,T,p); //在右子树继续查找  
  29. }  
数据结构中 树（重点kdtree）

二叉排序树的插入操作

有了二叉排序树的查找函数，那么所谓二叉排序的插入，其实也就是将关键字放到树中的合适位置而已

[cpp]  view plain copy
  1. // 当二叉排序树T中不存在关键字等于key的数据元素时  
  2. // 插入key并返回TRUE,否则返回FALSE  
  3. Status InsertBiTree(BiTree *T,int key)  
  4. {  
  5.     BiTree p,s;  
  6.     if(!SearchBiTree(*T,key,NULL,&p))   //查找不成功  
  7.     {  
  8.         s = (BiTree)malloc(sizeof(BiTNode));  
  9.         s->data = key;  
  10.         s->lchild = s->rchild = NULL;  
  11.   
  12.         if(!p)  
  13.             *T = s;                     //插入s为新的根结点  
  14.         else if(key < p->data)  
  15.             p->lchild = s;              //插入s为左孩子  
  16.         else   
  17.             p->rchild = s;              //插入s为右孩子  
  18.   
  19.         return TRUE;  
  20.     }  
  21.     else  
  22.         return FALSE;  
  23. }  

二叉排序树的删除操作

删除结点的三种情况：

  • 叶子结点；
  • 仅有左或右子树的结点；
  • 左右子树都有结点。

[cpp]  view plain copy
  1. // 若二叉排序树T中存在关键字等于key的数据元素时，则删除该元素结点  
  2. // 并返回TRUE,否则返回FALSE  
  3.   
  4. Status DeleteBST(BiTree *T, int key)  
  5. {  
  6.     if(!*T)     //不存在关键字等于key的数据元素  
  7.         return FALSE;  
  8.     else  
  9.     {  
  10.         if( key == (*T)->data)                  // 找到关键字等于key的数据元素  
  11.             return Delete(T);  
  12.         else if(key < (*T)->data)  
  13.             return DeleteBST(&(*T)->lchild,key);  
  14.         else  
  15.             return DeleteBST(&(*T)->rchild,key)；  
  16.     }  
  17. }  
  18.   
  19. Status Delete(BiTree *p)  
  20. {  
  21.     BiTree q,s;     //q存待删结点，s存替换结点  
  22.   
  23.     if((*p)->rchild == NULL)            //右子树为空，重接左子树  
  24.     {  
  25.         q = *p; *p = (*p)->lchild; free(q);  
  26.     }  
  27.     else((*p)->lchild == NULL)          //左子树为空，重接右子树  
  28.     {  
  29.         q = *p; *p = (*p)->rchild; free(q);  
  30.     }  
  31.     else  
  32.     {  
  33.         q = *p;  
  34.         s = (*p)->lchild;  
  35.         while(s->rchild)        //转左，然后向右到尽头，找到待删结点前驱  
  36.         {  
  37.             q=s;//q删除结点的前驱  
  38.             s=s->rchild;//删除结点  
  39.         }  
  40.   
  41.         (*p)->data = s->data;   //s指向被删除结点的前驱  
  42.   
  43.         if(q != *p)  
  44.             q->rchild = s->lchild;  //重接q右子树  
  45.         else  
  46.             q->lchild = s->rchild;  //重接q左子树  
  47.         free(s);  
  48.     }  
  49.   
  50.     return TRUE;  
  51. }  

数据结构中 树（重点kdtree）


二叉排序树总结

二叉排序树是以链接方式存储，保持了连接存储结构在执行插入或删除操作时不用移动元素的有点，只要找到合适的插入和删除的位置后，仅仅修改指针即可。插入删除的时间性能比较好。

对于二叉排序树的查找，走的就是从根节点到要查找结点的路径，其比较次数等于给定值的结点在二叉树的层次。


                                                                  （四）Kd-树

Kd-树 其实是K-dimension tree的缩写，是对数据点在k维空间中划分的一种数据结构。其实，Kd-树是一种平衡二叉树。

关于平衡二叉树详见：http://www.cppblog.com/cxiaojia/archive/2012/08/20/187776.html

举一示例：

假设有六个二维数据点 = {（2,3），（5,4），（9,6），（4,7），（8,1），（7,2）}，数据点位于二维空间中。为了能有效的找到最近邻，Kd-树采用分而治之的思想，即将整个空间划分为几个小部分。六个二维数据点生成的Kd-树的图为：
数据结构中 树（重点kdtree）                 数据结构中 树（重点kdtree）

                2D 对应的kd的平面划分                                3D 对应的kd的平面划分

 

 

k-d树算法可以分为两大部分，一部分是有关k-d树本身这种数据结构建立的算法，另一部分是在建立的k-d树上如何进行最邻近查找的算法。

一 Kd-树的构建

Kd-树是一个二叉树，每个节点表示的是一个空间范围。下表表示的是Kd-树中每个节点中主要包含的数据结构。

Range域表示的是节点包含的空间范围。

Node-data域就是数据集中的某一个n维数据点。分割超面是通过数据点Node-Data并垂直于轴split的平面，分割超面将整个空间分割成两个子空间。

令split域的值为i，如果空间Range中某个数据点的第i维数据小于Node-Data[i]，那么，它就属于该节点空间的左子空间，否则就属于右子空间。

Left，Right域分别表示由左子空间和右子空间空的数据点构成的Kd-树。

                             表1 k-d树中每个节点的数据类型
域名
数据类型
描述
Node-data
数据矢量
数据集中某个数据点，是n维矢量（这里也就是k维）
Range
空间矢量
该节点所代表的空间范围
split
整数
垂直于分割超平面的方向轴序号
Left
k-d树
由位于该节点分割超平面左子空间内所有数据点所构成的k-d树
Right
k-d树
由位于该节点分割超平面右子空间内所有数据点所构成的k-d树
parent
k-d树
父节点
从上面对k-d树节点的数据类型的描述可以看出构建k-d树是一个逐级展开的递归过程。下面是给出的是构建k-d树的伪码。

 

构建k-d树的算法实现
算法：构建k-d树（createKDTree）

输入：数据点集Data-set和其所在的空间Range 
输出：Kd，类型为k-d tree 
1、If Data-set为空，则返回空的k-d tree 
2、调用节点生成程序：
（1）确定split域：对于所有描述子数据（特征矢量），统计它们在每个维上的数据方差。以SURF特征为例，描述子为64维，可计算64个方差。挑选出最大值，对应的维就是split域的值。数据方差大表明沿该坐标轴方向上的数据分散得比较开，在这个方向上进行数据分割有较好的分辨率；
（2）确定Node-data域：数据点集Data-set按其第split域的值排序。位于正中间的那个数据点被选为Node-data。此时新的Data-set' = Data-set\Node-data（除去其中Node-data这一点）。 
3、dataleft = {d属于Data-set' && d[split] ≤ Node-data[split]}
Left_Range = {Range && dataleft} dataright = {d属于Data-set' && d[split] > Node-data[split]}
Right_Range = {Range && dataright} 
4.、eft = 由（dataleft，Left_Range）建立的k-d tree，即递归调用createKDTree（dataleft，Left_
Range）。并设置left的parent域为Kd；
right = 由（dataright，Right_Range）建立的k-d tree，即调用createKDTree（dataright，Right_
Range）。并设置right的parent域为Kd。

构建k-d树算法举例

从上述举的实例来看，过程如下：
（1）确定：split 域=x，6个数据点在x,y 维度上的数据方差为39,28.63.在x轴方向上的方差大，所以split域值为x。

（2）确定：Node-Data=（7,2），根据x维上的值将数据排序，6个数据的中值为7，所以node-data域为数据点（7,2）。这样该节点的分割超面就是通过（7,2）并垂直于：split=x轴的直线x=7.

  (3)   确定：左子空间和右子空间，分割超面x=7将整个空间分为两部分。x<=7 为左子空间，包含节点（2,3），（5,4），（4，7），另一部分为右子空间。包含节点（9,6），（8,1）

这个构建过程是一个递归过程。重复上述过程，直至只包含一个节点。

 

如算法所述，k-d树的构建是一个递归的过程。然后对左子空间和右子空间内的数据重复根节点的过程就可以得到下一级子节点（5,4）和（9,6）（也就是左右子空间的'根'节点），同时将空间和数据集进一步细分。如此反复直到空间中只包含一个数据点，如图1所示。最后生成的k-d树如图2所示。

数据结构中 树（重点kdtree）数据结构中 树（重点kdtree）

                             图1                                                                                                图2

 

二、构建完kd树之后，如今进行最近邻搜索呢？

KD树的查找算法：

在k-d树中进行数据的查找也是特征匹配的重要环节，其目的是检索在k-d树中与查询点距离最近的数据点。

这里先以一个简单的实例来描述最邻近查找的基本思路。

例一：查询的点（2.1,3.1）（较简单）。

1、如图3所示，星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。

2、而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。

3、为了找到真正的最近邻，还需要进行'回溯'操作：

             算法沿搜索路径反向查找是否有距离查询点更近的数据点。

此例中先从（7,2）点开始进行二叉查找，然后到达（5,4），最后到达（2,3），此时搜索路径中的节点为<（7,2），（5,4），（2,3）>，

首先以（2,3）作为当前最近邻点，计算其到查询点（2.1,3.1）的距离为0.1414，

然后回溯到其父节点（5,4），并判断在该父节点的其他子节点空间中是否有距离查询点更近的数据点。以（2.1,3.1）为圆心，以0.1414为半径画圆，如图3所示。发现该圆并不和超平面y = 4交割，因此不用进入（5,4）节点右子空间中去搜索。

4、最后，再回溯到（7,2），以（2.1,3.1）为圆心，以0.1414为半径的圆更不会与x = 7超平面交割，因此不用进入（7,2）右子空间进行查找。至此，搜索路径中的节点已经全部回溯完，结束整个搜索，返回最近邻点（2,3），最近距离为0.1414。

数据结构中 树（重点kdtree）数据结构中 树（重点kdtree）

                                      图3

例二：查找点为（2，4.5）（叫复杂一点）。

一个复杂点了例子如查找点为（2，4.5）。

1、同样先进行二叉查找，先从（7,2）查找到（5,4）节点，在进行查找时是由y = 4为分割超平面的，由于查找点为y值为4.5，因此进入右子空间查找到（4,7），形成搜索路径<（7,2），（5,4），（4,7）>，

2、取（4,7）为当前最近邻点，计算其与目标查找点的距离为3.202。然后回溯到（5,4），计算其与查找点之间的距离为3.041。

       （（4,7）与目标查找点的距离为3.202，而（5,4）与查找点之间的距离为3.041，所以（5,4）为查询点的最近点；）

3、以（2，4.5）为圆心，以3.041为半径作圆，如图4所示。可见该圆和y = 4超平面交割，所以需要进入（5,4）左子空间进行查找。此时需将（2,3）节点加入搜索路径中得<（7,2），（2,3）>。

4、回溯至（2,3）叶子节点，（2,3）距离（2,4.5）比（5,4）要近，所以最近邻点更新为（2，3），最近距离更新为1.5。

5、回溯至（7,2），以（2,4.5）为圆心1.5为半径作圆，并不和x = 7分割超平面交割，如图5所示。

至此，搜索路径回溯完。返回最近邻点（2,3），最近距离1.5。

数据结构中 树（重点kdtree）数据结构中 树（重点kdtree）

                   图4                                                                         图5

 

k-d树查询算法的简要说明：

 

  • 从root节点开始，DFS搜索直到叶子节点，同时在stack中顺序存储已经访问的节点。
  • 如果搜索到叶子节点，当前的叶子节点被设为最近邻节点。
  • 然后通过stack回溯:
    如果当前点的距离比最近邻点距离近，更新最近邻节点.
    然后检查以最近距离为半径的圆是否和父节点的超平面相交.
    如果相交，则必须到父节点的另外一侧，用同样的DFS搜索法，开始检查最近邻节点。
    如果不相交，则继续往上回溯，而父节点的另一侧子节点都被淘汰，不再考虑的范围中.
  • 当搜索回到root节点时，搜索完成，得到最近邻节点。

     

    当然设计到KD树的操作还有插入和删除等，但是k近邻算法主要就是用来查找元素。
    • 标签：

    相关文章