C ++ AVL Tree - Как восстановить порядок ввода узлов с использованием только предварительного и последующего порядка

Для своего проекта в университете я реализую класс дерева AVL на C ++ с символами для значений. У нас есть автогрейдер, который указывает на наши ошибки случайными тестами, если они есть. Я запускал его несколько раз, довольно много, и не получил ошибок, что означает, что он должен иметь нормальную логику. Однако иногда я получал сообщение об ошибке, в котором говорилось, что мои предварительные и последующие обходы неверны. Это одна из фактических ошибок, которые я получил:

YOUR PREORDER: "IECABDGFHPLKOUSRYX", YOUR POSTORDER: "BADCFHGEKOLRSXYUPI" 
CORRECT PREORDER: "ECABDOIGFHKLURPSYX", CORRECT POSTORDER: "BADCFHGLKIPSRXYUOE"

Да, эти деревья еще сбалансированы, но как-то неправильно сложены. Как мне отладить это? У меня есть функция, которая может восстанавливать деревья с использованием предварительного и последующего порядка, но я думаю, что порядок размещения переменных имеет значение. В противном случае у меня нет возможности узнать порядок ввода узлов и где мой алгоритм пошел не так.


c++ avl-tree postorder preorder
person F. Kukec    schedule 22.10.2020    source источник

Ответы (2)


arrow_upward
2
arrow_downward

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

если они не совпадают, он печатает случайную строку и два заказа. Это должно помочь вам найти неудачные тестовые случаи для предварительного заказа.

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

Google Fuzzer для других идей :)

person EvilTeach    schedule 22.10.2020

arrow_upward
0
arrow_downward

Очевидно, было бы лучше, если бы, учитывая результаты теста, вы могли проанализировать свой код и выяснить, что вызывает проблему.

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

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

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

Повторите этот процесс, используя настоящую функцию предварительного заказа и заменяя постзаказ фиктивным методом.

person idz    schedule 22.10.2020