Java递归深度克隆

Question

晚上好。

我正在尝试实现 AVL 树，但在旋转过程中复制节点时遇到问题:

• 如果我使用浅拷贝来执行此操作，则会发生相当可预见的困惑。
• 如果我使用手动深层复制，我只能复制对象(节点)的直接属性，而不能复制其更深层次的属性。 澄清一下，如果我有一个节点，它有 2 个子节点，它们本身有 1-2 个子节点，并且其子节点可能有自己的子节点，...我只能复制初始节点及其直接子节点，但会失去孙子节点和进一步的节点后代。

所以，我想知道是否有办法绕过这个限制。
这是该类的完整代码(主要只是对initialise()的调用)，其他所有内容都正常运行，因此如果我能够在旋转中正确复制节点，我将拥有一个可用的AVL树。

预先感谢您的帮助。

import java.util.ArrayList;

public class NodeQ
{
static boolean isEmpty=true;
private int h=1;
private double x, y;
private ArrayList<Segment> segmentsStarting=new ArrayList<Segment>();
private NodeQ left=null, right=null;

public NodeQ(double abs, double ord) {x=abs; y=ord;}
public NodeQ(NodeQ Q) {this.x=Q.x; this.y=Q.y; this.segmentsStarting=Q.segmentsStarting;}

public double getX() {return x;}
public double getY() {return y;}
public NodeQ getLeft() {return left;}
public NodeQ getRight() {return right;}
public ArrayList<Segment> getSegmentsStarting() {return segmentsStarting;}
public int getH(){return h;}

public void setX(double abs) {x=abs;}
public void setY(double ord) {y=ord;}
public void setLeft(NodeQ l) {left=l;}
public void setRight(NodeQ r) {right=r;}
public void addSegment(Segment s) {segmentsStarting.add(s);}

public void calcH()
{
    if (this.left!=null)
    {
        if (this.right != null)
        {
            if (this.left.h > this.right.h) this.h = this.left.h + 1;
            else this.h = this.right.h + 1;
        }
        else this.h = this.left.h + 1;
    }
    else if (this.right!=null) this.h=this.right.h+1;
}

public void initialise(Segment segment)
{
    if (NodeQ.isEmpty)
    {
        y=segment.yUpper; 
        x=segment.xUpper;
        addSegment(segment); 
        setLeft(new NodeQ(segment.xLower, segment.yLower));
        h=2;
        NodeQ.isEmpty=false;
    }
    else
    {
        insert(segment.xUpper, segment.yUpper, true, segment);
        insert(segment.xLower, segment.yLower, false, segment);
    }
}

public void deepCopy(NodeQ Q)
{
    this.x=Q.x;
    this.y=Q.y;
    this.segmentsStarting=Q.segmentsStarting;
    if (Q.left==null)this.left=null;
    else this.left=new NodeQ(Q.left);
    if (Q.right==null) this.right=null;
    else this.right=new NodeQ(Q.right);
}

public void insert(double abs, double ord, boolean isUpperEndpoint, Segment s)
{
    if (y>ord || (y==ord && x<abs))
    {
        if (left==null)
        {
            left=new NodeQ(abs, ord); 
            if (isUpperEndpoint) addSegment(s);
        }
        else left.insert(abs, ord, isUpperEndpoint, s); 
    }
    else
    {
        if (right==null)
        {
            right=new NodeQ(abs, ord);
            if (isUpperEndpoint) addSegment(s);
        }
        else right.insert(abs, ord, isUpperEndpoint, s);
    }
    balancing();
}

public void leftRotation()
{
    NodeQ tmp=new NodeQ(-1, -1);
    tmp.deepCopy(this);
    this.deepCopy(this.right);

    if (this.left==null) tmp.right=null;
    else tmp.right=new NodeQ(this.left);
    this.left=new NodeQ(tmp);

    tmp.calcH();
    this.calcH();
}

public void rightRotation()
{
    NodeQ tmp=new NodeQ(-1, -1);
    tmp.deepCopy(this);
    this.deepCopy(this.left);

    if (this.right==null) tmp.left=null;
    else tmp.left=new NodeQ(this.right);
    this.right=new NodeQ(tmp);

    tmp.calcH();
    this.calcH();
}

public int calcBalance()
{
    int bal=0;
    if (left==null)
    {
        if (right!=null) bal=right.h;
    }
    else
    {
        if (right==null) bal=-left.h;
        else bal=right.h-left.h;
    }
    return bal;
}

public void balancing()
{
    int b=calcBalance();
    if (b==2)
    {
        if (right.calcBalance()<0) right.rightRotation();
        leftRotation();
    }
    else if (b==-2)
    {
`       if (left.calcBalance()>0) left.leftRotation();
        rightRotation();
    }
    else calcH();
}
}

Answer 1

您应该避免复制节点；您只需分配子树的左和右指针即可平衡子树。

旋转函数应将子树根作为参数并返回变换后的子树； “就地”旋转树木是一个主要的、不必要的复杂情况。