1

リンク

public Node merge(Node x, Node y) {
  if(x == null)
    return y;
  if(y == null) 
    return x;

  // if this was a max height biased leftist tree, then the 
  // next line would be: if(x.element < y.element)
  if(x.element.compareTo(y.element) > 0) {  
    // x.element > y.element
    Node temp = x;
    x = y;
    y = temp;
  }

  x.rightChild = merge(x.rightChild, y);

  if(x.leftChild == null) {
    // left child doesn't exist, so move right child to the left side
    x.leftChild = x.rightChild;
    x.rightChild = null;
    x.s = 1;
  } else {
    // left child does exist, so compare s-values
    if(x.leftChild.s < x.rightChild.s) {
      Node temp = x.leftChild;
      x.leftChild = x.rightChild;
      x.rightChild = temp;
    }
    // since we know the right child has the lower s-value, we can just
    // add one to its s-value
    x.s = x.rightChild.s + 1;
  }
  return x;
}

私がこの質問をする理由は次のとおりです。

  if(x.element.compareTo(y.element) > 0) {  
    // x.element > y.element
    Node temp = x;
    x = y;
    y = temp;
  }

参照はメソッド内でのみ切り替えられるため、これは機能しませんか？

4

2 に答える 2

1

メソッド内で後で実行するために、それらを切り替えています。スイッチはメソッドの外部で参照を直接変更しませんが、コード内のロジックのパスが 1 つだけであるようにチェックが行われ、小さい値の要素は常に x ノードにあるため、後でコード内でそれらが交換されます。正しい要素で動作します。

具体的な例として、次のコード行を見てください。

x.rightChild = merge(x.rightChild, y);

2 つのうち小さい方 (x または y) は、その下でマージされ、右側の子で、2 つのうち大きい方がマージされます。したがって、これにより、メソッド自体が順序を気にすることができ、2 つの要素を任意の順序で追加できるため、正しい動作が発生します。

お役に立てれば。

于 2010-05-06T20:48:25.370 に答える
0

参照はメソッド内でのみ切り替えられるため、それは機能しませんか?

メソッドの残りの部分は切り替えられた参照で動作するため、切り替えは非常に意味のあるものになります。

于 2010-05-06T20:47:27.790 に答える