Тестирование софта - статьи


         

Обход дерева


Сравним эффективность обходчиков при обходе полного бинарного дерева высотой N, с операциями «опуститься на уровень ниже влево», «опуститься на уровень ниже вправо» и «подняться на уровень выше».

Теоретическая оценка длины обхода снизу равна количеству дуг 2N+2-4. Эта оценка может быть достигнута, например, при обходе в симметричном порядке [].

В Таблице 2 приведены длины обходов и время их выполнения для разных обходчиков.

N dfsm, длина dfsm, время ndfsm, длина ndfsm, время мин. длина
9 4088 6 2044 3 2044
10 8184 25 4092 12 4092
11 16376 100 8188 45 8188
12 32760 427 16380 19016380

Таблица 2. Длина и время обхода дерева для разных N.

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

Содержание  Назад  Вперед