Как пересечь двоичное дерево в O (n) время без дополнительной памяти
Возможно, ModelState недействителен
...
if (!ModelState.IsValid)
{
var viewModel = new MovieViewModel
{
Generes = _context.Generes.ToList()
};
return View("MovieForm", viewModel);
}
...
4 ответа
Любая хорошая книга алгоритма будет иметь этот алгоритм, посмотрите, например, в Knuth (TAOCP Я 2.3.1 Пересекающий двоичные деревья, упражнение 21). Однако, потому что этот алгоритм изменяет дерево на месте, необходимо соблюдать экстремальную осторожность в многопоточной среде.
Вы могли бы также использовать поточные деревья (см. в Knuth).
Основная идея подобна алгоритму инверсии списка, с одним суперужасным хитрым взломом (с теоретической точки зрения, вероятно, обман), на основе того, что указатели (во всем langugae, в настоящее время известном людям), 0 режимов 4 как целые числа.
Идея состоит в том, что можно зеркально отразить указатели на пути вниз деревом для указания вверх. Проблема состоит в том, что - и это - то, где Вы отклоняете из алгоритма инверсии списка - при отслеживании в обратном порядке Вас, должен знать если левые точки или правые точки; в которой точке мы используем взлом.
Псевдо код следует:
current = root->left
next = current
while (current != null) {
next = current->left
current->left = static_cast<int>(prev) + 1 // ugly hack.
current = next
}
status = done
while (current != root or status != done) {
if (status = done) {
if (static_cast<u32>(current->left) %4 = 1) {
next = static_cast<u32>(current->left) -1
current->left = prev
status = middle
}
else {
next = current->right
current->right = prev
status = done
}
prev = current
current = next
}
else if (status == left) {
if (current->left) {
prev = current->left
current->left = static_cast<u32>(next) +1
next = current
}
else
status = middle
}
else if (status == right) {
if (current->right) {
prev = current->right;
current ->right = next;
next = current
}
else
status = done
}
else {// status == middle
work_on_node(current)
status = right
}
}
Алгоритм того парня интересен, но нужно указать, что это действительно требует O (зарегистрируйте n), дополнительные биты пространства для пересечения двоичного дерева с n узлами. Необходимые площади должны измеряться в битах, не байтах - обычно они выходят из строя в то же самое, когда Большой, О, нотация используется, но случаи как это указывают, почему важно сделать различие.
Для наблюдения этого спросите, как дерево с больше, чем 2^32-1 узлы может быть пересечено с помощью единственного целого числа устройства хранения данных (на 32-разрядной платформе).
Используйте O (1) устройство хранения данных, чтобы помнить, что "последний узел посетил" указатель. Можно инициализировать его к 0 или некоторому неизвестному значению.
Для обхода дерева запустите в корневом узле. Посмотрите на обоих из детей узла. Если Ваш "последний посещаемый узел" равен правильному узлу, то ступите в родительский узел. Если "последний посещаемый" равно левому узлу, то ступите в правильный узел. Еще ступите в левый узел.
Повторитесь, пока Вы не закончили обходить целое дерево. Единственный реальный ум использует одну переменную для запоминания, куда Вы происходите из того, для решения, куда пойти затем. Это делает обход детерминированным.
Вы закончите тем, что брали O (n) шаги. Вы посетите каждый средний узел три раза и каждый лист однажды, таким образом, Вы будете все еще O (N). Устройство хранения данных является O (1).