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

Вы должны просто избегать копирования узлов; вы можете сбалансировать поддеревья, просто назначив их слева и справа указатели.

Функции вращения должны принимать корни поддерева в качестве параметра и возвращать преобразованное поддерево; вращающиеся деревья «на месте» являются основным ненужным осложнением.

Answer 2

очень простой способ глубокой клон является реализация Serializable, а затем сериализации/десериализации объекта (например, к ByteArrayOutputStream).