트리와 이진 탐색 트리(2)

1) search 메소드

public class NodeMgmt{
    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){
         if(this.head == null){

        }else{
            Node findNode = this.head; 
              
            while(true){
              if(data < findNode.value){
                   if(findNode.left != null){
                       findNode = findNode.left; 
                   }else{
                      findNode.left = new Node(data); 
                      break; 
                   }
              }else{
                  if(findNode.right != null){
                      findNode = findNode.right; 
                  }else{
                      findNode.right = new Node(data);
                      break;
                  }
            }
            return true;
        }  
   
     }

     public Node search(int data){

        if(this.head == null){
            return  null;
        }else{
           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; 
}

 

 

2) 이진 탐색 트리 삭제

 

-> 복잡한 코드의 경우의 수를 나눠서 생각해봄

 

- 삭제를 여러 가지 케이스로 구분해서 생각

(1) leaf node인 경우

(2) Child node가 하나인 노드를 삭제할 때

(3) Child node가 2개인 노드를 삭제할 때,

-> 삭제할 노드의 오른쪽 자식 중 가장 작은 값을

    Node의 Parent Node가 가리키도록 한다. 

 

 

참고

- 한 번에 끝내는 코딩테스트 369 Java편 초격차 패키지 Online편