完全二叉树相邻结点最近共同祖先的一种快速算法

Fast algorithm for finding the lowest common ancestor of two neighboring nodes in a complete binary tree

寻找二叉树中两结点的最近共同祖先问题一直是图论与计算机科学关注的问题。首先,证明了完全求解二叉树相邻结点最近共同祖先的一个定理,该定理的求解方法主要涉及到位运算,无需递归搜索,既易于软件编程实现又易于通过硬件实现,然后给出了一个具有对数时间复杂度O(lnn)的快速算法及C++示例。

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 first proves a theorem for finding the LCA of two neighboring nodes in a complete binary tree. The method in the theorem mainly concerns bitwise operations, needs no recursive searching procedures and thus is easy to be realized by software programming as well as firmware mode. In the end of the paper, an algorithm that has logarithmic time complexity is also presented with C＋＋ implementation.