Самая быстрая нерекурсивная реализация LCA?

Question

Вот алгоритм, который я придумал для нерекурсивного нахождения младшего общего предка двух узлов в двоичном дереве. Вот основная стратегия:

1. Используйте словарь/хеш-таблицу для хранения дерева. Каждая пара ключ-значение представляет собой узел и его родительский элемент.
2. Начиная с каждого из двух узлов, поднимитесь по дереву, установив переменную, представляющую значение каждого узла, в значение родительского элемента, сохраняя пройденные значения в хэш-наборе (по одному для каждого из двух узлов).
3. Поиск завершен при достижении любого из следующих условий: (a) значение двух узлов равно; или (b) когда два пути пересекаются друг с другом (то есть, хешсет перемещенных значений узла 1 содержит текущее значение для узла 2 или наоборот); или (c) переданный узел не существует в дереве (в этом случае алгоритм завершается и возвращает -1).

Мое понимание заключается в том, что наихудшая временная и пространственная сложность моего алгоритма - это O (log (n)), так как нам никогда не нужно совершать более 2 * дорожек по высоте или хранить более 2 * значений высоты в наших хэшсетах (и поскольку время поиска для хешсет и словаря дерева - O (1)).

Следующий мой код (C#). Пожалуйста, сообщите, если я правильно в моем анализе, или если есть более эффективный (нерекурсивный) способ сделать это:

int LowestCommonAncestor(int value1, int value2, Dictionary<int, int> tree) 
{ 
    var value1Visited = new HashSet<int>(); 
    var value2Visited = new HashSet<int>(); 
    while (true) 
    { 
     if (value1 == value2) return value1; 
     if (value1Visited.Contains(value2)) return value2; 
     if (value2Visited.Contains(value1)) return value1; 

     int nextValue1; 
     int nextValue2; 

     if (tree.TryGetValue(value1, out nextValue1)) 
     { 
      //Walk node 1 up the tree: 
      value1 = nextValue1; 
      value1Visited.Add(value1); 
     } 
     else 
     { 
      //Node doesn't exist in tree: 
      return -1; 
     } 

     if (tree.TryGetValue(value2, out nextValue2)) 
     { 
      //Walk node 2 up the tree: 
      value2 = nextValue2; 
      value2Visited.Add(value2); 
     } 
     else 
     { 
      //Node doesn't exist in tree: 
      return -1; 
     } 
    } 
} 

Answer 1

1. Поднимитесь от каждого узла к корню, чтобы измерить его глубину

2. Переместите путь от более глубокого узла до тех пор, пока вы не достигнете той же глубины, что и более мелкая.

3. Перемещение по дорожкам с обоих узлов (т. Е. Сохранение одинаковой глубины на обоих дорожках) до тех пор, пока они не совпадут.

Answer 2

Вам не нужны два набора хэшей.

1. Перейти вверх и собрать в одном хэше установить предок одного узла
2. Перейти вверх от второго узла, и на каждом из своих предков, проверить, если путь собранный на этапе 1 содержит текущий предок второй. Остановитесь на первом общем.

С D, являющимся максимальной глубиной дерева, сложность сложна в O (D).

Худший размер сложности в N - количество узлов - когда дерево вырождено в списке, одним из узлов является глава этого списка, а другая - хвост.

Если дерево сбалансировано, D = log (N) - с базой журнала, являющейся числом потомков узла (двоичный - log2, тройной - log3 и т. Д.).

Answer 3

Вот тогда мой пересмотренный алгоритм:

int LCA(int value1, int value2, Dictionary<int, int> tree) 
{ 
    if (!tree.ContainsKey(value1) || !(tree.ContainsKey(value2))) return -1; 

    int depth1 = 0; 
    int depth2 = 0; 
    int tmpVal1 = value1; 
    int tmpVal2 = value2; 

    while (tmpVal1 != -1) 
    { 
     tmpVal1 = tree[tmpVal1]; 
     depth1++; 
    } 

    while (tmpVal2 != -1) 
    { 
     tmpVal2 = tree[tmpVal2]; 
     depth2++; 
    } 

    if (depth1 > depth2) 
    { 
     while (depth1 > depth2) 
     { 
      value1 = tree[value1]; 
      depth1--; 
     } 
    } 

    else if (depth2 > depth1) 
    { 
     while (depth2 > depth1) 
     { 
      value2 = tree[value2]; 
      depth2--; 
     } 
    } 
    while (value1 != value2) 
    { 
     value1 = tree[value1]; 
     value2 = tree[value2]; 
    } 

    return value1; 
}