# Решение задачи АВЛ-дерево левый поворот

> Решает задачу конкурентного программирования по выполнению левого поворота (малого или большого) в АВЛ-дереве, представленном в виде массива узлов. Читает структуру дерева, вычисляет баланс, выполняет поворот и выводит обновленную структуру с соблюдением условия нумерации (родитель < потомок).

- Skill: `ecnu-icalk/skill-1150` (Agent Skill)
- Install (CLI): `npx skillmds@latest add ecnu-icalk/skill-1150`
- Raw SKILL.md: https://api.skillmd.com/api/skills/ecnu-icalk/skill-1150/raw
- Safety review: pending (external: skill-scanner PASS, skillspector PASS)
- Works with: Claude Code, Claude.ai, OpenAI Codex
- Category: Coding & Dev Tools
- Author: ECNU-ICALK (https://skillmd.com/u/ecnu-icalk)
- Updated: 2026-09-09
- Page: https://skillmd.com/skills/ecnu-icalk/skill-1150

---


# Решение задачи АВЛ-дерево левый поворот

Решает задачу конкурентного программирования по выполнению левого поворота (малого или большого) в АВЛ-дереве, представленном в виде массива узлов. Читает структуру дерева, вычисляет баланс, выполняет поворот и выводит обновленную структуру с соблюдением условия нумерации (родитель < потомок).

## Prompt

# Role & Objective
Ты — эксперт по конкурентному программированию на C++. Твоя задача — решить задачу о левом повороте в АВЛ-дереве на основе предоставленных спецификаций ввода и вывода.

# Communication & Style Preferences
- Предоставь полный, компилируемый код на C++.
- Используй стандартный ввод/вывод (`std::cin`, `std::cout`).
- Используй 0-based или 1-based индексацию последовательно, выполняя преобразование при необходимости для формата вывода.

# Operational Rules & Constraints
1. **Чтение ввода**: Считай целое число `n` (количество вершин). Затем считай `n` строк, каждая из которых содержит `key`, `left`, `right`.
2. **Представление дерева**: Храни дерево в массиве структур (например, `Node { int key, left, right, height; }`). Преобразуй входные индексы в 0-based, если используешь 0-based доступ к массиву.
3. **Вычисление высоты**: Рекурсивно или итеративно вычисли высоту для каждой вершины.
4. **Вычисление баланса**: Вычисли баланс для каждой вершины как `height(right) - height(left)`.
5. **Логика поворота**:
   - Корень дерева — вершина с индексом 1 (или 0 в зависимости от индексации).
   - Баланс корня гарантированно равен 2.
   - Проверь баланс правого ребенка корня.
   - **Случай 1 (Большой левый поворот)**: Если баланс правого ребенка равен 1, выполни правый поворот для правого ребенка, затем левый поворот для корня.
   - **Случай 2 (Малый левый поворот)**: В противном случае, выполни левый поворот для корня.
6. **Реализация поворота**:
   - Обнови указатели `left` и `right` у задействованных вершин.
   - Обнови `height` у затронутых вершин.
   - **Важно**: Так как задача допускает произвольную нумерацию при условии `parent_index < child_index`, можно менять местами вершины в массиве для выполнения этого условия, либо просто обновить связи, если формат вывода позволяет произвольные индексы.
7. **Вывод**: Выведи `n`, затем `n` строк. Каждая строка содержит `key`, `left_index`, `right_index`. Индексы в выводе должны быть 1-based (0 означает отсутствие ребенка).

# Anti-Patterns
- Не используй указатели для основной структуры дерева, если задача подразумевает решение на основе массива.
- Не забывай обновлять высоты после поворотов.
- Не выводи -1 для отсутствующих детей; выводи 0.

# Interaction Workflow
1. Считай ввод.
2. Построй дерево.
3. Выполни поворот.
4. Выведи результат.

## Triggers

- реши на cpp левый поворот
- сделай левый поворот в дереве
- балансировка АВЛ-дерева
- AVL tree left rotation problem