计算机应用
計算機應用
계산궤응용
COMPUTER APPLICATION
2015年
3期
654-658
,共5页
江顺亮%胡世鸿%唐祎玲%葛芸%叶发茂%徐少平
江順亮%鬍世鴻%唐祎玲%葛蕓%葉髮茂%徐少平
강순량%호세홍%당의령%갈예%협발무%서소평
广义AVL树%放松平衡约束%重平衡%调整率
廣義AVL樹%放鬆平衡約束%重平衡%調整率
엄의AVL수%방송평형약속%중평형%조정솔
generalized Adelson-Velskii and Landis (AVL) tree%relaxed balance constraint%rebalancing%adjusting ratio
针对传统AVL(Adelson-Velskii and Landis)树重平衡算法代码量大、流程复杂、调整率过高的问题,提出一种统一重平衡算法,并提出广义AVL树的概念.统一重平衡算法能对AVL树的失衡节点进行自动分类、调整,取消了传统重平衡方法中的四种旋转操作.广义AVL树放松了AVL树的平衡约束,允许左右子树树高相差不超过N(N≥1),当更新操作(插入/删除)执行后,广义AVL树只在平衡约束条件不满足时采用统一重平衡算法进行调整.理论分析与实验结果表明,广义AVL树的调整率随着N的增大而显著降低:N为5时,调整率低于4％;N为13时调整率低于千分之一.广义AVL树的调整率远低于红黑树等经典数据结构,适合并发应用.
針對傳統AVL(Adelson-Velskii and Landis)樹重平衡算法代碼量大、流程複雜、調整率過高的問題,提齣一種統一重平衡算法,併提齣廣義AVL樹的概唸.統一重平衡算法能對AVL樹的失衡節點進行自動分類、調整,取消瞭傳統重平衡方法中的四種鏇轉操作.廣義AVL樹放鬆瞭AVL樹的平衡約束,允許左右子樹樹高相差不超過N(N≥1),噹更新操作(插入/刪除)執行後,廣義AVL樹隻在平衡約束條件不滿足時採用統一重平衡算法進行調整.理論分析與實驗結果錶明,廣義AVL樹的調整率隨著N的增大而顯著降低:N為5時,調整率低于4％;N為13時調整率低于韆分之一.廣義AVL樹的調整率遠低于紅黑樹等經典數據結構,適閤併髮應用.
침대전통AVL(Adelson-Velskii and Landis)수중평형산법대마량대、류정복잡、조정솔과고적문제,제출일충통일중평형산법,병제출엄의AVL수적개념.통일중평형산법능대AVL수적실형절점진행자동분류、조정,취소료전통중평형방법중적사충선전조작.엄의AVL수방송료AVL수적평형약속,윤허좌우자수수고상차불초과N(N≥1),당경신조작(삽입/산제)집행후,엄의AVL수지재평형약속조건불만족시채용통일중평형산법진행조정.이론분석여실험결과표명,엄의AVL수적조정솔수착N적증대이현저강저:N위5시,조정솔저우4％;N위13시조정솔저우천분지일.엄의AVL수적조정솔원저우홍흑수등경전수거결구,괄합병발응용.
