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

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

Восстановить пароль Регистрация
 
Gudsaf
103 / 14 / 3
Регистрация: 29.11.2010
Сообщений: 325
26.11.2014, 16:35     Теряю ссылку на сына в узле дерева #1
Привет, продолжаю нашествие на форум.. сегодня столкнулся с интересным приёмом в 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++ TreeView данные об узле (WINAPI)
Теряю значение переменной char* C++
C++ Функция - принять ссылку вернуть ссылку
C++ Удалить из бинарного дерева всех отцов, имеющих одного сына
C++ Как сделать односвязный список в узле дерева
C++ Теряю ссылку на элемент в std::vector после того, как делаю push_back следующего элемента
C++ Теряю значение private члена класса
Однонаправленный связный список с полями данных в самом узле списка C++

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

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

Текущее время: 00:12. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru