Оптимальные деревья поиска 🌳

Решение задачи построения оптимальных двоичных деревьев поиска с использованием динамического программирования.

Описание задачи

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

Элемент i выбирается с вероятностью wᵢ / S, где S — сумма всех весов.

Алгоритм решения

Используется классический алгоритм динамического программирования для задачи Optimal Binary Search Tree (OBST):

1. DP[i][j] — минимальная стоимость (сумма взвешенных глубин) для дерева, содержащего элементы от i до j
2. Оптимизация Кнута — сужение диапазона поиска корня до O(1) элементов
3. Генерация всех деревьев — рекурсивное построение всех комбинаций оптимальных корней

Сложность

• Временная: O(N²) с оптимизацией Кнута
• Пространственная: O(N²)

Структура проекта

.
├── optimal_bst.py         # Всё в одном файле (решение + тесты + CLI)
├── input_example.txt      # Пример входных данных
└── README.md              # Документация

---

🚀 Инструкция по использованию

Шаг 1: Убедитесь, что Python установлен

python --version
# Должен быть Python 3.7 или выше

Шаг 2: Перейдите в директорию проекта

cd /path/to/project

Шаг 3: Запуск

Вариант A: Запуск тестов ✅

python optimal_bst.py --test

Ожидаемый вывод:

🧪 Запуск тестов...

✅ Тест с одним элементом пройден!
✅ Тест с двумя элементами пройден!
...
✨ Все тесты пройдены успешно!

Вариант B: Демонстрация на примере 🎯

python optimal_bst.py --demo

Ожидаемый вывод:

🎯 Демонстрация на примере из условия:

Входные данные:
6
1 2 3 4 5 6

Найдено оптимальных деревьев: 1

Дерево 1: [5, 3, 2, 1, 4, 6]

Математическое ожидание числа итераций: 2.142857

Формат вывода для задачи:
1
5 3 2 1 4 6

Вариант C: Решение из файла 📁

1. Создайте файл с входными данными (например, input.txt):

6
1 2 3 4 5 6

2. Запустите:

python optimal_bst.py --file input.txt

Ожидаемый вывод:

📊 Результат:
1
5 3 2 1 4 6

Вариант D: Ввод через pipe 🔧

echo "3
10 20 30" | python optimal_bst.py

Ожидаемый вывод:

📊 Результат:
2
2 1 3
3 2 1

Вариант E: Интерактивный ввод ⌨️

python optimal_bst.py

Затем введите данные в формате:

N
w₁ w₂ ... wₙ

И нажмите:

• Ctrl+D (Linux/Mac)
• Ctrl+Z, затем Enter (Windows)

---

Формат ввода

N
w₁ w₂ ... wₙ

Где:

• N — количество элементов (1 ≤ N ≤ 800)
• wᵢ — веса элементов (1 ≤ wᵢ ≤ 1000)

Пример ввода:

6
1 2 3 4 5 6

---

Формат вывода

K
алгоритм₁
алгоритм₂
...
алгоритмₖ

Где:

• K — количество оптимальных алгоритмов (≤ 1000)
• Каждый алгоритм описан в формате pre-order обхода дерева

Формат описания дерева

Строка «3 1 2 5 4 6» описывает алгоритм:

1. Сначала проверяем элемент 3
2. Если искомое меньше → проверяем элемент 1, затем 2
3. Если искомое больше → проверяем элемент 5, затем 4 или 6

---

Примеры

Пример 1: Шесть элементов

Ввод:

6
1 2 3 4 5 6

Вывод:

1
5 3 2 1 4 6

Дерево:

        5
       / \
      3   6
     / \
    2   4
   /
  1

Математическое ожидание:

• Элемент 5: глубина 1, вес 5 → вклад 1×5 = 5
• Элемент 3: глубина 2, вес 3 → вклад 2×3 = 6
• Элемент 6: глубина 2, вес 6 → вклад 2×6 = 12
• Элемент 2: глубина 3, вес 2 → вклад 3×2 = 6
• Элемент 4: глубина 3, вес 4 → вклад 3×4 = 12
• Элемент 1: глубина 4, вес 1 → вклад 4×1 = 4

Итого: (5 + 6 + 12 + 6 + 12 + 4) / 21 = 45/21 ≈ 2.143 итерации

---

Пример 2: Три элемента

Ввод:

3
10 20 30

Вывод:

2
2 1 3
3 2 1

Здесь найдено 2 оптимальных дерева с одинаковой минимальной стоимостью.

---

Пример 3: Равные веса

Ввод:

4
1 1 1 1

Вывод:

4
2 1 3 4
2 1 4 3
3 1 2 4
3 2 1 4

При равных весах существует несколько оптимальных деревьев.

---

🔧 Устранение неполадок

Ошибка: python: command not found

Используйте python3 вместо python:

python3 optimal_bst.py --test

Ошибка чтения файла

Убедитесь, что файл существует и имеет правильный формат:

cat input_example.txt
# Должно быть:
# 6
# 1 2 3 4 5 6

---

📚 Дополнительная информация

Что такое оптимальное дерево поиска?

Оптимальное бинарное дерево поиска — это дерево, которое минимизирует среднее время поиска элемента с учетом вероятностей обращения к каждому элементу.

Зачем нужна оптимизация Кнута?

Без оптимизации алгоритм работает за O(N³). Оптимизация Кнута позволяет сузить диапазон поиска оптимального корня, что ускоряет алгоритм до O(N²).

Ограничения

• Максимальное количество элементов: N ≤ 800
• Максимальное количество выводимых деревьев: 1000
• Веса элементов: от 1 до 1000

---

Лицензия

Проект предоставлен для образовательных целей.