维基百科上的这段左派树代码正确吗？

发布于 2024-08-31 18:42:23 字数 1225 浏览 9 评论 0原文

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;
  }

这不是行不通吗，因为引用仅在方法内部切换？

原文

Link

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;
}

What makes me ask this question is:

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

Isn't that just not gonna work, since the references are only switched inside the method?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

无远思近则忧 2024-09-07 18:42:23

它正在切换它们，以便稍后在方法内执行。尽管 switch 不会直接更改方法外部的任何引用，但会进行检查，以便代码中只有一条逻辑路径，较小值的元素始终位于 x 节点中，以便稍后在代码中进行交换使用正确的元素。

对于一个具体示例，请查看下一行代码：

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

两者（x 或 y）中较小的一个将合并到其下方，在其右子节点处，即两个中较大的一个。因此，这允许方法本身担心顺序，并且意味着可以按任何顺序添加两个元素，并且因此会发生正确的行为。

希望这有帮助。

It is switching them for the purposes of the later executions inside the method. Although the switch does not change any references directly outside the method, the check is done so that there is only one path of logic through the code, with the smaller valued element always being in the x node, so that their swapping later in the code works with the correct elements.

For one specific example, look at the next line of code:

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

Whichever is the smaller of the two (x or y) will be merging underneath it, at it's right child, the larger of the two. So, this allows the method itself to worry about the ordering, and means that the two elements can be added in any order, and the correct behavior will occur because of it.

Hope this helps.

回复收藏 0 原文