一种有效的丰满树算法
DOI:
CSTR:
作者:
作者单位:

作者简介:

通讯作者:

中图分类号:

基金项目:


A Effective Full Tree Algorithm
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    本文提出了一种新的有效的丰满树数据结构及其插入、删除、查询、中序周游等的基本算法。这种数据结构不用指针场,而用顺序地址标法来保持树中结点的联系,从而使空间复杂度大为减少,而且其算法也得以简化。在插入、删除的结点个数相对于文件规模不算太大的情况下,该算法的时间复杂度也是比较好的。

    Abstract:

    When we use the binary tree to store data, one of the main problems is space complexity, and the other is degeneration. There must be some pointer fields to point out the successor of every node in the binary tree.Additional stack space is needed to complete the output of the nodes in the tree according to the sorted order. We usually insert and delete the nodes in a random way. If we do not make use of special techniques to insure the balancing of the binary tree, the tree probably would finaUy degenerate into a linear linked list. Consequently, the time complexity of the inquiry, insertion and deletion in the data structure is increased to a great extent.To solve the two problems mentioned above, the threaded tree, the balancing tree and the threaded balancing tree are employed to replace the ordinary binary tree. Among these techniques some can save stack space and others can solve degenerating problem. However, is there such a method w.hich can simultaneously solve those problems?A new, effective data structure of the full tree and the fundamental algorithms of its insertion, deletion, inquiry and symmetric order traversing are presented in this artile. In the data structure, without a pointer field, the relationship of the nodes in the tree is connected with sequential address notation. So the space complexity is considerably decreased and the fundamental algorithm is also simplified to a certain extent. If the inserting and deleting nodes are less than the nodes of the file, the time complexity of the algorithm is also comparatively good.

    参考文献
    相似文献
    引证文献
引用本文

顾立尧,王乐一.一种有效的丰满树算法[J].上海理工大学学报,1985,(1).

复制
分享
相关视频

文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:
  • 最后修改日期:
  • 录用日期:
  • 在线发布日期:
  • 出版日期:
文章二维码