Двоичный поиск Обход предварительного предпросмотра деревьев, рекурсия против цикла?

Question

мы можем пройти через дерево двоичного поиска с помощью рекурсии, как:

void traverse1(node t) { 
    if(t != NULL) { 
     visit(t); 
     traverse1(t->left); 
     traverse1(t->right); 
    } 
} 

, а также через петлю (с стека), как:

void traverse2(node root) { 
    stack.push(root); 
    while (stack.notEmpty()) { 
     node next = stack.pop(); 
     visit(next); 
     if (next->right != NULL) 
      stack.push(next->right); 
     if (next->left != NUll) 
      stack.push(next->left) 
    } 
} 

Вопрос

Какой из более эффективна? Зачем?

Я думаю, что эти два метода сложности времени - это и O (n). так что все различия все в сложности пространства или ...?

Answer 1

Это будет зависеть от того, как вы определяете эффективность? Это во время выполнения, объем кода, размер исполняемого файла, объем пространства памяти/стека, или как легко понять код?

Рекурсия очень проста в кодировании, мы надеемся, легко понять и меньше кода. Зацикливание может быть немного сложнее (в зависимости от того, как вы оцениваете сложность) и кода. Рекурсия может быть проще понять и будет меньше в размере кода и в исполняемом размере. Recursion будет использовать больше пространства стека, предполагая, что у вас есть несколько предметов для поперечной.

Цилиндр будет иметь больший объем кода (как показывает пример выше), и его можно считать более сложным. Но поперечный - это всего один вызов, который нужно разместить в стеке, а не несколько. Поэтому, если у вас есть много элементов для поперечной, цикл будет быстрее, так как у вас нет времени на то, чтобы нажимать элементы в стеке и выталкивать их, что и произойдет при использовании рекурсии.

Answer 2

Сложность времени и пространства одинакова. Единственное отличие состоит в том, что traverse2 не называет себя рекурсивно. Этот должен сделать его немного быстрее, так как нажатие/выскакивание из стека является более дешевой операцией, чем вызов функции.

Это, я думаю, рекурсивная версия «чище», поэтому я лично использовал бы это, если на практике это не будет слишком медленным.

Answer 3

Обе версии имеют одинаковую сложность пространства и времени.

Рекурсия неявно использует стек (расположение памяти) для хранения контекста вызова, а второй использует абстрактный тип данных стека, эффективно эмулируя первую версию, используя стек явно.

Разница в том, что с первой версией вы рискуете переполнением стека с глубокими неуравновешенными деревьями, однако это проще концептуально (меньше возможностей для ошибок). Второй использует динамическое распределение для хранения указателей на родительские узлы.

Answer 4

Помимо эффективности, если ваше дерево слишком глубокое или если пространство вашего стека ограничено, вы можете столкнуться с переполнением стека!

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

Я знаю, что такие ограниченные стековые среды могут быть немного редкими; тем не менее, нужно знать об этом.

Answer 5

Вам нужно будет измерить разницу, чтобы знать наверняка. Я лично чувствую, что рекурсивная формулировка будет бить тот, у которого есть явный стек в данном конкретном случае.

Что такое нерекурсивная версия, так это то, что она устраняет вызовы. С другой стороны - в зависимости от точной реализации библиотеки - нажатие и поп также могут разрешать выполнение вызовов.

Любой приличный компилятор будет на самом деле кодировать рекурсивную функцию аналогичны следующий псевдокод:

void traverse1(node t) { 
1: 
    if(t != NULL) { 
     visit(t); 
     traverse1(t->left); 
     t = t->right; 
     goto 1; 
    } 
} 

Таким образом, устраняя один из рекурсивных вызовов. Это известно как устранение хвостового вызова.