패스트캠퍼스 챌린지 7일차

트리(Tree) 구조

 • 트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 

  - 이진 트리(Binary Turee) 탐색 알고리즘 구현을 위해 많이 사용됨

 

(좌) 사이클을 이루지 않는 구조, (우) 노드 구조 및 용어

용어

 • Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)

 • Root Node : 트리 맨 위에 있는 노드

 • Level : 최상위 노드를 Level 0으로 하였을 떄, 하위 Branch로 연결된 노드의 깊이를 나타냄

 • Parent Node : 어떤 노드의 다음 레벨에 연결된 노드

 • Child Node : 어떤 노드의 상위 레벨에 연결된 노드

 • Leaf Node : Child Node가 하나도 없는 노드

 • Silbing : 동일한 Parent Node를 가진 노드

 • Depth : 트리에서 Node가 가질 수 있는 최대 Level 

 

이진트리 와 이진 탐색 트리 (Binary Search Tree)

 • 이진 트리 : 노드의 최대 Branch가 2인트리

 • 이진 탐색 트리 : 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있다.

 

public class NodeMgmt{
  Node head; 
    
  public class Node {
    Node left; 
    Node right;
    int value;
    
    public Node(int data){
      this.value = data;
      this.left = null;
      this.right = null;
    }
  
    // 데이터 넣기
    public boolean insertNode(int data){
      // CASE1 : Node 가 하나도 없을 때
       if(this.head == null){
         this.head = new Node(data);
       }else{
         // CASE2 : Node 가 하나 이상 들어가 있을 떄
      	 Node findNode = this.head;
         while(true){
           // CASE2-1: 현재 노드의 왼쪽에 노드가 들어가야 할 때
           if(data < findNode.value){
             // 왼쪽에 노드가 없다면
             if(findNode.left != null){
               findNode = findNode.left;
             }else{
               findNode.left = new Node(data);
               break;
             }
           // CASE2-2: 현재 노드의 오른쪽에 노드가 들어가야 할 때
           }else{
             if(findNode.right != null){
               findNode = findNode.right;
             }else{
               findNode.right = new Node(data);
               break;
             }
           }
         }
      }
    }
    return true;
  }
  
  // 데이터 검색
  public Node search(int data){
    // CASE1 : 노드가 하나도 없을 때
    if(this.head == null){
      return null;
    }else{ // CASE2 : 노드가 하나 이상 있을 
      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;
        }
      }
      // 왼쪽, 오른쪽 다 돌고나서 값이 없을 경우 null 리턴
      return null;
    }    
  }
  
}

 

 

노드 삭제

public boolean delete(int value){
  boolean searched = false;
  
  Node currParentNode = this.head;
  Node currNode = this.head;
  
  // 코너 케이스1 : 노드가 하나도 없을 떄
  if(this.head = null){
    return false;
  }else{ // 코너 케이스2 : 노드가 하나만 있고, 해당 노드가 삭제할 노드일 떄
    if(this.head.value == value && this.head.left == null && this.head.right == null){
      this.head = null;
      return true;
    }
  }
  
  while(currNode != null){
    if(currNode.value == value){
      searched = true;
      break;
    }else if(value < currNode.value){
      currParentNode = currNode;
      currNode = currNode.left;
    }else{
      currParentNode = currNode;
      currNode = currNode.right;
    }
  }
  
  // 삭제할 노드가 없다
  if(searched == false){
    return false;
  }
  
}

 

 1. Leaf Node 삭제

  -  삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.

  -  부모노드를 찾아 부모노드에서 브런치를 끊는다

if(currNode.left == null && currNode.right == null){
  if(value < currParentNode.value){
    currParentNode.left = null;
    currNode = null; // 명시적으로 선언
  }else{
    currParentNode.right = null;
    currNode = null;
  }
  return true;
}

 

 2. Child Node가 하나인 Node 삭제

  - 삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다

  EX) 10 -> 15 -> 19  => 10 -> 19

// 위의 Leaf Node 제거 로직 다음부터
else if(currNode.left != null && currNode.right == null){
  // CASE 1 : 삭제할 노드가 Child Node를 왼쪽에 한 개 가지고 있을 경우
  if(value < currParentNode.value){
    currParentNode.left = currNode.left;
    currNode = null;
  }else{
    currParentNode.right = currNode.left;
    currNode = null;
  }
  return true;
}else if(currNode.left == null && currNode.right != null){
  // CASE 2 : 삭제할 노드가 Child Node를 오른쪽에 한 개 가지고 있을 경우
  if(value < currParentNode.value){
    currParentNode.left = currNode.right;
    currNode = null;
  }else{
    currParentNode.right = currNode.right;
    currNode = null;
  }
  return true;
}

 

 3. Child Node가 두 개인 Node 삭제

 

// 위의 코드에 이어서

// 삭제할 Node가 Child Node를 두 개 가지고 있을 떄
} else{
  //삭제할 Node 가 부모 Node의 왼쪽에 있을 떄 
  if(value < currParentNode.value){
    Node changeNode = currNode.right;
    Node changeParentNode = currNode.right;
    while(changeNode.left != null){
      changeParentNode = changeNode;
      changeNode = changeNode.left;
    }
    // 여기까지 실행되면, changeNode에는 삭제할 Node의 오른쪽 Node중에서 가장 작은 값을 가진 노드가 들어있다
    if(changeNode.right != null){
      // changeNode의 Child Node가 없을 떄
      changeParentNode.left = changeNode.right;
    }else{
      // changeNode의 오른쪽 childNode가 있을 떄
      changeParentNode.left = null;
    }
    
    // currParentNode의 왼쪽 Child Node에 삭제할 Node의 오른쪽 자식중 가장 작은 값을 가진 changeNode를 연결
    currParentNode.left = changeNode;
    
    // parentNode의 왼쪽 Child Node가 현재, changeNode이고
    // changeNode의 왼쪽/오른쪽 Child Node를 모두 삭제할 currNode의 기존 왼쪽/오른쪽 Node로 변경
    changeNode.right = currNode.right;
    changeNode.left = currNode.left;
    
    currNode = null;
  
   else{ //삭제할 Node 가 부모 Node의 오른쪽에 있을 떄 
      Node changeNode = currNode.right;
      Node changeParentNode = currNode.right;
      while(changeNode.left != null){
        changeParentNode = changeNode;
        changeNode = changeNode.left;
      }
     // 여기까지 실행되면, changeNode에는 삭제할 Node의 오른쪽 Node중에서 가장 작은 값을 가진 노드가 들어있다
     if(changeNode.right != null){
       // changeNode의 Child Node가 없을 떄
       changeParentNode.left = changeNode.right;
     }else{
       // changeNode의 오른쪽 childNode가 있을 떄
       changeParentNode.left = null;
     }
     
     currParentNode.right = changeNode;
     
     changeNode.right = currNode.right;
     changeNode.left = currNode.left;
     
     currNode = null;
   }
  
  return true;
  
  }
}

 

 

노드를 제거한 후 이진트리 구조 

 

시간 복잡도 (탐색 시)

 • n개의 노드를 가진다면, h = logn 에 가까우므로, 시간복잡도는 O(logn)

 

 

7일차 인증

 

현재까지 딱 일주일 정도의 챌린지를 진행해 보았다.

매일마다 한다는 부담감은 있지만 이렇게 꾸준히 하다보면 한단계 더 성장하는 개발자가 되어있기를 바란다..

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]