Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Gudsaf
103 / 14 / 3
Регистрация: 29.11.2010
Сообщений: 327
#1

Теряю ссылку на сына в узле дерева - C++

26.11.2014, 16:35. Просмотров 177. Ответов 0
Метки нет (Все метки)

Привет, продолжаю нашествие на форум.. сегодня столкнулся с интересным приёмом в C#.
C#
1
2
3
4
5
6
7
8
9
10
11
private void Skew(ref Node node)
        {
                if (node.level == node.left.level)
                {
                        // rotate right
                        Node left = node.left;
                        node.left = left.right;
                        left.right = node;
                        node = left;
                }
        }
Данный код делает балансировку в АА дереве (один из случаев балансировки). Функция принимает значение узла который надо проверить, проверяет, если надо балансирует. При балансировке создаётся новый узел, потом к этому новому узлу прикрепляется всё что должно прикрепиться. Но есть одна проблема - отец перебалансированного узла не в курсе, что его сына заменили на нового (Node left) и в последующих вызовах выдаст неверную информацию. Как я понял эту проблему решает модификатор ref благодаря ему, отец тоже меняет ссылку на сына и всё становится прекрасно.

Но я пишу на C++, и думаю как организовать смену адреса у отца.. дело в том, что сыновья не ссылаются на своих предков - только лишь на своих сыновей. Пока есть одна идея как решить данную проблему - ввести дополнительное поле parent в класс Node.

Есть какие-нибудь оригинальные идеи?

Вот код автора на которого я пытаюсь равняться _http://demakov.com/snippets/aatree.cs
Так же пытаюсь что-то сделать в направления возвращаемых значений функции, но пока фигня получается:
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
Tree::Node *skew(Node *thisNode)
    {
        if (thisNode->left->_level == thisNode->_level)
        {   //сделать поворот вправо
            Node *left = new Node;
            
            //временный узел = левому узлу корня
            left = thisNode->left;
            //на место левого узла корня ставим правого сына
            thisNode->left = left->right;
            //временный узел становится вторым корнем, присоединяем к нему справа бывший корень
            left->right = thisNode;
            //ставим уровень нового корня в единицу
            left->_level = 1;
            //заменяем старый корень дерева новым корнем
            //*thisNode = *left;
            
            /*
            тут мы стабильно просераем связи от корня,
            чтобы не просрать связи будем возвращать адрес на новое поддерево и потом припиливать к отцу
            */
 
            return left;
        }
    }
изначально делал так: но так я грубо теряю связи отцов с сыновьями
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
    void skew(Node *thisNode)
    {
        if (thisNode->left->_level == thisNode->_level)
        {   //сделать поворот в право
            Node *left = new Node;
 
            //временный узел = левому узлу корня
            left = thisNode->left;
            //на место левого узла корня ставим правого сына
            thisNode->left = left->right;
            //временный узел становится вторым корнем, присоединяем к нему справа бывший корень
            left->right = thisNode;
            //ставим уровень нового корня в единицу
            left->_level = 1;
            //заменяем старый корень дерева новым корнем
            *thisNode = *left;
}}
Добавлено через 1 час 43 минуты
Решил проблему методом 2ух новых переменных: да, код в стиле барокко, но всё же
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    void skew(Node *thisNode)
    {
        if (thisNode->left->_level == thisNode->_level)
        {   //сделать поворот в право
 
            //обменять местами левого сына и отца
            Node *oldRoot = new Node;
            // скопировать в oldRoot содержимое бывшего корня thisNode
            *oldRoot = *thisNode;
            // на место бывшего корня вставить его прошлого левого сына
            *thisNode = *oldRoot->left;
 
            Node *tmpRightSone = new Node;
            // скопировать правого сына нового корня (бывшего левого сына)
            *tmpRightSone = *thisNode->right;
 
            //восстановить связи
            // на место правого сына нового корня вставить сам бывший корень
            thisNode->right = oldRoot;
            // сделать левым сыном прошлого корня правого сына новго корня
            *oldRoot->left = *tmpRightSone;
        }
    }
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2014, 16:35     Теряю ссылку на сына в узле дерева
Посмотрите здесь:

Удалить из бинарного дерева всех отцов, имеющих одного сына - C++
Написала класс по работе с бинарным деревом. Помогите, пожалуйста, написать функцию по удалению из дерева всех однодетных отцов. Сижу уже...

Теряю ссылку на элемент в std::vector после того, как делаю push_back следующего элемента - C++
Добрый день! Подскажите пожалуйста в чем причина моей ошибки. Сам работал на чистом C++, то есть использовал все по минимуму из C++. В...

Как сделать односвязный список в узле дерева - C++
Ребят подскажите, пожалуйста, как сделать односвязный список в узле дерева? Нужно написать программу учета нарушений ПДД. Для каждого...

Теряю значение переменной char* - C++
Не пойму почему так. В заголовочнике прописано private: char *lastfilename; В одной функции присваиваю ей имя последнего...

Теряю значение private члена класса - C++
#include "Node.h" template <class _Compare, typename K, typename V> class My_Tree { public: My_Tree(){}; My_Tree(K key, V...

TreeView данные об узле (WINAPI) - C++
Доброго времени суток :) Существует ли возможность для узлов в TreeView хранить больше информации об элементе, чем одно название? ...

Однонаправленный связный список с полями данных в самом узле списка - C++
Добрый день! Правильно я поняла, что однонаправленный связный список с полями данных в самом узле списка выглядит так: struct robot //...

Функция - принять ссылку вернуть ссылку - C++
В одной из тем я интересовался записью типа int & fun (int rhs), что она значит и что именно в ней делает символ &, как я понял, программа...

Ссылка на ссылку - C++
Можно ли говорить, что t это ссылка на ссылку? int y=2; int &q=y; int& t = q;

Указатель на ссылку - C++
Чем отличается указатель от указателя на ссылку??


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru