обмен узлами в двоичном дереве

Question

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

Вот класс с своп способом:

class Node 
{ 
    public int value; 
    public Node parent { get; set; } 
    public Node left { get; set; } 
    public Node right { get; set; } 

    public Node addLeft(int value) 
    { 
     this.left = new Node(value); 
     this.left.parent = this; 
     this.left.left = null; 
     this.left.right = null; 
     return this.left; 
    } 

    public Node addRight(int value) 
    { 
     this.right = new Node(value); 
     this.right.parent = this; 
     this.right.left = null; 
     this.right.right = null; 
     return this.right; 
    } 

    public Node(int value) 
    { 
     this.value = value; 
     this.parent = null; 
     this.left = null; 
     this.right = null; 
    } 

    public Node getRoot() 
    { 
     Node n = this; 
     while(n.parent!=null) 
     { 
      n = n.parent; 
     } 
     return n; 
    } 

    public static void swap(ref Node n1,ref Node n2) 
    { 
     //updating references of n1 and n2 parents 
     if(n1.Equals(n1.parent.left)) //n1 is a left child 
     { 
      n1.parent.left = n2; 
     } 
     else if(n1.Equals(n1.parent.right)) //n1 is a right child 
     { 
      n1.parent.right = n2; 
     } 
     else 
     { 
      throw new Exception("Something is wrong"); 
     } 
     if (n2.Equals(n2.parent.left)) //n2 is a left child 
     { 
      n2.parent.left = n1; 
     } 
     else if (n2.Equals(n2.parent.right)) //n2 is a right child 
     { 
      n2.parent.right = n1; 
     } 
     else 
     { 
      throw new Exception("Something is wrong"); 
     } 
     //updating references of n1 and n2 childs 
     if(n1.left != null) 
     { 
      n1.left.parent = n2; 
     } 
     if (n1.right != null) 
     { 
      n1.right.parent = n2; 
     } 
     if (n2.left != null) 
     { 
      n2.left.parent = n1; 
     } 
     if (n2.right != null) 
     { 
      n2.right.parent = n1; 
     } 
     //Swapping n1 and n2 references 
     Node t_p = n1.parent; 
     Node t_l = n1.left; 
     Node t_r = n1.right; 
     n1.parent = n2.parent; 
     n1.left = n2.left; 
     n1.right = n2.right; 
     n2.parent = t_p; 
     n2.left = t_l; 
     n2.right = t_r; 

    } 
} 

---

А вот мой главная функция:

static void Main(string[] args) 
    { 
     Node root = new Node(10); 
     Node a = root.addLeft(1); 
     Node b = root.addRight(2); 
     Node c = a.addLeft(3); 
     Node d = a.addRight(4); 
     Node e = b.addLeft(5); 
     Node f = b.addRight(6); 
     Node g = d.addLeft(7); 
     Node h = d.addRight(8); 
     Node.swap(ref a,ref d); 
     Console.WriteLine("Value is: " + root.left.value); 
     Console.WriteLine("Value is: " + root.left.right.value); 
     Console.WriteLine("Root: " + a.getRoot().value); 
     Console.WriteLine("Root: " + d.getRoot().value); 
     Console.Read(); 
    } 

---

Выход код выше:

Value is: 4 
Value is: 1 

Он висит после второго Console.WriteLine, и я не понимаю, почему. Не могли бы вы рассказать мне, что я делаю неправильно?

---

EDIT:

И если я пытаюсь поменять местами узлы несколько раз, «Что-то» исключение.

Answer 1

while (n.parent != null) 

Это условие никогда не выполняется, поэтому вы застреваете в цикле while.

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

Вот состояние дерева, прежде чем мы начнем замены

   ((Root(10)) 
      /   \ 
      a(1)   b(2) 
     / \  / \ 
     c(3) d(4) e(5) f(6) 
      / \ 
      g(7) h(8) 

Если поменять только дочерние узлы для & д, вы в конечном итоге с круговой ссылкой для родителей.

Что-то еще подобное для вашего метода подкачки должно работать. Я оставил эту подробность ради ясности.

public static void swap(ref Node A, ref Node B) 
    { 
     var newA = new Node(B.value); 
     var newB = new Node(A.value); 

     newA.left = A.left; 
     newA.right = A.right; 
     newA.parent = A.parent; 

     newB.left = B.left; 
     newB.right = B.right; 
     newB.parent = B.parent; 

     // Fix up parent node for A 
     if (A.parent.left == A) 
     { 
      // A is a left node 
      A.parent.left = newA; 
     } 
     if (A.parent.right == A) 
     { 
      // A is a Right node 
      A.parent.right = newA; 
     } 

     // Fix up parent node for B 
     if (B.parent.left == B) 
     { 
      // B is a left node 
      B.parent.left = newB; 
     } 
     if (B.parent.right == B) 
     { 
      // B is a right node 
      B.parent.right = newB; 
     } 


     if (newA.right == B) 
     { 
      // If B was a right child of A, update reference to newB 
      newA.right = newB; 
     } 
     if (newA.left == A) 
     { 
      // If B was a left child of A, update reference to newB 
      newA.left = newB; 
     } 

     if (newB.right == A) 
     { 
      // If A was a right child of B, update reference to newA 
      newB.right = newA; 
     } 
     if (newB.left == A) 
     { 
      // If A was a left child of B, update reference to newA 
      newA.left = newB; 
     } 

     // Update child references to be orphaned to point to new parents for A 
     A.left.parent = newA; 
     A.right.parent = newA; 

     // Update child references to be orphaned to point to new parents for A 
     B.left.parent = newB; 
     B.right.parent = newB; 

     // Final Swap to update ref types 
     A = newA; 
     B = newB; 

    } 

желательное состояние после обмена

  ((Root(10)) 
     /   \ 
     d(4)   b(2) 
    / \  / \ 
    c(3) a(1) e(5) f(6) 
     / \ 
     g(7) h(8) 

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

static void Main(string[] args) 
    { 
     var root = new Node(10); 
     var a = root.addLeft(1); 
     var b = root.addRight(2); 
     var c = a.addLeft(3); 
     var d = a.addRight(4); 
     var e = b.addLeft(5); 
     var f = b.addRight(6); 
     var g = d.addLeft(7); 
     var h = d.addRight(8); 
     Node.swap(ref a, ref d); 

     if (root.left.value != 4) 
      throw new ApplicationException("New Root --> left --> value != 4 as expected"); 
     Console.WriteLine("New root --> left node has correct value of 4"); 

     if ((root.left.right.parent != root.left)) 
      throw new Exception("and root --> left --> right has incorrect parent"); 
     Console.WriteLine("Root --> left --> right has the correct parent"); 

     if (root.left.right.value != 1) 
      throw new ApplicationException("New Root --> left --> right --> value did not equal 1."); 
     Console.WriteLine("New Root --> Left --> right has the correct value of 1"); 

     if (root.left.right.left.value != 7) 
      throw new ApplicationException("New Root --> left --> right --> left --> value was not 7 as expected."); 
     Console.WriteLine("New Root --> left --> right --> left.value had a value of 7 as expected"); 

     if (root.left.right.left.parent != root.left.right) 
      throw new ApplicationException("New Root --> left --> right --> left --> parent was not root --> left --> right as expected"); 
     Console.WriteLine("New Root --> Left --> right --> left has the correct value of 7 and expected parent"); 


     Console.Read(); 
    } 

Answer 2

Если я понять, что ваша функция подкачки должен делать, это должно быть так же просто, как это:

public static void swap(Node n1, Node n2) 
    { 
     Node left1 = n1.left; 
     Node left2 = n2.left; 
     Node right1 = n1.right; 
     Node right2 = n2.right; 
     Node parent1 = n1.parent; 
     Node parent2 = n2.parent; 

     n1.left = left2; 
     n2.left = left1; 

     n1.right = right2; 
     n2.right = right1; 

     n1.parent = parent2; 
     n2.parent = parent1; 
    } 

То, что я думаю, что вам нужно сделать, это просто замена n1 слева и справа с п2 х Лево и право. Нет необходимости в ref, так как это ссылочный тип, а не тип значения.

Answer 3

Пожалуйста, обратите внимание на следующую строку:

if (n1.right != null) 
{ 
    n1.right.parent = n2; 
} 

Если n2 является правильным потомком n1, так как в этом случае, n1.right является n2, так n1.right.parent = n2 на самом деле n2.parent = n2, который вызывает цикл.

Чтобы решить эту проблему, вам нужно либо сделать копии узлов, либо заменить их, либо попытаться выполнить оба обмена атомарно и независимо.