Как я могу вращать узлы в Splay Tree?

Question

Код у меня есть

private Node rotateLeftChild(Node n)
{
    Node o = n.left;
    n.left = o.right;
    o.right = n;
    return o;
}

Когда я вызываю это, чтобы повернуть дерево, как это в корне:

             7
            / \
           4   8
          / \   
         1   5

он удаляет 4 и 1 и делает 5 левым корнем из 7. Я пытался сделать метод пустым, но, похоже, он тоже не работает. Я пойду на это совершенно неправильно?

Answer 1

Как первый, извините за мой английский.

Ответ на вопрос - почему узел 4 исчезает просто. 7 имеют родительский узел (или 7 является корневым). Когда вы вызываете rotateLeftChild, родитель 7 все еще "думает", что его ребенку 7, а не 4:

Итак, есть древовидные решения:

1. Сделайте ссылку на родительский узел и обновите ее. В конце leftRotation сделайте присваивание, n.Parent.Left = o или n.Parent.Right = o (если (n.Parent.Left == n) или (n.Parent.Right == n) соответственно). Конечно, вы должны обновить ссылки на корень дерева, когда вы поворачиваете дочерний корень.

2. Когда вы добавляете | вставка | найти узел, сохранить все предыдущие (родительские) узлы в стеке, а затем после ротации необходимо обновить ссылки на их дочерние элементы. Или используйте рекурсию так:

   private Splay(Node parent, Node cur, Node n, bool canMoveUpTwice = false) {
       if (cur.Value > n.Value)
           Splay(cur, cur.Left, n, !canMoveUpTwice);
       else
           Splay(cur, cur.Right, n, !canMoveUpTwice);
   
       if (canMoveUpTwice)
           MoveUpTwice();
       else
           MoveUpOnce();
   
       if (parent.Left == cur)
           parent.Left = n;
       else
           parent.Right = n;
   
       if (Parent == null)
           tree.Root = n;
   }
   

   Как пользоваться. После добавления узла вы должны запустить Splay(root, newNode). Будьте уверены, вы получите переполнение стека.

3. Вы должны поменять местами значения узлов, а затем подумать, что узлы поменялись местами. В стандартной реализации ротации у нас есть такая картина: В ротации со свопами мы получаем это (=x означает "узел имеет значение X"):Итак, у нас есть этот код

   private rotateLeftChild(Node q) {
       Node p = q.Left;
   
       Swap(q.Value, p.Value); 
   
       A = p.Left;
       B = p.Right;
       C = q.Right;
   
       q.Left  = A;
       q.Right = p;
   
       p.Left  = B;
       p.Right = C;
   }
   

Будьте осторожны: код не был протестирован.