이진 탐색 트리(2) - 구현

1) 이진 탐색 트리 구현

(1) 노드

- 이진 탐색 트리도 이진 트리이기 때문에,

   좌측 자식 노드와 우측 자식 노드 변수를 만들어줍니다. 

class Node{
    int key;
    Node left;
    Node right;
}

(2) 이진 탐색 트리

- 이진 탐색 트리의 기본 행위는 키를 추가하고, 삭제하고, 찾는 것입니다. 

 

(2-1) 추가

- 키를 추가하는 것은 루트가 null인 경우와 루트가 null이 아닌 경우로 나누어집니다.

  루트가 null인 경우는 새로운 노드를 루트 노드로 저장하고,

  루트가 null이 아닌 경우는 재귀적으로 insertNode 메소드를 호출하여, 

  노드가 삽입되어야 할 위치를 재귀적으로 찾아, 새로운 노드를 반환 후, 

  이전 분기점으로 돌아가 연결시키는 방식으로 동작합니다. 

 

(2-2) 가장 작은 키를 가진 노드를 찾기

- 좌측 자식이 null 값이 될 때까지 재귀적으로 호출합니다. 

  

(2-3) 가장 큰 키를 가진 노드를 찾기

- 우측 자식이 null 값이 될 때까지 재귀적으로 호출합니다. 

 

(2-4) 키를 삭제

- 키를 삭제하는 것은 크게 3가지 흐름으로 진행됩니다.

  (1) 삭제할 키를 찾아가는 행위

  (2) 삭제할 키를 찾으며, 좌측 자식에서 가장 큰 키 또는 우측 자식에서 가장 작은 키를 찾아 스왑하는 행위

  (3) 리프 노드이면 연결을 끊는 행위

 

(2-5) 키를 검색

- 재귀적으로 호출한다는 점과 반환값이 존재한다는 점 때문에 

  키의 삽입, 삭제, 검색은 비슷합니다. 

  따라서 하나를 이해하면 전반적인 원리가 이해됩니다.  

class BinarySearchTree{

   Node root;
   
   public int search(int key){
     return searchNode(root, key).key;
   }
   
   Node getSmallestNode(Node x){
      if(null == x.left){
         return x;
      }
      return getSmallestNode(x.left);
   }
   
   Node getLargestNode(Node x){
      if(null == x.right){
        return x;
      }
      return getLargetNode(x.right); 
   }
   
   Node searchNode(Node x, int key){
      Node node = x;
      if(null == node){
         throw new RuntimeException("노드가 없음");
      }else if(node.key > key){
         node = searchNode(x.left, key);
      }else if(node.key < key){
         node = searchNode(x.right, key);
      }  
      return node;
   }
   
   public void add(int key){
      Node newNode = new Node(key);
      
      if(root == null){
         root = newNode;
      }else{
         root = insertNode(root, newNode);
      }
   }
   
   
   Node insertNode(Node x, Node newNode){
       if(null == x){
          return newNode;
       }else if(x.key > newNode.key){
          x.left = insertNode(x.left, newNode);
       }else{
          x.right = insertNode(x.right, newNode);
       }
       return x;
   }


   Node removeNode(Node x, int key){
      if(null == x){
         throw new RuntimeException("노드가 존재하지 않음");
      }else if(x.key > key){
         x.left = removeNode(x.left, key);
      }else if(x.key < key){
         x.right = removeNode(x.right, key);
      }else{
        if(null != x.left){
          Node predecessor = getLargestNode(x.left);
          int removeKey = x.key;
          x.key = predecessor.key;
          predecessor.key = removeKey;
          x.left = removeNode(x.left, key);
        }else if(null != x.right){
          Node successor = getSmallestNode(x.right);
          int removeKey = x.key;
          x.key = successor.key;
          successor.key = removeKey;
          x.right = removeNode(x.right, key);
        }else{
          return null;
      }
     }
     return x;
   }



}

 

참고

코드라떼 자료구조