1 / 17 일 모각코 제 6회 결과

8 주차 : AVL 트리 구현

key 값과 함께 balance factor 를 프린트 하는 to String() 메소드 

public String toString() {  //키 값과 함께 balance factor 를 같이 프린트

if (this == NIL) return "";

return  left + " " + key +  "("+ (left.height-right.height) +")"  +" " + right;

}

키가 주어졌을 때 검색하여 트리내에 있으면 노드 삭제 하는 remove 메소드  ( 순환적인 방법 사용 ) 

public AVLTree remove(int key) { 

if (this == NIL) return new AVLTree(key); 

if (key < this.key)

left = left.remove(key); // 키가 찾는 값보다 작다면 left = left.remove(key)

else if(key > this.key)  

right = right.remove(key); // 키가 찾는 값보다 크다면 right = right.remove(key)

if(key == this.key) { //만약 키값과 같은것을 찾았다면 

if(left== NIL&&right == NIL) // 왼쪽자식과 오른쪽 자식이 없다면 NIL 리턴 

return NIL; 

if(left== NIL) // 왼쪽 자식이 없다면 오른쪽 자식 리턴 

     return right; 

if(right == NIL) // 오른쪽자식이 없다면 왼쪽 자식 리턴 

return left; 

if(right.height==0) { // 오른쪽 자식이 1개만 있어서 그 자식이 키값으로 대체          this.key = right.key; //  키자리에 오른쪽 자식을 넣음 

this.right = NIL; // this.right 을 NIL 로 만듬 

rebalance( );

height = Math.max(left.height, right.height)+1;

return this;

}

         this.key = this.right.minimumremove(); // this의 오른쪽에서 중위후속자를 찾음 

  this.right.height = Math.max(right.left.height, right.right.height)+1;

 // 오른쪽 트리의 높이 재정비 

}

rebalance( );

height = Math.max(left.height, right.height)+1; // 트리의 높이 재정비 

return this;

}

remove 메소드에서 중위후속자 삭제시 사용하는 minimumremove 메소드 

public int minimumremove() { // 중위후속자를 찾고 삭제 

if(this.left.left==NIL) { // 왼쪽자식의 왼쪽트리가 없다면 

int temp =this.left.key; // 왼쫏의 키를 템프에 넣어두고     

   if(this.left.right==NIL) // 만약 왼쪽의 오른쪽 자식도 없다면 

this.left=NIL; // 왼쪽을 NIL 로만든다 

else // 왼쪽의 오른쪽 자식이 있다면 

this.left = this.left.right; // 왼쪽에 왼쪽의 오른쪽 자식을 넣음 

height = Math.max(this.left.height, this.right.height)+1;  // 높이 재정비 

rebalance();

return temp; // 중위후속자리턴 

}

else

return this.left.minimumremove(); // 왼쪽자식에서 recursive 하게 중위후속자를 찾음 

}