Как вращать treap или AVL-дерево?

Извините, что снова беспокою вас, ребята, но у меня есть вопрос, и я не могу решить его самостоятельно в течение нескольких дней. Речь идет о вращении треапа, например, чтобы повернуть треап вправо в точке pos. Вопрос заключается в том, как связать (или соединить) pos->left с pos оригинальным родителем? Я нашел этот код в интернете, который работает, но я не видел, как он решает мой вопрос, это из-за использования *&? Если да, то не могли бы вы помочь мне немного объяснить это? А какова функция pos=b это код?

void Treap::right_rotate(Node *&pos) {
    Node *b   = pos->left; 
    pos->left = b->right;
    b->right  = pos;
    pos       = b;
}

Заранее спасибо!!

1 3
c++ algorithm data-structures avl-tree

1 ответ:

Хитрая часть-это действительно часть *&. Это объявляет его как ссылку на указатель (вот ссылка или два на некоторый аналогичный пример кода, но я боюсь, что они могут быть более запутанными, чем полезными).

Изменяя узел, на который указывает указатель с помощью pos = b, Вы можете поменять содержимое на другой узел, не зная родителя. Исходная ссылка обновляется, чтобы стать новым повернутым узлом.

Вот схема на всякий случай, если вам нужно немного перебор того, как выглядит вращение (хотя это звучит так, как будто вы понимаете эту часть).

Начальное условие: 

Node *&pos; 

         |
        [P]
      /     \
     L       R
    / \     / \ 
   w   x   y   z

Затем вы сохраняете левого ребенка, так как вы собираетесь перезаписать его, насколько это касается П.

Node *b = pos->left;
pos->left = b->right;

           |
    L     [P]
  /  \   /   \
 w     x      R
             / \ 
            y   z

Теперь мы заканчиваем вращение, так как поскольку L плавает в пространстве, нарушая правильную структуру дерева: 

b->right = pos;

        L     
      /  \ |
     w    [P]
         /   \
        x     R
             / \ 
            y   z

Затем мы завершаем обслуживание, обновляя ссылку на указатель узла, чтобы стать новым узлом, который заменяет содержимое это место в памяти: 

pos = b;

       |
      [L]     
     /   \
    w      P
         /   \
        x     R
             / \ 
            y   z

На кого раньше указывали pos (pos's original parent) теперь указывает на то же самое место в памяти,но это значение теперь заменено дочерним, которое было повернуто.

7