Дерево почти оптимального поиска (ДОП) (приближенные алгоритмы).
- Реализовать программно алгоритмы А1 и А2 для построения почти оптимальных деревьев поиска.
- Для построенных деревьев вычислить размер, контрольную сумму и средневзвешенную высоту.
Теория:
А1-алгоритм предлагает в качестве корня использовать вершину с наибольшим весом. Затем среди оставшихся вершин снова выбирается вершина с наибольшим весом и помещается в левое или правое поддерево в зависимости от ее значения, и так далее.
А2-алгоритм использует предварительно упорядоченный набор вершин. В качестве корня выбирается такая вершина, что разность весов левого и правого поддеревьев была минимальна, для каждого из поддеревьев действия по выбору вершины повторяются. А2 более требователен к ресурсам, чем алгоритм А1.