Eugene Kirpichov (antilamer) wrote,

Внимание, задачка

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

Лучшее, что я придумал - обходить одно дерево рекурсивно, а второе в это время нерекурсивно, с помощью явного стека. Это работает примерно на 20% быстрее для деревьев высоты 10..15, нежели решение с двумя явными стеками.

Вопрос: Можно ли избавиться от явного стека совсем?

Выгода - меньше проверок выходов за границы массива при операциях со стеком. Звучит неправдоподобно, но на 20% же ускорилось от удаления одного стека :)
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 50 comments