大二上數(shù)算實(shí)習(xí)空間

數(shù)據(jù)結(jié)構(gòu)與算法實(shí)數(shù)據(jù)結(jié)構(gòu)與算法實(shí)海杰，《數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)教（國家十一五規(guī)劃教材），高教社2011年1北京大學(xué)信息科學(xué)技術(shù)學(xué)——空間數(shù)據(jù)結(jié)張銘張路詢詢經(jīng)度、緯經(jīng)營類數(shù)據(jù)：N數(shù)據(jù)：N維空間中的一個點(diǎn)區(qū)域：矩形(2維)，立方體(3維)目標(biāo)點(diǎn)：查找操作中要查找的數(shù)PRK-DPRK-DR 定義：點(diǎn)-區(qū)域四分樹（Point-RegionQuadtree）：每個內(nèi)部結(jié)點(diǎn)都恰好有四個子結(jié)將當(dāng)前空間均等地劃分為四個區(qū) ，點(diǎn)A、B頂層空間平分為4份(包含多個數(shù)據(jù)點(diǎn))進(jìn)一步分0ABCD，點(diǎn)A、B頂層空間平分為4份(包含多個數(shù)據(jù)點(diǎn))進(jìn)一步分0ABCDGEFEAFCDBG 128128，并且其中包含點(diǎn)A、B、C、D、 檢 檢索的過程與劃分過程類例如，檢索數(shù)據(jù)點(diǎn)D，其坐標(biāo)為（40，85）127)）96）、（32-64，64-96）、（0-32，96-127）和（32-64，96-127），D應(yīng)該位于下一個NE子樹中首先通首先通過檢索確定其位如果葉結(jié)點(diǎn)已經(jīng)包含另一條記錄 首先檢索到P所在的結(jié)點(diǎn)將結(jié)點(diǎn)N所包含的記錄改為把這四個結(jié)點(diǎn)的子樹合并為一個結(jié)點(diǎn)N’，代替它們的父結(jié)在上一層也可能需要相似的合直到到達(dá)某一層，該層至少有兩個記錄分別包含在結(jié)點(diǎn)N’以N’的某個兄弟結(jié)點(diǎn)子樹中，合并結(jié)刪除結(jié)點(diǎn)合并空0再合刪除結(jié)點(diǎn)合并空0再合DACB 根結(jié)點(diǎn)為如果根結(jié)點(diǎn)是包含一個數(shù)據(jù)記錄的葉結(jié) 如果根結(jié)點(diǎn)是一個內(nèi)部結(jié)如果不包含任何的記則直接返回如果包含一個數(shù)據(jù)記 頂層頂層結(jié)點(diǎn)按一個維劃第二層結(jié)點(diǎn)按照另一維進(jìn)行劃以此類推，在各個維之間反復(fù)進(jìn)行劃， 時(shí)間復(fù)雜度 XYXXYXXYX y:x:y:xy y:x:y:xy0DBAGFCE 把當(dāng)前的空間劃分為兩交替地對兩個維進(jìn)行劃其子結(jié)點(diǎn)進(jìn)一步把空間劃分成更小的部子結(jié)點(diǎn)的劃分線不會穿過根結(jié)點(diǎn)的劃分這些矩形是結(jié)點(diǎn)可能落到的各子樹范識別器(discriminator 在每識別器(discriminator 在每一層用來進(jìn)行決策的關(guān)鍵碼稱為識別(discriminator對于k維關(guān)鍵碼，標(biāo)號分別為imod在第I層把識別器的標(biāo)號定義例如，對一個三維的關(guān)鍵碼做檢索，3個關(guān)碼（x，y，z）標(biāo)號分別為0、1、zmod3=0mod3=1mod3=2若關(guān)鍵若關(guān)鍵碼小于識別器的值就放入左子否則放到右子 求中位數(shù)T(1)=T(n)=總時(shí)間 交 交替地用識別器與各個維進(jìn)行比不斷地劃分區(qū)間縮小范圍，直到找到需要 檢索xyD(20,80) 檢索xyD(20,80)檢索成如果最后到達(dá)的結(jié)點(diǎn)指針是則檢索結(jié)束，該結(jié)點(diǎn)不存*{//rt:*{//rt:if(rt==NULL)returnNULL;elseif(val==rt->val)returnrt;else{intk=levmod//rt就是搜索的結(jié)returnKdFind(rt->leftvallev+1,dimension小，在左子樹returnKdFind(rt->rightvallev+1,dimension);//}} 如果刪除了一個有子結(jié)點(diǎn)的結(jié) 該結(jié)點(diǎn)最好能夠保持原來的空間劃F代替結(jié)點(diǎn)選最好的選擇F代替結(jié)點(diǎn)選最好的選擇是左子樹中當(dāng)前I(65,70)中值最大的一個結(jié)刪除結(jié)點(diǎn)F代替I代替結(jié)點(diǎn)選F代替I代替結(jié)點(diǎn)選刪除結(jié)點(diǎn)I代替結(jié)點(diǎn)選I代替結(jié)點(diǎn)選 (x (x(y1212根結(jié)點(diǎn)根結(jié)點(diǎn)A（50，55）滿足要進(jìn)入左子樹，點(diǎn)B（30，50）不在范進(jìn)入其右子樹發(fā)現(xiàn)結(jié)點(diǎn)D（20，80）也不符合類似地，進(jìn)入根結(jié)點(diǎn)的右子樹進(jìn)行搜給定k給定k維空間上的點(diǎn)x，查數(shù)據(jù)集中離x最近的查詢點(diǎn)(2,4.5)，搜索查詢點(diǎn)(2,4.5)，搜索路徑<(7,2),(5,4),(4,7)>，似最近點(diǎn)為(5,4)?；厮輹r(shí)發(fā)現(xiàn)跨過了=4，那需要進(jìn)入(5,4)的左子樹進(jìn)行查找。找到 find(NodeA,pointx){//x給定點(diǎn),A是kd樹的某個結(jié)點(diǎn)dist=Distance(x,A.x);//A.x是數(shù)據(jù)集中的某個點(diǎn)update(ansdistA.x);//ans是最終答案，更新ans的值if(compare(A,x)==Left)//compare只比較當(dāng)前維度判斷以x為圓心ans為半徑的圓是否穿越A.x所在半平ifcross(circle(x,ans),x);//查找另外一棵子} 是否跨過半平面取決于當(dāng)前近似最近 基于在kd樹查 1.將(7,2)加入優(yōu)先隊(duì)2(7,2(2,4.52(4,7){(2,3),(9,6)}3.從優(yōu)先隊(duì)列中取出 這個思想能不能用到BBF算法的查詢中 sift是圖片匹配算 K-NearestNeighboralgorithm，機(jī)器學(xué)習(xí) 其結(jié)構(gòu) 其結(jié)構(gòu)與輸入數(shù)據(jù)的順序也是有關(guān)Bentley和Friedman發(fā)明了k-d樹 采用了B樹分割空間的思 YX左邊圖的矩形和右邊的編號對應(yīng)，而點(diǎn)則表示數(shù)據(jù)對象；右邊是構(gòu)建好的一棵R樹，根結(jié)點(diǎn)包含兩個（指針，矩形）的實(shí)體，葉結(jié)點(diǎn)包含指向數(shù)據(jù)的指針和矩形編號 YX左邊圖的矩形和右邊的編號對應(yīng)，而點(diǎn)則表示數(shù)據(jù)對象；右邊是構(gòu)建好的一棵R樹，根結(jié)點(diǎn)包含兩個（指針，矩形）的實(shí)體，葉結(jié)點(diǎn)包含指向數(shù)據(jù)的指針和矩形編號I所代表的就是圖中的矩形，其范圍是圖示圖示 1.除根結(jié)點(diǎn)之外，所有葉子結(jié)點(diǎn)包含有m至M個記錄索引（條目）。3.每一個非葉子結(jié)點(diǎn)擁有m至M個孩子結(jié)點(diǎn)，除非它是根結(jié)點(diǎn)5.所有葉子結(jié)點(diǎn)都位于同一層，因此R樹為平衡樹 輸 輸入的是一個搜索矩它返回的結(jié)果是所有符合查找信息的記錄條描述：假設(shè)T為一棵R樹的根結(jié)點(diǎn)，查找所有搜索矩S覆蓋的記錄條目S2:[查找葉子結(jié)點(diǎn)]如果T是葉子結(jié)點(diǎn)，如果T所對應(yīng) R樹的R樹的主要問題就是矩形重疊覆YXYX影響R影響R樹性能的因R樹的插R樹的插入操作同B樹的插入操作類顯然，葉子結(jié)點(diǎn)的插入操作會比搜索操作 描述：將 描述：將新的記錄條目E插入給定的R樹中I3：[將變換向上傳遞]開始對結(jié)點(diǎn)L進(jìn)行AdjustTree操作，如I4：[對樹進(jìn)行增高操作]如果結(jié)點(diǎn)分裂，且該分裂向上傳播導(dǎo)致了根結(jié)點(diǎn)的分裂，那么需要創(chuàng)建一個新的根結(jié)點(diǎn)，并 描述： 描述：選擇葉子結(jié)點(diǎn)以放置新條目ECL1：[Initialize]設(shè)置N為根結(jié)點(diǎn)CL3：[選擇子樹]如果N不是葉子結(jié)點(diǎn)，則遍歷N中的AT1：[初始化AT1：[初始化將N設(shè)為LAT2：[檢驗(yàn)是否完成]如果N為根結(jié)點(diǎn)，則停止操作。插入（例插入（例插入（例插入（例插入（例插入（例插入（例插入（例R樹的刪R樹的刪除操作與B樹的刪除操作會有所不同，不過 描述：將一條記錄E從指定的R樹中刪除D1：[找到含有記錄的葉子結(jié)點(diǎn)]使用FindLeaf方法找D2：[刪除記錄]將E從L中刪除D3：[傳遞記錄]對L使用CondenseTree操D4：[縮減樹]當(dāng)經(jīng)過以上調(diào)整后，如果根結(jié)點(diǎn)只包 描述：根結(jié)點(diǎn)為T，期望找到包含有記錄E的葉子結(jié)點(diǎn)FL1：[搜索子樹]如果T不是葉子結(jié)點(diǎn)，則檢查每一條