Analytic criterion and algorithm for the lowest common ancestor of two neighboring nodes in a complete binary tree

Xingbo Wang; Jun Zhou

doi:10.1117/12.2010765

14 March 2013 Analytic criterion and algorithm for the lowest common ancestor of two neighboring nodes in a complete binary tree

Xingbo Wang, Jun Zhou

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.

Citation Download Citation

Xingbo Wang and 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); https://doi.org/10.1117/12.2010765

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available