武汉工业学院学报
武漢工業學院學報
무한공업학원학보
JOURNAL OF WUHAN POLYTECHNIC UNIVERSITY
2013年
4期
32-34,43
,共4页
二叉搜索树%平衡二叉树%严格平衡二叉树%平衡二叉搜索树%严格平衡二叉搜索树
二扠搜索樹%平衡二扠樹%嚴格平衡二扠樹%平衡二扠搜索樹%嚴格平衡二扠搜索樹
이차수색수%평형이차수%엄격평형이차수%평형이차수색수%엄격평형이차수색수
two binary search tree%balance two binary tree%strict balance two binary tree%balance two binary search tree%strict balance two binary search tree
针对传统算法所构造的平衡二叉搜索树并非真正平衡的二叉搜索树，设计了一种构建严格平衡二叉搜索树的非递归算法。改进后的算法具有计算速度快、占用内存小、计算机易于实现等优点。改进算法的核心是生成严格二叉搜索树的先序序列，提出了对升序序列的进行二分得到严格二叉搜索树的先序序列，讨论并给出了构建严格二叉搜索树的快速算法，该算法充分利用了栈在计算过程中提供的二分信息得到严格二叉搜索树的先序序列，该算法与传统算法相比可更快地构建严格二叉搜索树。
針對傳統算法所構造的平衡二扠搜索樹併非真正平衡的二扠搜索樹，設計瞭一種構建嚴格平衡二扠搜索樹的非遞歸算法。改進後的算法具有計算速度快、佔用內存小、計算機易于實現等優點。改進算法的覈心是生成嚴格二扠搜索樹的先序序列，提齣瞭對升序序列的進行二分得到嚴格二扠搜索樹的先序序列，討論併給齣瞭構建嚴格二扠搜索樹的快速算法，該算法充分利用瞭棧在計算過程中提供的二分信息得到嚴格二扠搜索樹的先序序列，該算法與傳統算法相比可更快地構建嚴格二扠搜索樹。
침대전통산법소구조적평형이차수색수병비진정평형적이차수색수，설계료일충구건엄격평형이차수색수적비체귀산법。개진후적산법구유계산속도쾌、점용내존소、계산궤역우실현등우점。개진산법적핵심시생성엄격이차수색수적선서서렬，제출료대승서서렬적진행이분득도엄격이차수색수적선서서렬，토론병급출료구건엄격이차수색수적쾌속산법，해산법충분이용료잔재계산과정중제공적이분신식득도엄격이차수색수적선서서렬，해산법여전통산법상비가경쾌지구건엄격이차수색수。
In view of the balance two binary search tree constructed with the traditional algorithm is not a really bal-ance binary search tree , this paper idesigns a non -recursive algorithm of constructing astrict balance two binary search tree .The improved algorithm has the advantages of faster calculation speed , small memory space ,being easy to be realized by computers .The core of the improved algorithmto is to generate the first order sequence of the strict two binary search tree .It is proposed to find the optimal solution of routing problem .It presents a method to gain the the first order sequence of the strict two binary search tree by dividing the ascending sequence into half ,discusses and gives as fast algorithm to construct the strict binary search tree .The algorithm makes full use of the information divided by two to gain the first order sequence of the strict two binary search tree .The algorithm has higher efficien-cy compared with the traditional algorithm to construct astrict two binary search tree .
