Analytic Criterion and Algorithm for the Lowest Common Ancestor of Two Neighboring Nodes in a Complete Binary Tree

摘要：

Finding the lowest common ancestor (LCA) of two nodes in a binary tree has been focused both in graph theory and computer science. The paper puts forward and proves an analytic criterion for the LCA of two neighboring nodes in a complete binary tree. The criterion mainly concerns addition, subtraction and bitwise operations, needs no searching procedures and thus is easy to implement in software programming as well as hardware programming. An algorithm that has logarithmic time complexity is also presented with C-language implementation in the paper.

关键词： Binary tree lowest common ancestor Criterion

作者: Wang Xiongbo Zhou Jun

作者单位: Department of Mechtronic Engineering Foshan University Foshan City, Guangdong Province, China College of Information Science and Technology Hunan Agricultural University Changsha City, Hunan Pro

会议类型: 国际会议

会议名称: 2011 3rd International Conference on Computer and Automation Engineering(ICCAE 2011)(2011年第三届IEEE计算机与自动化工程国际会议)

会议地点: 重庆

会议语种:英文

页码: 270-272

在线出版日期: 2011-01-21（万方平台首次上网日期，不代表论文的发表时间）