О бинарных вращениях деревьев

Question

О бинарных вращениях деревьев

Я пытаюсь запрограммировать AVL на паскале. Я уже запрограммировал обычное двоичное дерево, и оно работает, я пытаюсь создать самобалансируемое дерево, и я столкнулся с проблемой.

У меня есть поддерево, которое я хочу повернуть, и дело в том, что я не знаю, как назначить родителя указателя корневого узла поддерева. Имеется в виду следующее дерево: корневой узел поддерева, которое я хочу повернуть = 30 родительский узел поддерева = 55

          55                                      55          
       30    60            ----->           45         60         
   10    45    75                        30   50          75       
  5  15    50    90                     10                    90
                                      5    15

как я должен изменить указатель, который идет от 55 до 30, чтобы перейти от 55 до 45? Большая часть кода, который я видел, не имеет указателя, который идет от узла к его родителю, поэтому я не знаю, как его изменить.

2

tree binary-tree pascal

Источник

user3447831 21 мар '14 в 19:24

1 ответ

Решение

Другие вопросы по тегам tree binary-tree pascal

user448932 21 мар '14 в 19:41 2014-03-21 19:41 · Accepted Answer · 2014-03-21 19:41

Вы не показываете никакого кода, но обычно вы делаете что-то вроде

Root := Root.Rebalance;

То есть, вы вызываете поддерево для перебалансировки себя, и эта функция перебалансировки возвращает корень в качестве результата. Этот результат может иметь тот же корень, что и ранее, или - как в вашем сценарии - новый корневой узел.