Указатели в AVL Tree Rotation

Мне трудно понять, почему работает приведенный ниже код вращения дерева. Если T2 указывает на y.left, а y.left указывает на x, не делает ли это последнее присваивание x.right = T2 равным x.right = x? Разве указатель не должен указывать на начальный T2?

Node leftRotate(Node x) {
    Node y = x.right;
    Node T2 = y.left;

    // Perform rotation
    y.left = x;
    x.right = T2;

    //  Update heights
    x.height = max(height(x.left), height(x.right)) + 1;
    y.height = max(height(y.left), height(y.right)) + 1;

    // Return new root
    return y;
}

java avl-tree tree-rotation
person Marc Tim Thiemann    schedule 31.05.2017    source источник

Ответы (2)


arrow_upward
0
arrow_downward 

Node T2 = y.left;

Эта строка заставляет T2 указывать на то же место, на которое указывал y.left во время выполнения этой строки. Если y.left обновляется, чтобы указывать на другой объект — в данном случае x — это изменение не отражено в T2.

Имейте в виду, что если кто-то изменил свойство этого объекта, это изменение будет отражено. Например. код

Node T2 = y.left;
y.left.foo = bar;

тогда T2.foo отразит изменение на bar. Изменения в том, на что y.left ссылается, не отражены. Это довольно универсальная вещь в Java, связанная со всем, что "ссылки передаются по значению".

person Louis Wasserman    schedule 31.05.2017

arrow_upward
0
arrow_downward

Лучший способ аргументировать это — нарисовать это и пройтись по ним шаг за шагом:

В начале функции у нас Node x:

   x
  /  \
 L    R
     /   \
    l1    r1

Теперь мы говорим у = R.

  R
 /  \
L1   R1

Узел T2 = R.Left, который равен l2

Затем поворот:

у.слева (R1.слева) = х

     R
   /   \
  x      R1
 / \
l   R
   /  \
  l1    r1

х.справа = T2 (l1)

    R
   /  \
  x    r1
 / \
l   l1

Отличный ресурс, который я нашел для всех попыток (хотя и на C), это вечно запутанный

person Community    schedule 31.05.2017