Nano Hash - криптовалюты, майнинг, программирование

С++ AVLtree удалить узел и сбалансировать

Я пытаюсь реализовать AVL-Tree на С++. Пока вставка и балансировка дерева работают просто отлично. Алгоритм, который я пытаюсь реализовать:

шаг 1: удалить/вставить нужный узел, как в BST.

шаг 2: сбалансируйте дерево из того же курса вставки/удаления.

Я хочу разделить его на два этапа, чтобы его не было сложно читать и программировать. проблема связана с шагом 2, «вставка» работает нормально, потому что я могу просто найти в дереве существующий узел, а затем использовать рекурсию для обновления курса, через который он прошел.

но при удалении, так как узел уже удален, я не могу найти маршрут, по которому он прошел на шаге 1.

Я думал о вставке преемника, но мне не повезло, я бы очень хотел сохранить его с двумя шагами, хотя все реализации, которые я видел в Интернете, объединяли оба шага.

c++ recursion algorithm tree avl-tree
20.11.2020

  • можно просто искать в дереве существующий узел. Не делайте этого таким образом. Функция вставки знает, что она только что вставила, она должна вызвать функцию баланса и передать ей поддерево для балансировки в качестве аргумента. Точно так же функция удаления должна вызывать функцию баланса и передавать ей поддерево для балансировки в качестве аргумента. 20.11.2020

Ответы:


1

Следующее видео полезно для понимания поворотов и вставок, а также удаления из дерева AVL: "nofollow noreferrer">https://www.youtube.com/watch?v=8JkBIA9V6Nc&list=PL30dC-5PIyXljRGbjvZ-mG8OITMESqxuj&index=12

Пример: https://www.youtube.com/watch?v=LkwZggRs0t8&list=PL30dC-5PIyXljRGbjvZ-mG8OITMESqxuj&index=13

24.11.2020
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..