Изменения
→Обработка запроса
|proof= Пусть <tex>i</tex> {{---}} индекс самой правой единицы в двоичном представлении <tex>b</tex>. Из того, что <tex>b</tex> общий предок <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex> в полном двоичном дереве следует, что <tex>l-i</tex> левых бит, совпадающих в <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>, должны быть такими же и в <tex>b</tex>, а так как <tex>b</tex> наименьший общий предок, то <tex>i</tex> {{---}} минимальный такой индекс. То есть <tex>i</tex> самый левый бит, в котором различаются <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} y</tex>. А двоичное представление <tex>b</tex> состоит из <tex>l-i</tex> левых бит <tex>\operatorname{inlabel} x</tex> (или <tex>\operatorname{inlabel} y</tex>), единички и <tex>i</tex> нулей.
}}
Найдем вершину <tex>\operatorname{inorder} z</tex>, где <tex>z = LCA(x, y)</tex>. На прошлом шаге была найдена вершина
<tex>LCA(\operatorname{inlabel} x, \operatorname{inlabel} y)</tex>. Если бы в двоичном дереве были представлены все вершины,
то это и было бы ответом. Но такой вершины может не оказаться. Воспользуемся значениями <tex>\operatorname{ascendant} \operatorname{inlabel} x</tex> и <tex>\operatorname{ascendant} \operatorname{inlabel} y</tex>. Они характеризуют пути
из вершин <tex>\operatorname{inlabel} x</tex> и <tex>\operatorname{inlabel} x</tex> к корню. С их помощью (с помощью
операции ''логическое и''), можно получить список вершин, через которые проходят оба эти пути и взять с пересечения
самую низкую посещаемую обоими.
Для этого можно воспользоваться описанным при построении методом для нахождения <tex>\operatorname{inlabel} v</tex>.
После этих действий нами был получен путь, в котором находится ответ. Осталось посмотреть на точки входа
<tex>x</tex> и <tex>y</tex> на путь <tex>\operatorname{inlabel} LCA(x, y)</tex>.
Это можно сделать с помощью посчитанной функции <tex>\operatorname{head}</tex>: найти <tex>\operatorname{head} v'</tex>, где <tex>v'</tex> {{---}} вершина предпоследнего пути в пути. Тогда, поднявшись от нее на один вверх по начальному дереву,
получим искомую точку входа.
Имея две точки входа, можно, как и в первом случае, сравнить их по высоте и выбрать более высокое из них.
