이진 트리 (2)

package NodeMgmtTest; //Node클래스가 겹쳐서 따로만듬
//노드 클래스 만들기 
class Node{
 Node left;
 Node right;
 int value;
 Node(int data) {
     this.value = data;
     this.left = null;
     this.right = null;
 }
}

public class NodeMgmt {
//	트리(Tree)의 구조
//	트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 
//	Branch : 노드와 노드를 연결 
//	실제 사용 처 :  
//		트리 중 이진 트리(Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용된다.
//		
//	용어 : 
//		Node : 트리에서 데이터를 저장하는 기본요소(데이터와 다른 연결된 노드에 대한 Branch 정보도 포함한다)
//		Root Node : 트리 맨 위에 있는 노드 (최상위 노드)
//		Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타낸다.
//		Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
//		Child Node : 어떤 노드의 상위 레벨에 연결된 노드
//		Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드
//		Sibling (Brother Node) : 동일한 Parent Node를 가진 노드
//		Depth : 트리에서 Node가 가질 수 있는 최대 Level
		
//	이진 트리와 이진 탐색 트리(Binary Search Tree)
//	이진 트리 : 노드의 최대 Branch가 2인 트리
//	이진 탐색 트리(Binary Search Tree, BST) : 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
//	-> 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음

//	이진 탐색 트리의 주요 용도 : 데이터 검색(탐색)
//	이진 탐색 트리의 장점 : 탐색 속도를 개선할 수 있다.
	
//	헤드 초기화
 Node head = null;

//	이진 탐색 트리에 데이터 넣기
 public boolean insertNode(int data) {

	//Case 1 : Node가 하나도 없을 때
     if (this.head == null) {
         this.head = new Node(data);
     } else {//Case 2 : Node가 하나 이상 존재할 때
         Node findNode = this.head;
         while (true) {//Case2-1 : 현재 Node의 왼쪽에 Node가 들어가야 할 떄       
             if (data < findNode.value) { 
                 if (findNode.left != null) {//왼쪽 노드가 비어있지 않으면
                     findNode = findNode.left;//왼쪽 노드로 find를 바꿔서 다시 탐색 (level down)
                 } else {//왼쪽 노드가 비어있으면
                     findNode.left = new Node(data);//왼쪽에 데이터를 삽입
                     break;
                 }

               //Case 2-2 : 현재 Node의 오른쪽에 Node가 들어가야 할때
             } else {// data > findNode.value
                 if (findNode.right != null) {//오른쪽 노드가 비어있지 않으면
                     findNode = findNode.right;//오른쪽 노드로 findNode로 바꿔서 다시 탐색(level down)
                 } else {//오른쪽 노드가 비어있으면
                     findNode.right = new Node(data);
                     break;
                 }
             }
         }
     }
     return true;
 }

//	이진 탐색 트리 탐색
 public Node search(int data) {
	//Case 1 : Node가 하나도 없을 떄 
     if (head == null) {
         return null;
     } else {        //Case 2 : Node가 하나 이상 있을 때
         Node findNode = this.head;
         while (findNode != null) {//노드 순회
             if (findNode.value == data) { //데이터를 찾았을 시 
                 return findNode;//데이터반환 
             } else if (data < findNode.value) {//찾는 데이터값이 현재 노드보다 작다면  
                 findNode = findNode.left;//왼쪽 노드로 탐색 
             } else {//더 크다면 
                 findNode = findNode.right;//오른쪽 노드로 탐색
             }
         }
         return null;
     }
 }
 
//	이진 탐색 트리 삭제
//	Case 1 : Leaf Node 삭제
//	Leaf Node : Child Node가 없는 Node
//	삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다. (null 로 만든다.)
//	
//	Case 2 : Child Node가 하나인 Node 삭제
//	삭제할 Node의 ParentNode가 삭제할 Node의 Child Node를 가리키도록 한다.
//	
//	Case 3 : Child Node가 두 개인 Node 삭제
//	1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
//	2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
//	
//	Case 3-1 인 경우
//	삭제할 Node의 오른쪽 자식 선택
//	오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
//	해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함
//	해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
//	만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 
//	해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함
	
//	1. 삭제할 Node 탐색
//		삭제할 Node가 없는 경우도 처리해야 한다.
//			이를 위해 삭제할 Node가 없는 경우에는 false를 리턴하고, 함수를 종료 시킨다.
	
//Case 3-1 : 삭제할 Node가 ChildNode를 두 개 가지고 있을 경우(삭제할 Node가 Parent Node 왼쪽에 있을 때)
//	기본 사용 가능 전략
//	1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
//	2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
	
	//1번을 선택해서 구현 
//	Case 3-1-1 : 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 
//	가장 작은 값을 가진 Node의 Child Node가 없을 때
//	Case 3-1-2 : 삭제할 Node가 Parent Node의 왼쪽에 있고, 삭제할 Node의 오른쪽 자식 중, 
//	가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때 
//		-가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음. 
//		이유는 왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻 
	
//	Case3-2 : 삭제할 Node가 ChildNode를 두 개 가지고 있을 경우(삭제할 Node가 ParentNode 오른쪽에 있을 떄)
//	기본 사용 가능 전략 
//	1. 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
//	2. 삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
	//1번을 선택해서 구현 
//	Case 3-2-1 : 삭제할 Node가 Parent Node의 오른쪽 에 있고, 삭제할 Node의 오른쪽 자식 중, 
//	가장 작은 값을 가진 Node의 Child Node가 없을 때
//	Case 3-2-2 : 삭제할 Node가 Parent Node의 오른쪽에 있고, 삭제할 Node의 오른쪽 자식 중,
//	가장 작은 값을 가진 Node의 Child가 오른쪽에 있을 때
//		가장 작은 값을 가진 Node의 Child Node가 왼쪽에 있을 경우는 없음, 이유는
//		왼쪽 Node가 있다는 것은 해당 Node보다 더 작은 값을 가진 Node가 있다는 뜻

 public boolean delete(int value) {
     boolean searched = false;
     
     Node currParentNode = this.head;
     Node currNode = this.head;

	//예외 Case 1 : Node가 하나도 없을 때 
     if (this.head == null) {
         return false;
     } else {
    	//예외 Case 2 : Node가 단지 하나만 있고 , 해당 Node가 삭제할 Node일 때
         if (this.head.value == value && this.head.left == null && this.head.right == null) {
             this.head = null; // 루트 노드 삭제
             return true;
         }

         while (currNode != null) {//값 탐색  , currNode를 설정하는 작업
             if (currNode.value == value) {//현재 Node가 찾는 값이면 반복문 종료
                 searched = true;
                 break;
             } else if (value < currNode.value) {//찾는 값이 현재 노드값보다 작으면 왼쪽 노드로 탐색
                 currParentNode = currNode;
                 currNode = currNode.left;
             } else {//찾는 값이 현재 노드값보다 크면 오른쪽 노드 탐색
                 currParentNode = currNode;
                 currNode = currNode.right;
             }
         }

         if (searched == false) {
             return false;
         }
     }
     	//여기 까지 실행되면 , currNode에는 해당 데이터를 가지고 있는 Node, 
   		//curParentNode에는 해당 데이터를 가지고 있는 Node의 부모 Node

//		Case 1 : 삭제할 Node가 LeafNode인 경우
     if (currNode.left == null && currNode.right == null) {//LeafNode의 조건 
         if (value < currParentNode.value) {//삭제할 값이 부모의 값보다 작다면
             currParentNode.left = null;
             currNode = null; //가독성 높이기 위해서 씀(안써도됨)
         } else {//삭제할 값이 부모의 값보다 크다면 
             currParentNode.right = null;
             currNode = null; // 해당 객체 삭제를 위해, 강제로 null 로 만들어줌
         }
         return true;
         //Case 2-1 : 삭제할 Node가 Child Node를 한 개 가지고 있을 경우 (왼쪽에 Child Node가 있을 경우)
     } else if (currNode.left != null && currNode.right == null) {
         if (value < currParentNode.value) { //삭제할 값이 currParent보다 작을 경우
             currParentNode.left = currNode.left;
             currNode = null;
         } else {//삭제할 값이 currParent보다 클 경우
             currParentNode.right = currNode.left;
             currNode = null;
         }
         return true;
       //Case 2-2 : 삭제할 Node가 Child Node를 한 개 가지고 있을 경우 (오른쪽에 Child Node가 있을 경우)
     } else if (currNode.left == null && currNode.right != null) {
         if (value < currParentNode.value) {//삭제할 값이 currParent보다 작을 경우
             currParentNode.left = currNode.right;
             currNode = null;
         } else {//삭제할 값이 currParent보다 클 경우
             currParentNode.right = currNode.right;
             currNode = null;
         }
         return true;
// 		Case 3-1 : 삭제할 Node가 Child Node를 두 개 가지고 있고 
     } else {
         // 삭제할 Node가 Parent Node 왼쪽에 있을 때
         if (value < currParentNode.value) {

             // 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node 찾기
             Node changeNode = currNode.right;
             Node changeParentNode = currNode.right;
             while (currNode.left != null) {//가장 작은 값 까지 찾아간다.
                 changeParentNode = currNode;
                 changeNode = currNode.left;
             }
             // 여기까지 실행되면, changeNode 에는 삭제할 Node 의 오른쪽 자식 중, 
             //가장 작은 값을 가진 Node 가 들어있음

             if (changeNode.right != null) {
                 // Case3-1-2: 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 있을 때
                 changeParentNode.left = changeNode.right;
             } else {
                 // Case3-1-1: 삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 가진 Node의 오른쪽에 Child Node가 없을 때
                 changeParentNode.left = null;
             }
             // parent Node 의 왼쪽 Child Node 에 삭제할 Node의 오른쪽 자식 중, 
             //가장 작은 값을 가진 changeNode 를 연결
             currParentNode.left = changeNode;
            //ParentNode의 왼쪽 ChildNode가 현재, changeNode이고,
			//changeNode의 왼쪽/오른쪽 Child Node 모두, 삭제할 currNode의 
			//기존의  있던 왼쪽 /오른쪽 Node로 변경
             changeNode.right = currNode.right;
             changeNode.left = currNode.left;

             // 삭제할 Node 삭제!
             currNode = null;
            
         } else {//Case 3-2 : 삭제할 Node가 Child Node를 두 개 가지고 있고 ,
        	 //(삭제할 Node 가 부모 Node 의 오른쪽에 있을 때)
             Node changeNode = currNode.right;
             Node changeParentNode = currNode.right;
             while (changeNode.left != null) {
                 changeParentNode = changeNode;
                 changeNode = changeNode.left;
             }
           //여기까지 실행되면, changeNode에는 삭제할 Node의 오른쪽 Node중에서,
			//가장 작은 값을 가진 Node가 들어있음

             if (changeNode.right != null) {
            	//case 3-2-2 : changeNode의 오른쪽 Child Node가 있을 때
                 changeParentNode.left = changeNode.right;
             } else {
            	//Case 3-2-1 : changeNode의 Child Node가 없을 때
                 changeParentNode.left = null;
             }

             //currParentNode의 오른쪽 Child Node에, 삭제할 Node의 오른쪽 자식 중,
			 //가장 작은 값을 가진 changNode를 연결 
             currParentNode.right = changeNode;
             //parentNode의 왼쪽 Child Node가 현재 , changeNode이고,
             //changeNode의 왼쪽 /오른쪽 ChildNode를 모두, 삭제할 currNode의 
             //기존노드에 연결된 왼쪽/오른쪽  Node를 연결 해줌 
             changeNode.right = currNode.right;
             changeNode.left = currNode.left;

             // 삭제할 Node 삭제!
             currNode = null;
         }
         return true;
     }
 }

 public static void main(String[] args) {
     
     NodeMgmt myTree = new NodeMgmt();
     myTree.insertNode(10);
     myTree.insertNode(15);
     myTree.insertNode(13);
     myTree.insertNode(11);
     myTree.insertNode(14);
     myTree.insertNode(18);
     myTree.insertNode(16);
     myTree.insertNode(19);
     myTree.insertNode(17);
     myTree.insertNode(7);
     myTree.insertNode(8);
     myTree.insertNode(6);
     System.out.println(myTree.delete(15));
     System.out.println("HEAD: " + myTree.head.value);
     System.out.println("HEAD LEFT: " + myTree.head.left.value);
     System.out.println("HEAD LEFT LEFT: " + myTree.head.left.left.value);
     System.out.println("HEAD LEFT RIGHT: " + myTree.head.left.right.value);

     System.out.println("HEAD RIGHT: " + myTree.head.right.value);
     System.out.println("HEAD RIGHT LEFT: " + myTree.head.right.left.value);
     System.out.println("HEAD RIGHT RIGHT: " + myTree.head.right.right.value);

     System.out.println("HEAD RIGHT RIGHT LEFT: " + myTree.head.right.right.left.value);
     System.out.println("HEAD RIGHT RIGHT RIGHT: " + myTree.head.right.right.right.value);
 
     //시간 복잡도(탐색 시 )
//     depth(트리의 높이)를 h라고 표기한다면, O(h)
//     n개의 노드를 가진다면, h = log_2 n에 가까우므로, 시간 복잡도는 O(logn)
//     	logn에서의 log의 밑은 10이 아니라 2이다.
//     	즉 : 학번 실행시 마다, 50% 의 실행할 수도 있는 명령을 제거한다는 의미, 즉 50%의 실행 시간을 단축 시킬 수 있다.

     	/*이진 탐색 트리의 단점
     	평균 시간 복잡도는 O(logn)이지만 ,
     		이는 트리가 균형이 잡혀 있을 때의 평균 시간 복잡도이고
     	만약 노드 자식이 한쪽으로만 쭉 있는 것처럼 구성되어 있으면 ,
     	최악의 경우이다.
     	최악의 경우는 링크드 리스트등과 동일한 성능을 보인다(O(n))*/
 
 }
}

이진트리 삭제 구현 및 테스트