[發(fā)明專利]二叉樹并行查找方法和設(shè)備

有效

• 申請?zhí)枺?/td>: 201110136760.1
• 申請日: 2011-05-25
• 公開（公告）號: CN102156759A
• 公開（公告）日: 2011-08-17
• 發(fā)明（設(shè)計）人: 商紅章
• 申請（專利權(quán)）人: 華為技術(shù)有限公司
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京龍雙利達知識產(chǎn)權(quán)代理有限公司 11329
• 代理人: 毛威;張亮

技術(shù)領(lǐng)域

本發(fā)明實施例涉及通信領(lǐng)域，具體涉及二叉樹并行查找方法和設(shè)備。

背景技術(shù)

二叉樹被廣泛使用于各種查找結(jié)構(gòu)中，其結(jié)構(gòu)簡單，查找性能只與樹的高度相關(guān)。基于傳統(tǒng)的二叉樹不能有效提高二叉樹的查找性能。現(xiàn)有技術(shù)在進行二叉樹查找時，必須通過逐層節(jié)點比較的方式來完成最終查找。由于需要逐層進行節(jié)點比較，因此對于一個高度為H的二叉樹來說，需要對內(nèi)存進行H次訪問。使用現(xiàn)有的查找技術(shù)，無法再在查找性能上有所突破。

發(fā)明內(nèi)容

本發(fā)明實施例一方面要解決的技術(shù)問題是減少內(nèi)存訪問次數(shù)，并提高二叉樹查找效率。

本發(fā)明實施例提出了一種二叉樹并行查找方法，包括：以選定的子樹階數(shù)將二叉樹分成多個子樹；為每個子樹構(gòu)造共同關(guān)鍵字，包括：從每個子樹的每個節(jié)點數(shù)據(jù)的最高位起，提取子樹中全部節(jié)點數(shù)據(jù)的相同的高位數(shù)據(jù)，作為該子樹的子樹共同關(guān)鍵字；據(jù)根據(jù)子樹的共同關(guān)鍵字的位數(shù)，從待查關(guān)鍵字構(gòu)造待查高位關(guān)鍵字，包括：按照共同關(guān)鍵字的位數(shù)，從最高位起，提取待查關(guān)鍵字的高位數(shù)據(jù)，作為待查高位關(guān)鍵字；比較待查高位關(guān)鍵字與子樹共同關(guān)鍵字，在待查高位關(guān)鍵字與子樹共同關(guān)鍵字的比較結(jié)果不相等時，根據(jù)比較結(jié)果確定下一次查找的子樹方向。

一種用于二叉樹并行查找的設(shè)備，設(shè)備包括：壓縮模塊，用于以選定的子樹階數(shù)將二叉樹分成多個子樹；并行查找關(guān)鍵字構(gòu)造模塊，用于為每個子樹構(gòu)造共同關(guān)鍵字，包括：從每個子樹的每個節(jié)點數(shù)據(jù)的最高位起，提取子樹中全部節(jié)點數(shù)據(jù)的相同的高位數(shù)據(jù)，作為該子樹的子樹共同關(guān)鍵字，并行查找關(guān)鍵字構(gòu)造模塊用于據(jù)根據(jù)子樹的共同關(guān)鍵字的位數(shù)，從待查數(shù)構(gòu)造待查高位關(guān)鍵字，包括：按照共同關(guān)鍵字的位數(shù)，從最高位起，提取待查關(guān)鍵字的高位數(shù)據(jù)，作為待查高位關(guān)鍵字；比較模塊，用于比較待查高位關(guān)鍵字與子樹共同關(guān)鍵字，控制模塊，用于在待查高位關(guān)鍵字與子樹共同關(guān)鍵字的比較結(jié)果不相等時，根據(jù)比較結(jié)果確定下一次查找的子樹方向。

根據(jù)本發(fā)明實施例，將二叉樹壓縮為低階數(shù)的子樹，提取每個子樹的共同關(guān)鍵字并為每個子樹構(gòu)造并行查找關(guān)鍵字，可以大大減少對數(shù)據(jù)存儲區(qū)的訪問次數(shù)，從而提高查找效率。

附圖說明

為了更清楚地說明本發(fā)明實施例的技術(shù)方案，下面將對實施例或現(xiàn)有技術(shù)描述中所需要使用的附圖作簡單地介紹，顯而易見地，下面描述中的附圖僅僅是本發(fā)明的一些實施例，對于本領(lǐng)域普通技術(shù)人員來講，在不付出創(chuàng)造性勞動性的前提下，還可以根據(jù)這些附圖獲得其他的附圖。在附圖中：

圖1是本發(fā)明實施例方法的流程圖；

圖2是本發(fā)明實施例所使用的二叉樹的結(jié)構(gòu)圖；

圖3是本發(fā)明實施例的設(shè)備的結(jié)構(gòu)圖。

具體實施方式

下面將結(jié)合本發(fā)明實施例中的附圖，對本發(fā)明實施例中的技術(shù)方案進行清楚、完整地描述，顯然，所描述的實施例是本發(fā)明一部分實施例，而不是全部的實施例。基于本發(fā)明中的實施例，本領(lǐng)域普通技術(shù)人員在沒有作出創(chuàng)造性勞動前提下所獲得的所有其他實施例，都屬于本發(fā)明保護的范圍。

本發(fā)明實施例的構(gòu)思在于，在二叉樹中進行節(jié)點比較時，首先將二叉樹劃分成低階子樹(例如，3階子樹)，將每個子樹的節(jié)點數(shù)據(jù)的高位數(shù)據(jù)提取出來，將所述高位數(shù)據(jù)與待查數(shù)據(jù)高位數(shù)據(jù)比較，如果待查關(guān)鍵字的高位數(shù)據(jù)與子樹的共同關(guān)鍵字不相等，則根據(jù)高位數(shù)據(jù)的比較結(jié)果直接確定下一次比較所選取的低階子樹。在待查關(guān)鍵字的高位數(shù)據(jù)大于子樹的共同關(guān)鍵字時，說明待查關(guān)鍵字大于當(dāng)前子樹的全部節(jié)點數(shù)據(jù)，則下一次查找選取的子樹為下一層低階子樹中最大的子樹。在待查關(guān)鍵字的高位數(shù)據(jù)小于子樹的共同關(guān)鍵字時，說明待查關(guān)鍵字小于當(dāng)前子樹的全部節(jié)點數(shù)據(jù)，則下一次查找選取的子樹為下一層低階子樹中最小的子樹。利用這種方式，可以快速過濾掉待查關(guān)鍵字的高位數(shù)據(jù)與子樹節(jié)點數(shù)據(jù)的高位數(shù)據(jù)不同的子樹，而免于比較低位數(shù)據(jù)，加快了查找速度，提高了查找效率。在待查關(guān)鍵字的高位數(shù)據(jù)等于節(jié)點數(shù)據(jù)的高位數(shù)據(jù)時，利用子樹節(jié)點數(shù)據(jù)的一定位數(shù)的低位數(shù)據(jù)構(gòu)造并行查找關(guān)鍵字，通過一次性比較，來確定下一次查找所選取的子樹。這樣可以減少比較步驟，加快查找速度。本發(fā)明實施例的具體示例將在以下參照附圖進行詳細描述。

圖1是本發(fā)明實施例的二叉樹查找方法的流程圖。該方法包括：

110：以選定的子樹階數(shù)將所述二叉樹分成多個子樹；

120：為每個子樹構(gòu)造共同關(guān)鍵字，包括：從每個子樹的每個節(jié)點數(shù)據(jù)的最高位起，提取所述子樹中全部節(jié)點數(shù)據(jù)的相同的高位數(shù)據(jù)，作為該子樹的子樹共同關(guān)鍵字；