Что случилось с моей идеей о обходе

Question

Когда его попросили создать BST учитывая обход, есть ответы, данные, как это: http://www.geeksforgeeks.org/construct-bst-from-given-preorder-traversa/

, которые требуют много кода.

Мой вопрос: почему я не могу просто вставить в пустое дерево, чтобы дать правильный ответ? Есть ли какой-нибудь пример, когда простое вставка может привести к неправильному ответу? Например, в примере, приведенном в этой ссылке, мы имеем {10, 5, 1, 7, 40, 50} как обход предварительного порядка. Но не только использование обычного метода вставки BST 6 раз в порядке списка предзаказа дает соответствующее дерево? Могу ли я получить контрпример и/или объяснение, почему я ошибаюсь? Я не смог придумать контрпример.

Answer 1

Просто позвонив insert правильное число раз должны действительно произвести правильное дерево - но это займет O (N журнал п) сложность, где может быть сделано с O (N) сложности.

Честно говоря, если вы не работаете с большим количеством данных, разница может быть не очень важна для вас.