一种构建严格平衡二叉搜索树的非递归算法  

A non-recursive algorithm of constructing strict balance two binary search tree

作　　者：王防修[1] 周康[1] 

机构地区：[1]武汉轻工大学数学与计算机学院,湖北武汉430023

出　　处：《武汉工业学院学报》2013年第4期32-34,43,共4页Journal of Wuhan Polytechnic University

基　　金：国家自然科学基金资助项目(61179032)

摘　　要：针对传统算法所构造的平衡二叉搜索树并非真正平衡的二叉搜索树,设计了一种构建严格平衡二叉搜索树的非递归算法。改进后的算法具有计算速度快、占用内存小、计算机易于实现等优点。改进算法的核心是生成严格二叉搜索树的先序序列,提出了对升序序列的进行二分得到严格二叉搜索树的先序序列,讨论并给出了构建严格二叉搜索树的快速算法,该算法充分利用了栈在计算过程中提供的二分信息得到严格二叉搜索树的先序序列,该算法与传统算法相比可更快地构建严格二叉搜索树。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 a strict 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 a s 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 a strict two binary search tree.

关 键 词：二叉搜索树 平衡二叉树 严格平衡二叉树 平衡二叉搜索树 严格平衡二叉搜索树 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]