A more localized, efficient Lowest Common Ancestor algorithm defined by several binary trees?

Question

I have several binary trees stored in an array. In each slot, either nil (or null, select your language), or a fixed tuple that stores two numbers: the indices of two "children". No node will have only one child - it is either not or two.

Think of each slot as a binary node that stores pointers only for its children and has no built-in value.

Take this binary tree system:

    0 1
   / \ / \
  2 3 4 5
 / \ / \
6 7 8 9
   / \
 10 11

Associated Array:

   0       1       2      3     4      5      6      7        8     9     10    11
[ [2,3] , [4,5] , [6,7] , nil , nil , [8,9] , nil , [10,11] , nil , nil , nil , nil ]

I already wrote simple functions for finding direct parents of nodes (just by searching from the front until there is a node that contains a child)

, , .

P(m,n)

m n - , LCA " " node, m n ( , ..). , nil .

, :

P( 6,11)   # => 2
P( 3,10)   # => 0
P( 8, 6)   # => nil
P( 2,11)   # => 2

, , , , ( node A 0 1 "" -1), :

A-0-2-6-2-7-10-7-11-7-2-0-3-0-A-1-4-1-5-8-5-9-5-1-A

node m n, ; , P (6,11), 6 11 . , , 2, . A (-1) , nil.

 -- Calculating P(6,11) --

A-0-2-6-2-7-10-7-11-7-2-0-3-0-A-1-4-1-5-8-5-9-5-1-A
      ^ ^        ^
      | |        |
      m lowest   n

, , , , - ... , , , LCA, .

, , ? , , , ? , , - "" / node, , - .

, , , 3025, 0, , , , , , .

?

---

, , .

, n X, (X-1) , n. :

        0
       / \
      /   \
     /     \
    1       2        6
   / \     / \      / \
  2   3   9  10    7   8
     / \              / \
    4   5            11 12

- .

, , .

Answer 1

, , , ? , - , . 6 11:

6  -> 2 -> 0
11 -> 7 -> 2 -> 0

, , :

left = left_start
right = right_start

while left > 0 and right > 0
    if left = right
        return left
    else if left > right
        left = parent(left)
    else
        right = parent(right)

:

left    right
----    -----
 6        11    (right -> 7)
 6        7     (right -> 2)
 6        2     (left -> 2)
 2        2     (return 2)

?

Answer 2

, : LCA .

:

,

, , , . 1. . 2. . 3. . 4. .

: - SODA 1999

Answer 3

Haskell. , , , . http://pastebin.com/ha4gqU0n.

, , , :

• m, n.
• m, n.
• n, m.
• m, n, - k.

A node m, n , .

a node k , :

join :: Int -> Result -> Result -> Result
join _ (HasBoth k) _ = HasBoth k
join _ _ (HasBoth k) = HasBoth k
join _ HasNeither r = r
join _ r HasNeither = r
join k HasLeft HasRight = HasBoth k
join k HasRight HasLeft = HasBoth k

k node; k m n, "" join.

, , :

• node
• , node, ,

, , .

, . , , m n, , , , , , ( , ).

, . , , , . - .

Answer 4

I think you can just jump back through the array, always replacing the higher of the two indices with your parent until they are equal or another parent is found:

(defun lowest-common-ancestor (array node-index-1 node-index-2)
  (cond ((or (null node-index-1)
             (null node-index-2))
         nil)
        ((= node-index-1 node-index-2)
         node-index-1)
        ((< node-index-1 node-index-2)
         (lowest-common-ancestor array
                                 node-index-1
                                 (find-parent array node-index-2)))
        (t
         (lowest-common-ancestor array
                                 (find-parent array node-index-1)
                                 node-index-2))))