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近鄰搜索及指定半徑的范圍搜索。多維空間的檢索，調用方式與此例相差無多。