Самый короткий путь между двумя узлами в бесконечном, полном двоичном дереве?

Question

Предположим, что у нас есть бесконечное, полное двоичное дерево, где узлы пронумерованы 1, 2, 3, ... по их положению в поэтапном обходе дерева. Учитывая индексы двух узлов u и v в дереве, как мы можем найти самый короткий путь между ними?

Спасибо!

Answer 1

@Jonathan Landrum указал на решение в своем комментарии. Этот ответ подсказывает это решение.

В любом дереве существует ровно один путь между любыми двумя узлами. Поэтому эта проблема сводится к определению уникального пути между этими двумя узлами.

В любом корневом дереве кратчайший путь между двумя узлами u и v может быть найден путем нахождения минимального общего предка x из двух узлов, а затем конкатенации путей от u до x и от x до v. В вашем случае , вам необходимо найти LCA двух узлов, затем склеить эти пути вместе.

Поскольку у вас есть бесконечное бинарное дерево, я полагаю, что представление выглядит следующим образом:

   1 
    /   \ 
     2    3 
    / \   / \ 
    4  5   6  7 
/\ /\  /\ /\ 
8 9 10 11  12 13 14 15 

Эта форма дерева имеет очень интересное свойство, если записать все числа в двоичном:

    1 
      /  \ 
     10     11 
    /  \  /  \ 
    100  101  110  111 
/ \ / \ / \ / \ 
1000 1001 1010 1011 1100 1101 1110 1111 

Есть несколько вещей, которые вы можете заметить. Во-первых, глубина каждого узла задается одним минусом индекса MSB.

Далее, обратите внимание, что если число имеет двоичное представление б б ... б _п-1 б _п, то его родитель б б .. b _n-1, и это левое дочернее событие, если b _n = 0 и правый ребенок, если b _n = 1. Применяя это свойство повторно, мы получаем следующее: узел u является k-ым предком of v тогда и только тогда, когда (v >> k) = u.

Это дает нам много работы. Как правило, вы бы вычислить LCA (и, v) следующим образом:

1. Если и глубже, чем у, шаг вверх от и до тех пор, пока достигнет узла на той же глубине, у (и, вице- наоборот, шаг вверх от v, если v глубже).
2. Пройдите вверх от u и v с той же скоростью, пока они не достигнут того же узла. Этот узел является LCA.

Мы можем реализовать это непосредственно во времени O (log max {u, v}) следующим образом. Чтобы выполнить шаг (1), вычислите индекс MSB u и v, чтобы определить глубины d (u) и d (v) каждого узла. Предположим WLOG, что d (v) ≥ d (u). В этом случае мы можем найти предка u, который находится на той же глубине v за время O (1), вычисляя v >> (d (u) - d (v)). Острота! Чтобы сделать шаг (2), мы сравниваем u и v и, если они неравны, сдвигайте каждый, оставленный одним пятном, имитируя повышение уровня на один уровень. Максимальное количество раз, которое мы можем сделать, дается O (log max {u, v}), поэтому общая продолжительность выполнения O (log max {u, v}).

Однако мы можем ускорить это экспоненциально, используя модифицированный двоичный поиск.Глубина LCA u и v должна быть между 0 и min {d (u), d (v)}. Как только мы находим общего предка x из u и v, мы знаем, что все предки x также являются обычными предками u и v. Поэтому мы можем бинарный поиск по возможным глубинам LCA для u и v, вычисляя предка каждый узел с этой глубины, используя бит-сдвиг. Это будет выполняться во времени O (log log max {u, v}), так как максимальная глубина u равна O (log u), а максимальная глубина v равна O (log v).

Как только мы обнаружили этого предка, мы можем вычислить путь между u и v следующим образом. Вычислите путь от u до этого предка, многократно отбрасывая один бит от u до тех пор, пока мы не достигнем общего предка. Вычислите путь от v к предшественнику таким же образом, а затем примените обращение к пути к пути, найденному на первом шаге. Длина этого пути определяется O (| log u - log v |), поэтому время выполнения O (| log u - log v |).

С другой стороны, если вам просто нужна длина пути, вы можете суммировать расстояние от u до LCA (u, v) и от LCA (u, v) до v. Мы можем вычислить эти значения в O (log log max {u, v}) каждый раз, поэтому время выполнения равно O (log log max {u, v}).

Надеюсь, это поможет!