k分查找算法用k叉树

A. 求k分查找算法的时间复杂度，辅导书上的答案是数的高度，但总觉得不

我感觉最坏比较次数应该是(k-1)logk(n),在树的每一节点上最坏情况要比较k-1次（k叉排序树每个节点有k-1个关键字），然后树高是logk(n)。然后n很大时忽略系数就是logk(n)我这么说也不知道对不对，恳求高手指点

B. java中的查找算法如何实现... 高手帮帮忙

这个。。。我随便乱说几句啊，说的不对别见笑。

有一个数组 当中存有一些字符串
另外有一个字典文件 我也将它导入一个数组 有50000多个单词
然后要找出字符串中包含的单词

由你给的条件可知：
1。数组 应该是从前到后依次顺序扫描字符串。
2。50000多个单词的字典文件一定优化。具体优化要看具体内容吧。
比如你可以按单词的首字母排序，然后分组。等扫描字符串的时候可以分组比较。但这种方法应该没省多少时间。
你还可以把50000多个单词的字典文件按单词的长度进行分组。比如1个字母的分成一组，二个字母的分成一组。。。。N个字母的分成一组，这样就分成了N组。然后扫描字符串的时候你可以按后续匹配（好象叫这个算法吧，名字记不清了）算法，这样就可以省很多时间了。
你还可以这样做，因为你要查的是单词，单词一定有意义。那你可以直接把你的字符串数组先进行语法、语义分析并分割，然后再去匹配你的字典。这样应该是最快的。但这要用到自然语言处理。。。

C. 数据结构 什么叫满K叉树

K叉树是指每个父节点最多有K个子节点的树。满K叉树就是除了底层节点以外的每个节点都有K个子节点的树。

D. 计算K叉树的叶子节点数

K叉数的性质
树T中结点总数n(n≥0)等于树中各结点得出度之和加1。
所以节点总数n=4*1+2*2+1*3+1*4+1=16
因为叶子节点出度为0所以
叶子节点个数等于16-4-2-1-1=8个

E. 一棵含有N个结点的K叉树，可能达到的最大深度和最小深度分别是多少

一棵含有N个结点的K叉树，可能达到的最大深度为n，最小为n-1除以k取整。

二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。

深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时，称为完全二叉树。

(5)k分查找算法用k叉树扩展阅读：

由m（m≥0）棵互不相交的树构成一片森林。如果把一棵非空的树的根结点删除，则该树就变成了一片森林，森林中的树由原来根结点的各棵子树构成。

F. 数据结构问题2

数据结构我倒是学得很好,本来也很想回答你这问题,但你的问题太长太大了,哪有时间回答?算了,这五分我不要了.
按字母顺序把树画出来就行了呗，很明显只有a只出现在左边（双亲）位置，所以a是根结点，只在右边出现的是叶子结点，两边都有的是普通结点
剩按字母顺序把树画出来就行了呗，很明显只有a只出现在左边（双亲）位置，所以a是根结点，只在右边出现的是叶子结点，两边都有的是普通结点
剩下的自己做吧
下的自己做吧

G. 数据结构（java）：二叉排序树上查找键值为K的算法函数

结点结构
左指针、右指针
数据域

typedef struct Node{
DataType data; //数据域
Node *right,*left; //结点的左右子树指针
}BTNode;

//函数体BTNode *FindBTree(BTNode* root, DataType item)
{
if(root==NULL) return NULL;
if(root->data==item) return root;
BTNode *p=FindBTree( root->left, item);
if(p!=NULL) return p;
else
return FindBTree( root->right, item);
}

H. 数据结构 简单算法实现在二叉排序树上查找关键值k

如果用C语言，应该要写成这样:
typedef
struct
node{int
key;
struct
node
*lchild;
struct
node
*rchild;}bitree;
bitree
*bstsearch(bitree
*t,
int
k)
{
if
(t==NULL
)
//这里t是一个指针，是不能跟0判等的，要和空指针判等
{
return(NULL);//如果t是空指针，表示数是空数，不存在关键值key
}
else
{
while
(t!=NULL)//要循环遍历整个树，寻找关键值key
{
if
(t->key==k)
//如果找到了关键值key，则返回节点指针t
return(t);
else
if
(t->key>k)
//因为是排序树，则有对于任意节点，左孩子小于根小于右孩子
t=t->lchild;
//所以如果当前节点的key大于输入值，则搜索左子树，否则右子树
else
t=t->rchild_;
}
return
NULL;//这里要加这个，如果搜索不到的话要返回空指针
}
}

I. KNN算法-4-算法优化-KD树

KNN算法的重要步骤是对所有的实例点进行快速k近邻搜索。如果采用线性扫描（linear scan），要计算输入点与每一个点的距离，时间复杂度非常高。因此在查询操作时，可以使用kd树对查询操作进行优化。

Kd-树是K-dimension tree的缩写，是对数据点在k维空间（如二维(x，y)，三维(x，y，z)，k维(x1，y，z..)）中划分的一种数据结构，主要应用于多维空间关键数据的搜索（如：范围搜索和最近邻搜索）。本质上说，Kd-树就是一种平衡二叉树。

k-d tree是每个节点均为k维样本点的二叉树，其上的每个样本点代表一个超平面，该超平面垂直于当前划分维度的坐标轴，并在该维度上将空间划分为两部分，一部分在其左子树，另一部分在其右子树。即若当前节点的划分维度为d，其左子树上所有点在d维的坐标值均小于当前值，右子树上所有点在d维的坐标值均大于等于当前值，本定义对其任意子节点均成立。

必须搞清楚的是，k-d树是一种空间划分树，说白了，就是把整个空间划分为特定的几个部分，然后在特定空间的部分内进行相关搜索操作。想象一个三维(多维有点为难你的想象力了)空间，kd树按照一定的划分规则把这个三维空间划分了多个空间，如下图所示：

首先，边框为红色的竖直平面将整个空间划分为两部分，此两部分又分别被边框为绿色的水平平面划分为上下两部分。最后此4个子空间又分别被边框为蓝色的竖直平面分割为两部分，变为8个子空间，此8个子空间即为叶子节点。

常规的k-d tree的构建过程为：

对于构建过程，有两个优化点：

例子：采用常规的构建方式，以二维平面点(x,y)的集合(2,3)，(5,4)，(9,6)，(4,7)，(8,1)，(7,2) 为例结合下图来说明k-d tree的构建过程：

如上算法所述，kd树的构建是一个递归过程，我们对左子空间和右子空间内的数据重复根节点的过程就可以得到一级子节点（5,4）和（9,6），同时将空间和数据集进一步细分，如此往复直到空间中只包含一个数据点。

如之前所述，kd树中，kd代表k-dimension，每个节点即为一个k维的点。每个非叶节点可以想象为一个分割超平面，用垂直于坐标轴的超平面将空间分为两个部分，这样递归的从根节点不停的划分，直到没有实例为止。经典的构造k-d tree的规则如下：

kd树的检索是KNN算法至关重要的一步，给定点p，查询数据集中与其距离最近点的过程即为最近邻搜索。

如在构建好的k-d tree上搜索(3,5)的最近邻时，对二维空间的最近邻搜索过程作分析。

首先从根节点(7,2)出发，将当前最近邻设为(7,2)，对该k-d tree作深度优先遍历。

以(3,5)为圆心，其到(7,2)的距离为半径画圆（多维空间为超球面），可以看出(8,1)右侧的区域与该圆不相交，所以(8,1)的右子树全部忽略。

接着走到(7,2)左子树根节点(5,4)，与原最近邻对比距离后，更新当前最近邻为(5,4)。

以(3,5)为圆心，其到(5,4)的距离为半径画圆，发现(7,2)右侧的区域与该圆不相交，忽略该侧所有节点，这样(7,2)的整个右子树被标记为已忽略。

遍历完(5,4)的左右叶子节点，发现与当前最优距离相等，不更新最近邻。所以(3,5)的最近邻为(5,4)。

举例：查询点（2.1,3.1）

星号表示要查询的点（2.1,3.1）。通过二叉搜索，顺着搜索路径很快就能找到最邻近的近似点，也就是叶子节点（2,3）。而找到的叶子节点并不一定就是最邻近的，最邻近肯定距离查询点更近，应该位于以查询点为圆心且通过叶子节点的圆域内。为了找到真正的最近邻，还需要进行相关的‘回溯'操作。也就是说，算法首先沿搜索路径反向查找是否有距离查询点更近的数据点。

举例：查询点（2，4.5）

一个复杂点了例子如查找点为（2，4.5），具体步骤依次如下：

上述两次实例表明，当查询点的邻域与分割超平面两侧空间交割时，需要查找另一侧子空间，导致检索过程复杂，效率下降。

一般来讲，最临近搜索只需要检测几个叶子结点即可，如下图所示：

但是，如果当实例点的分布比较糟糕时，几乎要遍历所有的结点，如下所示：

研究表明N个节点的K维k-d树搜索过程时间复杂度为： 。

同时，以上为了介绍方便，讨论的是二维或三维情形。但在实际的应用中，如SIFT特征矢量128维，SURF特征矢量64维，维度都比较大，直接利用k-d树快速检索（维数不超过20）的性能急剧下降，几乎接近贪婪线性扫描。假设数据集的维数为D，一般来说要求数据的规模N满足N»2D，才能达到高效的搜索。

Sklearn中有KDTree的实现，仅构建了一个二维空间的k-d tree，然后对其作k近邻搜索及指定半径的范围搜索。多维空间的检索，调用方式与此例相差无多。