Нахождение общего родителя в идеальном бинарном дереве

Question

Этот вопрос:

Существуют ли эффективные способы заполнения сбалансированной древовидной структуры

обеспечивает аналитический способ маркировки идеального двоичного дерева любой глубины.

В таком дереве есть ли способ эффективно вычислить первый общий родительский элемент произвольного подмножества листовых узлов?

Например, учитывая следующее двоичное дерево:

Я ищу способ, если:

Вход: 3,5 Выход: 0

Вход is: 3,5,6 Выходные данные: 0

Входные данные: 3,4 Выходные данные: 1

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

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

Answer 1

Пусть H будет высотой вашего дерева, и пусть k будет количеством чисел в ваших входных данных.

Если вы начнете нумерацию узлов с 1 и запишите двоичные числа узлов, это будет Стало ясно, что номер каждого узла является префиксом номеров всех его дочерних элементов. Итак, чтобы найти наименьшего общего предка, вы должны найти наибольший общий префикс (GCP) двоичных чисел.

Let min и max быть минимальными и максимальными числами в вашем подмножестве. Если числа в вашем входе уже отсортированы, вы можете найти min и max в O(1). Если они не отсортированы, вы можете найти min и max в O(k * H).

GCP всех двоичных чисел - это GCP min и max - вы можете найти его тривиально в O(H).

Этот алгоритм работает в O(H), если числа отсортированы, и в O(k * H) в противном случае (хотя ваш алгоритм работает и в O(k * H), если вы правильно его реализуете).