Trie Hashing结构平均路径长度分析  

Analysis of average path length for Trie Hashing structure

作　　者：王宏[1] 熊西文[1] 朱振文 

机构地区：[1]大连理工大学应用数学系

出　　处：《大连理工大学学报》1991年第5期507-514,共8页Journal of Dalian University of Technology

摘　　要：针对 Ｗ．Ｌｉｔｗｉｎ提出的 Ｔｒｉｅ Ｈａｓｈｉｎｇ结构的路径长度分析问题，研究并揭示 了该结构所具有的某些新的性质；建立了必要的分析前提．从而给出了 Ｔｒｉｅ Ｈａｓｈｉｎｇ 结构平均路径长度的分析方法。所得估计式仅与外部结点数目有关，理论分析与模拟 实验的结果表明，对于 Ｔｒｉｅ Ｈａｓｈｉｎｇ 结构，文中的分析方法明显优于 Ｋｌｅｉｎ 和 ｗｏｏｄ的类似结果。The research aims at solving the problem of the analysis of the average path length for Trie Hashing structure proposed by W.Litwin. Some new properties that exist in the structure are further investigated and revealed.The. necessary for basis analyses is established and then an analysis of the average path length for Trie Hashing structure is presented. An estimation is obtained to give a formula for the average path length which is a function of the only number of external nodes.Furthermore, the results of simulations are compared with the results obtained from the analysis method proposed by Klein and Wood

关 键 词：T-H结构 路 树 算法分析 

分 类 号：TP301.5[自动化与计算机技术—计算机系统结构]