(3.231.29.122) 您好!臺灣時間:2021/02/25 21:25
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:李景立
研究生(外文):LI,JING-LI
論文名稱:AVL樹之同作搜尋,插入與刪除
論文名稱(外文):AVL 樹之同作搜尋,插入與刪除
指導教授:黃宗傳
指導教授(外文):HUANG,ZONG-CHUAN
學位類別:碩士
校院名稱:國立中山大學
系所名稱:電機工程研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:1991
畢業學年度:78
語文別:中文
論文頁數:18
中文關鍵詞:同作搜尋
外文關鍵詞:AVL 樹SYMBOL-TABLESDIRECTORIESDATA-BASESINTERNAL-PATH-LENGTHBINARY-SEARCH-TREESCONCURRENCY
相關次數:
  • 被引用被引用:0
  • 點閱點閱:81
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
對於有順序性關係資料組纖而言,高度平衡的二元搜尋樹(hight balanced binary s
earch tree;即AVL樹)是一種非常重要的結構。它們經常地使用在符號表(symbol ta
bles)、目錄(directories)及資料庫(data bases)等方面。
AVL樹主要的特性如下:
1.每個節點的左、右子樹高度之差至多為1,使得整棵樹的高度不超過1.44 logzn(n
是樹的節點數)。
2.局部再平衡法做搜尋、搜入與刪除這運算所需時間為O(logzn)。
3.結構簡單實作容易。
雖然有其它類型的平衡搜尋樹和整體平衡的方法可以減少樹的內部路徑長度(interna
l path length),但為了重建樹的平衡,在最差情況下,卻必須付出O(n)的時間。
這篇論文主要討論動態“二元搜樹 (binary seanch trees)”同作存取的問題。其目
的在增加讀者(reader)與寫者(writer)間的同作率(concurrency)。有二個在AVL樹中
同作搜尋,插入與刪除的方法在這篇論文中討論,第二個方法在同作率與效率上都較
第一個方法為佳,但需要較多的記憶體。
在嘗試平行化的過程中,不可避免的會增加一些額外的負擔(overhead)。對單一處理
器的電腦,可以使用時脈中斷的方法達到同作處理的目的。我們在個人電腦上模擬這
些演算法,以評估它的同作率及平行處理時所產生的額外負擔,並在這兩個方法之間
作個比較。

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔