计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2007年
5期
45-48
,共4页
HB(κ)树%结点%删除%旋转
HB(κ)樹%結點%刪除%鏇轉
HB(κ)수%결점%산제%선전
Foster的删除HB(κ)树的结点的算法的主要思想是先删除结点再自下而上处理某些子树,涉及自下而上的后退.提出一种新的删除HB(κ)树的结点的算法,其主要思想是先自上而下处理某些子树再删除结点,不涉及自下而上的后退.举例说明新算法的执行过程.证明新算法是正确的.与Foster的删除HB(κ)树的结点的算法相比,新算法不涉及辅助栈的使用.设n是HB(κ)树的结点的个数.新算法的时间复杂性是0(log2n),与Foster的删除HB(κ)树的结点的算法的相同.实验结果表明新算法的平均执行对间比Foster的删除HB(κ)树的结点的算法短.新算法的空间复杂性是O(1),比Foster的删除HB(κ)树的结点的算法低.
Foster的刪除HB(κ)樹的結點的算法的主要思想是先刪除結點再自下而上處理某些子樹,涉及自下而上的後退.提齣一種新的刪除HB(κ)樹的結點的算法,其主要思想是先自上而下處理某些子樹再刪除結點,不涉及自下而上的後退.舉例說明新算法的執行過程.證明新算法是正確的.與Foster的刪除HB(κ)樹的結點的算法相比,新算法不涉及輔助棧的使用.設n是HB(κ)樹的結點的箇數.新算法的時間複雜性是0(log2n),與Foster的刪除HB(κ)樹的結點的算法的相同.實驗結果錶明新算法的平均執行對間比Foster的刪除HB(κ)樹的結點的算法短.新算法的空間複雜性是O(1),比Foster的刪除HB(κ)樹的結點的算法低.
Foster적산제HB(κ)수적결점적산법적주요사상시선산제결점재자하이상처리모사자수,섭급자하이상적후퇴.제출일충신적산제HB(κ)수적결점적산법,기주요사상시선자상이하처리모사자수재산제결점,불섭급자하이상적후퇴.거례설명신산법적집행과정.증명신산법시정학적.여Foster적산제HB(κ)수적결점적산법상비,신산법불섭급보조잔적사용.설n시HB(κ)수적결점적개수.신산법적시간복잡성시0(log2n),여Foster적산제HB(κ)수적결점적산법적상동.실험결과표명신산법적평균집행대간비Foster적산제HB(κ)수적결점적산법단.신산법적공간복잡성시O(1),비Foster적산제HB(κ)수적결점적산법저.
