Постепенно сохраняйте путь от корневого узла к узлу многостороннего дерева во время вставки, чтобы операция хранения не имела сложности O (n)

Прямо сейчас ваше решение имеет O(1) время поиска, O(h) время вставки и O(n^2) сгибание пространства, где n - количество узлов, а 'h - высота, которая не превышает n.

Вы можете найти компромисс с O(log n) поиском, O((log n)^2) вставкой и O(n log n) пробелом следующим образом:

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

Ответить на вопрос, является ли y предком x, тривиально, если y не имеет глубины ниже, чем x. Назовите глубины узлов dy и dx. Вы знаете, что если y является предком x, то это dx-dy предок x. То есть, если dy = 5 и dx = 17, вы знаете, что если y является x предком, то он на 17 - 5 уровней выше x.

Следовательно, вы можете выполнять поиск, рекурсивно перепрыгивая на максимально возможное расстояние вверх по дереву от x, не выходя за пределы целевого предка. Например, если вы начинаете с глубины 16 и хотите найти предка на глубине 6, вас интересует предок на 10 уровней выше. Вы не можете перепрыгнуть на 16 уровней вверх, так как это приведет к пролету над целевым предком, поэтому вместо этого вы прыгаете на 8. Теперь вы находитесь на глубине 16-8 = 8, а оставшееся расстояние до целевого предка, равное 6, равно 2. Поскольку есть указатель, который идет ровно на два шага вверх, вы следуете за ним и достигли целевой предок.

Каждый раз, когда вы следуете за указателем вверх по дереву, вы приближаетесь хотя бы к половине пути к своей цели, поэтому максимальное количество указателей, которым вы можете следовать, составляет O(log n).

При вставке узла e в качестве дочернего элемента другого узла x вы можете построить указатели перехода e, найдя предков x на расстоянии 1, 3, 7, 15 и т. Д. (Поскольку e находится на один уровень дальше от всех этих узлов, чем x. ). Есть O(log n)таких запросов. Как мы утверждали выше, каждый поиск занимает O(log n) времени. Таким образом, общая сумма составляет O((log n)^2).

Эту операцию можно было бы даже сделать еще быстрее, сохранив некоторую дополнительную информацию, но я не могу точно понять, как именно сейчас.

ПРИМЕЧАНИЕ. Эта идея на самом деле является частью классического решения проблемы с предками уровня < / а>. Классическое решение позволяет выполнять поиск, как вы их описали, в O(1) раз, сохраняя пространство всей структуры данных равным O(n). Однако структура данных статична, поэтому в решении не указано, как выполнять вставки. Возможно, существует способ адаптировать предка уровня к динамическому сценарию и получить даже лучшее время работы, чем я описал здесь, но я не уверен, как это сделать.

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

Сопоставьте свои узлы в HashMap<node-id, node>.

Теперь, когда тебе нужно

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

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

В достаточно сбалансированном дереве это будет время выполнения O (Log n) (для обхода дерева) и O (n) пространства (HashMap).

Если вы пойдете с вашим текущим дизайном хранения пути от каждого узла до корня, тогда у вас будет время выполнения O (Log n) (при условии сбалансированного дерева) и O (n * Log n) пространство для хранения Зарегистрируйте путь длиной n для каждого из n узлов.