Форум программистов, компьютерный форум, киберфорум
Алгоритмы
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
Alvin Seville
 Аватар для Соколиный глаз
343 / 273 / 134
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 22

Пересчёт высот у AVL-деревьев в больших поворотах

23.08.2018, 16:20. Показов 1250. Ответов 8
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Местоположение X надо учитывать при большом повороте? Я имею ввиду под местоположением - либо левый, либо правый потомок B. Ведь, баланс при вращениях будет различаться (в частности после первого малого правого вращения).
Миниатюры
Пересчёт высот у AVL-деревьев в больших поворотах  
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
23.08.2018, 16:20
Ответы с готовыми решениями:

Исходник avl деревьев.
Пожалуйста помогите разобраться. Если это возможно пришлите простейщий исходник на Visual C++ на мыло. За ранее благодарен.

Отличие высот деревьев на 2
Цитата взята отсюда (стр. 29). Как это может быть вообще? В AVL-дереве же самые нижние узлы находятся примерно на одном уровне. Как может...

AVL-деревья - не вижу высоты у деревьев
Почему тут: type AVLTree = ^AVLNode; AVLNode = record key: key_type; left: AVLTree; right: AVLTree; ...

8
Alvin Seville
 Аватар для Соколиный глаз
343 / 273 / 134
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 22
23.08.2018, 16:27  [ТС]
Более полный рисунок:
Миниатюры
Пересчёт высот у AVL-деревьев в больших поворотах  
0
Модератор
Эксперт функциональных языков программирования
3136 / 2283 / 469
Регистрация: 26.03.2015
Сообщений: 8,886
23.08.2018, 17:33
От местоположения Х зависит тип поворота, который выполняется для балансировки.
0
Alvin Seville
 Аватар для Соколиный глаз
343 / 273 / 134
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 22
23.08.2018, 19:04  [ТС]
Shamil1, погодите, но разве не один ли тип поворота будет использоваться в случае, если X - слева от правого потомка A?

Добавлено через 18 минут
Но ведь в этой ситуации X может быть как под T2, так и под T3. И я не могу придумать как реализовать левый и правый повороты, чтобы они правильно перерассчитывали баланс в двух ситуациях: X под T2, X под T3.
0
Модератор
Эксперт функциональных языков программирования
3136 / 2283 / 469
Регистрация: 26.03.2015
Сообщений: 8,886
23.08.2018, 22:25
Цитата Сообщение от Соколиный глаз Посмотреть сообщение
X может быть как под T2, так и под T3
Если Х под Т2 (баланс 1), то после передачи вершине С правого поддерева её баланс будет -1.
Если Х под Т3 (баланс -1), то после передачи вершине С правого поддерева её баланс будет 0.
0
Alvin Seville
 Аватар для Соколиный глаз
343 / 273 / 134
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 22
24.08.2018, 08:27  [ТС]
Вот как делается у меня правый поворот:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
        private void RotateRight(ref AVLTreeNode<T> root)
        {
            AVLTreeNode<T> leftNode = root.left;
            root.left = leftNode.right;
            root.left.parent = root;
 
            leftNode.parent = root.parent;
 
            leftNode.right = root;
            root.parent = leftNode;
 
            root = leftNode;
 
            // тут пересчёт баланса
        }
Как написать его так (имеется ввиду как решить проблему пересчёта балансов), чтобы в большом повороте просто применять малые повороты:
C#
1
2
3
4
5
        private void RotateRightLeft(ref AVLTreeNode<T> root)
        {
            RotateRight(ref root.right);
            RotateLeft(ref root);
        }
?

Вот класс узла этого дерева:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
using System;
 
namespace MyCollections.Generic
{
    //Класс узла AVL-дерева.
    public class AVLTreeNode<T> : TreeNode<T>, IPrintable, ICloneableAs<AVLTreeNode<T>>
    {
        public new AVLTreeNode<T> left;
        public new AVLTreeNode<T> right;
        public new AVLTreeNode<T> parent;
        public int balance;
 
        public AVLTreeNode(T value = default(T), AVLTreeNode<T> left  = null, AVLTreeNode<T> right  = null, AVLTreeNode<T> parent = null)
        {
            this.value = value;
            this.left = left;
            this.right = right;
            this.parent = parent;
        }
 
        public new AVLTreeNode<T> CloneAs() => new AVLTreeNode<T>(value, left, right, parent);
 
        public override object Clone() => CloneAs();
    }
}
0
Модератор
Эксперт функциональных языков программирования
3136 / 2283 / 469
Регистрация: 26.03.2015
Сообщений: 8,886
24.08.2018, 14:14
Цитата Сообщение от Соколиный глаз Посмотреть сообщение
// тут пересчёт баланса
Берёте и пересчитываете. Новые балансы А и Б зависят только от старых балансов А и Б.

Есть три разных подхода:
1. Вывести формулы в общем виде
2. Для каждого из 9 случаев использовать элементарные формулы
3. Сразу писать код без всяких формул

Выбирайте любой и делайте.
0
Модератор
Эксперт функциональных языков программирования
3136 / 2283 / 469
Регистрация: 26.03.2015
Сообщений: 8,886
24.08.2018, 14:53
Попробовал третий способ. Получилось так:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
var balanceB = root.balance;
var balanceA = leftNode.balance;
 
// Обозначим dx = x.height - t1.height
 
// d1 = 0
 
// a.balance = t1.height - t2.height = d1 - d2
var d2 = -balanceA;
 
// a.height = (a.balance >= 0 ? t1.height : t2.height) + 1
var da = (balanceA >= 0 ? 0 : d2) + 1;
 
// b.balance = a.height - t3.height = da - d3
var d3 = da - balanceB;
 
// b1.balance = d2 - d3
var balanceB1 = d2 - d3;
 
// b1.height = (b1.balance >= 0 ? t2.height : t3.height) + 1
db1 = (balanceB1 >= 0 ? d2 : d3) + 1;
 
// a1.balance = t1.height - b1.height
var balanceA1 = -db1;
Теперь этот код нужно отладить. Лучше всего написать юнит тесты.
После отладки его можно упростить. Сначала, избавиться от переменной d2, заменив её на " -balanceA", и так далее. После каждого упрощения запускать юнит тесты. В результате получим формулу, которую мы могли бы вывести на бумаге. Код станет заметно короче (предположительно 2 строки), но читающему будет непонятно, откуда взялись эти формулы (в принципе, ничего плохого в этом нет).

Добавлено через 7 минут
p.s. Вместо тернарного оператора лучше использовать Math.Max()
1
Alvin Seville
 Аватар для Соколиный глаз
343 / 273 / 134
Регистрация: 25.07.2014
Сообщений: 4,537
Записей в блоге: 22
24.08.2018, 19:30  [ТС]
Shamil1, спасибо Вам.

Не по теме:

Очень не хватает литературы, рассматривающей данный вопрос. :)



Добавлено через 4 часа 10 минут
Shamil1, я нашёл материалы по этой теме с выводом формул - то, что мне и надо. А главное - понял наконец что и почему.
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
24.08.2018, 19:30
Помогаю со студенческими работами здесь

AVL-деревья - высота пустых деревьев
Высота пустого AVL-дерева обычно принимается за -1 или за 0?

Бинарные деревья - правый поворот (перевычисление высот деревьев)
Смотрю эту презентацию. Там есть псевдокод (страница 18): P.left = L.right L.right = P P.height = max(P.left.height, P.right.height)...

Ищу готовый код с примерами реализации деревьев (AVL, красно-черное, декартово)
Может у кого завалялась его реализация AVL дерева, красно-чёрного дерева либо декартового (treap) дерева? Было бы очень кстати, а если...

Пересчет больших чисел
Доброго времени суток вам. У меня возник вопрос по написанию программы для пересчета больших чисел. код планируется писать в Fasm. ...

C/C++ vs Objective-C для обхода больших деревьев - вопрос оптимизации
Добрый день! Появилась необходимость обрабатывать многотысячный словарь (&quot;словарь&quot; - буквально, набор слов): поиск вариантов...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Новые блоги и статьи
Программный контроль заполнения реквизита табличной части документа
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита "ПричинаСписания". . .
wmic не является внутренней или внешней командой
Maks 02.04.2026
Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/
Программная установка даты и запрет ее изменения
Maks 02.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .
Вывод данных в справочнике через динамический список
Maks 01.04.2026
Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Программное заполнения текстового поля в реквизите формы документа
Maks 01.04.2026
Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .
К слову об оптимизации
kumehtar 01.04.2026
Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .
Идея фильтра интернета (сервер = слой+фильтр).
Hrethgir 31.03.2026
Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .
Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда
anaschu 31.03.2026
В прикрепленном документе раздумья о том, как можно поменять модель в будущем
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru