Как генерировать случайные скобочные последовательности
Привет, Хабр! При тестировании алгоритмов у меня часто возникает задача сгенерировать случайное бинарное дерево. Причем хотелка сводится не к абы какому случайному дереву, а взятому из равномерного распределения. Не смотря на кажущуюся простоту, эффективно построить такое дерево совсем нетривиально. В названии этой статьи присутствуют слова «скобочная последовательность». За этими словами скрывается нечто большее, поскольку с помощью скобок можно описать очень разнообразные объекты, в том числе и бинарные деревья. На Хабре этому факту был посвящен отдельный пост. В этой статье я расскажу несколько способов генерирования случайной скобочной последовательности, в том числе за линейное время, а потом приведу пример преобразования последовательности в бинарное дерево. Интересно? Добро пожаловать под кат
