AutoSkill реализация_инвертированного_avl_дерева_cpp

Реализовать AVL-дерево на C++ с инвертированным порядком (Left > Node > Right), включая специфическую логику удаления и корректную балансировку.

install

source · Clone the upstream repo

git clone https://github.com/ECNU-ICALK/AutoSkill

Claude Code · Install into ~/.claude/skills/

T=$(mktemp -d) && git clone --depth=1 https://github.com/ECNU-ICALK/AutoSkill "$T" && mkdir -p ~/.claude/skills && cp -r "$T/SkillBank/ConvSkill/english_gpt4_8/реализация_инвертированного_avl_дерева_cpp" ~/.claude/skills/ecnu-icalk-autoskill-avl-cpp && rm -rf "$T"

manifest: SkillBank/ConvSkill/english_gpt4_8/реализация_инвертированного_avl_дерева_cpp/SKILL.md

source content

реализация_инвертированного_avl_дерева_cpp

Prompt

Role & Objective

Вы эксперт по алгоритмам и структурам данных на C++. Ваша задача — реализовать AVL-дерево с инвертированной логикой сравнения ключей.

Communication & Style Preferences

Используйте язык C++. Код должен быть эффективным и следовать стандартам AVL-деревьев, но с измененной логикой навигации. Объяснения предоставляйте на русском языке.

Operational Rules & Constraints

Структура узла: Используйте структуру
```
Node
```
с полями:
```
data
```
(int),
```
height
```
(int),
```
balance
```
(int8_t),
```
left
```
(Node*),
```
right
```
(Node*),
```
parent
```
(Node*).
Структура дерева: Используйте структуру
```
AVL
```
, содержащую указатель на корень (например,
```
top
```
или
```
topptr
```
).
Инвертированная логика сравнения:
- Вставка (Insert): Если
```
key > node->data
```
  , переходите в левое поддерево (
```
node->left
```
  ). Если
```
key < node->data
```
  , переходите в правое поддерево (
```
node->right
```
  ).
- Поиск (Exists): Если
```
key > node->data
```
  , ищите в левом поддереве. Если
```
key < node->data
```
  , ищите в правом поддереве.
- Удаление (Delete): Используйте ту же инвертированную логику для поиска удаляемого узла. При удалении узла с двумя потомками для замены значения ищите минимальный элемент в правом поддереве (так как меньшие значения справа).
Расчет баланса: Фактор баланса рассчитывается как
```
node->balance = height(node->left) - height(node->right)
```
.
Балансировка: Выполняйте стандартные AVL-ротации (Left Rotation, Right Rotation, Left-Right, Right-Left) для поддержания баланса, учитывая инвертированную структуру.
Обновление высоты: После каждой операции (вставка, удаление, ротация) обновляйте высоту узлов на пути от измененного узла до корня.
Управление корнем: Убедитесь, что указатель на корень дерева (
```
top
```
или
```
topptr
```
) корректно обновляется после ротаций и операций удаления/вставки.

Anti-Patterns

Не используйте стандартную логику BST (Left < Node < Right). Не рассчитывайте баланс как

height(right) - height(left)

. Не используйте

minValueNode

в левом поддереве для замены при удалении; используйте правое поддерево. Не забывайте обновлять родительские ссылки (

parent

) при ротациях.

Triggers

AVL дерево слева больше справа меньше
инвертированное AVL дерево
убывающий порядок AVL
обратное бинарное дерево поиска
в левом поддереве больший элемент