Как преобразовать двоичное дерево в оперативное дерево двоичного поиска, т.е. мы не можем использовать дополнительное пространство
Как преобразовать двоичное дерево в оперативное дерево двоичного поиска, т.е. мы не можем использовать дополнительное пространство.
3 ответа
Вы мало что даете, но если требование такое, как я думаю, у вас есть двоичное дерево, уже созданное и хранящееся в памяти, но не отсортированное (в любом случае, как вы хотите, чтобы оно было отсортировано ).
Я предполагаю, что узлы дерева выглядят как
struct tree_node {
struct tree_node * left;
struct tree_node * right;
data_t data;
};
Я также предполагаю, что вы можете читать C
Пока мы могли бы просто сидеть и гадать, почему это дерево было создано, не будучи созданным в отсортированном порядке, чтобы не приносит нам никакой пользы, поэтому я проигнорирую это и займусь сортировкой.
Требование не использовать дополнительное пространство является странным. Временно будет лишнее место, хотя бы в стеке. Я собираюсь предположить, что это означает, что вызов malloc или что-то в этом роде, а также что результирующее дерево должно использовать не больше памяти, чем исходное несортированное дерево.
Первое и самое простое решение - выполнить предварительный обход несортированного дерева, удалив каждый узел из этого дерева и сделав отсортированную вставку в новое дерево. Это O (n + n log (n)), то есть O (n log (n)).
Если это не то, что они хотят, и вам придется использовать ротации и прочее… это ужасно!
Я думал, что это можно сделать, выполнив странную версию сортировки кучи, но у меня возникли проблемы. Еще одна вещь, которая пришла в голову, которая была бы ужасно медленной, - это сделать странную вариант пузырьковой сортировки на дереве.
Для этого каждый узел сравнивается и, возможно, обменивается местами с каждым из своих прямых потомков (и, следовательно, также со своим родителем) несколько раз, пока вы не пройдете дерево и не найдете необходимых свопов.Вариант с шейкерной сортировкой (пузырьковая сортировка слева направо и справа налево) будет работать лучше всего, и после начального прохода вам не нужно будет перемещаться вниз по поддеревьям, которые не выглядели не по порядку относительно своего родителя. .
Я уверен, что либо этот алгоритм был придуман кем-то еще до меня и имеет крутое название, которого я просто не знаю, либо он в корне ошибочен, чего я не вижу.
Приступить к расчетам времени выполнения для второго предложения довольно сложно. Сначала я подумал, что это будет просто O (n ^ 2), как сортировка пузырьков и шейкер, но я не могу убедить себя, что предотвращение обхода поддерева может не выиграть достаточно, чтобы сделать его немного лучше, чем O (n ^ 2). По сути, пузырьковая и шейкерная сортировки также получают эту оптимизацию, но только на концах, где полная сортировка происходит раньше, и вы можете сократить пределы. С помощью этой древовидной версии вы также получаете возможность избежать фрагментов в середине набора. Что ж, как я уже сказал, вероятно, он фатально ошибочен.
Двоичное дерево обычно является двоичным деревом поиска, и в этом случае преобразование не требуется.
Возможно, вам нужно уточнить структуру того, из чего вы конвертируете. Не является ли ваше исходное дерево несбалансированным? Оно не упорядочено по ключу, по которому вы хотите выполнить поиск? Как вы пришли к исходному дереву?
Ну, если это вопрос собеседования, первое, что я бы выпалил (без реальных мыслей), это следующее: рекурсивно перебирать весь двоичный файл и находить наименьший элемент. Выньте его из двоичного дерева. Теперь повторите процесс, в котором вы перебираете все дерево, находите наименьший элемент и добавляете его как родительский для последнего найденного элемента (при этом предыдущий элемент становится левым дочерним элементом нового узла). Повторяйте столько раз, сколько необходимо, пока исходное дерево не станет пустым. В конце концов, у вас остается наихудшее отсортированное двоичное дерево - связанный список. Ваш указатель указывает на корневой узел, который является самым большим элементом.
Это ужасный алгоритм на все случаи жизни - время работы O (n ^ 2) с наихудшим выходом двоичного дерева, но это достойная отправная точка, прежде чем придумать что-то лучшее, и дает вам то преимущество, что вы можете писать код для этого примерно в 20 строках на доске.