AutoSkill inverted_avl_tree_cpp

Реализация AVL-дерева на C++ с инвертированной логикой хранения (Left > Node > Right) и стандартным фактором баланса (Left - 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_GLM4.7/inverted_avl_tree_cpp" ~/.claude/skills/ecnu-icalk-autoskill-inverted-avl-tree-cpp && rm -rf "$T"

manifest: SkillBank/ConvSkill/english_gpt4_8_GLM4.7/inverted_avl_tree_cpp/SKILL.md

source content

inverted_avl_tree_cpp

Prompt

Role & Objective

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

Operational Rules & Constraints

Структура узла (Node):
- Поля:
```
long data
```
  ,
```
long height
```
  ,
```
long balance
```
  ,
```
Node* left
```
  ,
```
Node* right
```
  ,
```
Node* parent
```
  .
- Инициализируй высоту нового узла как 1.
Логика хранения (Инверсия):
- В левом поддереве должны храниться элементы строго больше значения текущего узла (
```
node->data
```
  ).
- В правом поддереве должны храниться элементы строго меньше значения текущего узла.
Расчет высоты (height):
- Если узел
```
nullptr
```
  , возвращай 0.
- Иначе возвращай
```
node->height
```
  .
Расчет баланса (Balance):
- Формула:
```
height(node->left) - height(node->right)
```
  .
- Это строгое требование.
Вставка (Insert):
- Если
```
key > node->data
```
  , рекурсивно вставляй в левое поддерево.
- Если
```
key < node->data
```
  , рекурсивно вставляй в правое поддерево.
- Если значение уже существует, верни указатель на текущий узел (игнорируй дубликаты).
- После вставки обнови высоту и баланс текущего узла.
- Выполни необходимые вращения для балансировки, если
```
abs(balance) > 1
```
  .
- Возвращай новый корень поддерева.
Поиск преемника (minValueNode):
- При удалении узла с двумя потомками, преемником является минимальный элемент в правом поддереве.
- Функция должна проходить по правым указателям (
```
current->right
```
  ), чтобы найти самый "глубокий" (минимальный) элемент в правом поддереве.
Удаление (Delete):
- Рекурсивно ищи узел с ключом
```
key
```
  (с учетом инвертированной логики поиска).
- Если узел не найден, верни исходный корень (изменений нет).
- Если узел найден:
  - Если у узла 0 или 1 ребенок: удали узел, обнови связи родителя, освободи память.
  - Если у узла 2 ребенка:
    - Найди преемника с помощью логики из пункта 6 (минимум в правом поддереве).
    - Скопируй данные (
```
data
```
      ) из преемника в удаляемый узел.
    - Рекурсивно удали преемник из правого поддерева.
- После удаления (если дерево не пустое) обнови высоту узлов на пути обратного хода и выполни балансировку.
- Верни новый корень поддерева.
Проверка существования (Exists):
- Логика поиска должна соответствовать логике вставки:
```
key > node->data
```
  ищи влево,
```
key < node->data
```
  ищи вправо.
- Верни
```
true
```
  , если узел найден, иначе
```
false
```
  .
Ввод/Вывод (main):
- Считай количество операций
```
n
```
  .
- В цикле обрабатывай команды:
  - ```
  A x
```
  : Вызови
```
  Insert
```
  . Выведи баланс корня. Если дерево пустое, выведи 0.
- ```
D x
```
    : Вызови
```
Delete
```
    . Важно: Если узел не был найден и удален, НЕ выводи ничего. Если удаление прошло успешно, выведи баланс корня.
  - ```
  C x
```
  : Вызови
```
  Exists
```
  . Выведи 'Y', если true, иначе 'N'.

Anti-Patterns

НЕ используй
```
malloc
```
/free
```
. Используй 
```
new
```
и
```
delete`.
НЕ используй стандартную логику AVL (Left < Node < Right).
НЕ меняй формулу баланса на
```
right - left
```
. Используй строго
```
left - right
```
.
НЕ ищи преемника в левом поддереве при удалении.
Не копируй узлы целиком (
```
*node = *temp
```
) при удалении, так как это нарушает связи родительских указателей (копируйте только
```
data
```
).

Triggers

реализовать инвертированное AVL дерево
AVL дерево левое больше правого
инвертированная логика AVL C++
AVL tree inverted storage
кастомный баланс AVL left right