14 March 2013 Analytic criterion and algorithm for the lowest common ancestor of two neighboring nodes in a complete binary tree
Author Affiliations +
Proceedings Volume 8768, International Conference on Graphic and Image Processing (ICGIP 2012); 87681F (2013) https://doi.org/10.1117/12.2010765
Event: 2012 International Conference on Graphic and Image Processing, 2012, Singapore, Singapore
Abstract
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.
© (2013) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Xingbo Wang, Jun Zhou, "Analytic criterion and algorithm for the lowest common ancestor of two neighboring nodes in a complete binary tree", Proc. SPIE 8768, International Conference on Graphic and Image Processing (ICGIP 2012), 87681F (14 March 2013); doi: 10.1117/12.2010765; https://doi.org/10.1117/12.2010765
PROCEEDINGS
5 PAGES


SHARE
RELATED CONTENT


Back to Top