-
题名基于双链表的严格平衡二叉树建立
被引量:1
- 1
-
-
作者
王防修
刘春红
-
机构
武汉轻工大学数学与计算机学院
鄂钢驰久钢板弹簧有限责任公司
-
出处
《武汉轻工大学学报》
CAS
2015年第3期75-79,共5页
-
基金
国家自然科学基金资助项目(61179032)
-
文摘
针对目前严格平衡二叉树的建立需要借助有序顺序表来实现的问题,提出一种无需借助有序顺序表也可建立严格平衡二叉树的算法。为了建立关键字的严格平衡二叉树,需要首先建立一个关键字的有序双链表,然后用分治法构造严格平衡二叉树的根节点和左右子树。为了验证所建立的二叉树是严格平衡的,还提出了判断一棵二叉树严格平衡的两种检验方法。其中,严格平衡二叉树的定义法是一种直接判断法,而平均查找长度法可以间接判断一棵二叉树的平衡性。算例仿真表明,无需借助有序顺序表也可建立一棵严格平衡二叉树。
-
关键词
升序双链表
严格平衡二叉树
精确查询
二分查找
查找效率
-
Keywords
ascending double linked list
strict balanced binary tree
precise query
binary search
search efficiency
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名一种无需借助栈的严格平衡二叉树建立
- 2
-
-
作者
魏志威
王防修
-
机构
武汉轻工大学数学与计算机学院
-
出处
《武汉轻工大学学报》
2015年第4期47-50,共4页
-
基金
武汉轻工大学校级大学生创新创业训练计划项目(xsky2015031)
-
文摘
针对当前严格平衡二叉树的建立需要借助栈来实现的问题,提出一种无需借助栈也能建立严格平衡二叉树的算法。为能对关键字进行二分查找,需要对现有的关键字序列进行排序,以便统计关键字的有序序列中每个关键字在二分查找时的比较次数。在统计完所有关键字的二分查找的比较次数后,通过关键字比较次数序列的排序得到严格平衡二叉树序列。最后,用非递归的二叉排序树插入算法依次插入严格平衡二叉树序列的每个关键字,得到的二叉排序树就是一棵严格平衡二叉树。算例仿真表明,无需借助栈也可建立一棵严格平衡二叉树。
-
关键词
选择排序
二叉排序树
严格平衡二叉树
二分查找
查找效率
-
Keywords
Selection sort
Two binary sort tree
Strict balanced two binary tree
Binary search
Search efficiency
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-
-
题名严格平衡二叉排序树及其构造
被引量:7
- 3
-
-
作者
岑岗
周炳生
-
机构
浙江科技学院
-
出处
《计算机工程与应用》
CSCD
北大核心
2005年第13期57-60,共4页
-
文摘
论文对一直沿用至今的平衡二叉树和平衡二叉排序树概念的合理性提出质疑,给出了二叉树结点的严格平衡因子和严格平衡二叉树及严格平衡二叉排序树的新概念。论文给出的构造严格平衡二叉排序树的递归算法及二叉排序树元素插入和删除的严格平衡化过程比动态构造平衡二叉排序树的传统Adelson-Velskii和Landis算法更加简单而自然。
-
关键词
严格平衡因子
严格平衡二叉树
严格平衡二叉排序树
平衡因子
平衡二叉树
平衡二叉排序树
-
Keywords
strict balance factor,strict balanced binary tree,strict balanced binary sort tree,balance factor,balanced binary tree,balanced binary sort tree
-
分类号
TP311
[自动化与计算机技术—计算机软件与理论]
-
-
题名一种构建严格平衡二叉搜索树的非递归算法
被引量:4
- 4
-
-
作者
王防修
周康
-
机构
武汉轻工大学数学与计算机学院
-
出处
《武汉工业学院学报》
CAS
2013年第4期32-34,43,共4页
-
基金
国家自然科学基金资助项目(61179032)
-
文摘
针对传统算法所构造的平衡二叉搜索树并非真正平衡的二叉搜索树,设计了一种构建严格平衡二叉搜索树的非递归算法。改进后的算法具有计算速度快、占用内存小、计算机易于实现等优点。改进算法的核心是生成严格二叉搜索树的先序序列,提出了对升序序列的进行二分得到严格二叉搜索树的先序序列,讨论并给出了构建严格二叉搜索树的快速算法,该算法充分利用了栈在计算过程中提供的二分信息得到严格二叉搜索树的先序序列,该算法与传统算法相比可更快地构建严格二叉搜索树。
-
关键词
二叉搜索树
平衡二叉树
严格平衡二叉树
平衡二叉搜索树
严格平衡二叉搜索树
-
Keywords
two binary search tree
balance two binary tree
strict balance two binary tree
balance two binary search tree
strict balance two binary search tree
-
分类号
TP391
[自动化与计算机技术—计算机应用技术]
-