[JAVA] 이진 탐색 트리 (Binary Search Tree, BST)

이진 탐색 트리 (Binary Search Tree, BST)

---

이진 탐색 트리 (Binary Search Tree, BST)

• 이진 트리의 일종
• 데이터를 트리에 저장하는 규칙에 따라야 함
• 노드에 저장된 키 값은 유일해야 함
• 왼쪽 자식 노드 키 > 부모 노드 키 > 오른쪽 노드 키
• 삽입할 데이터가 부모 노드보다 작으면 왼쪽, 크면 오른쪽에 삽입
• 왼쪽과 오른쪽의 서브 트리도 이진 탐색 트리
  

  

이진 탐색 트리 구현 방법

• 삽입
  부모 노드와 삽입할 데이터를 비교해서 삽입할 데이터가 더 크면 오른쪽에 추가하고, 더 작으면 왼쪽에 추가한다. 단, 비교할 대상이 없을때까지 내려가야 한다.
  

  

• 탐색
  삽입과 마찬가지로 찾고자하는 데이터가 부모 노드보다 작으면 왼쪽, 크다면 오른쪽으로 탐색한다. 단, 탐색 도중 데이터를 찾았거나 마지막까지 탐색했다면 탐색을 중지한다.
  
  
• 삭제
  임의의 노드(데이터)를 삭제하는 경우 삭제 후에도 이진 탐색 트리가 유지되도록 빈자리를 채워야 한다. 삭제에는 아래 3가지 경우가 있어 각각 다른 방식으로 삭제를 해야한다. 
  1) 단말 노드를 삭제할 경우
  2) 하나의 자식 노드를 가진 노드를 삭제할 경우
  3) 두 개의 자식 노드를 가진 노드를 삭제할 경우
  
  

1) 단말 노드를 삭제할 경우

2) 하나의 자식 노드를 가진 노드를 삭제할 경우

10을 삭제할 경우 자식 노드 13을 10의 위치로 복사하고 13의 노드를 삭제한다.

 

3) 두 개의 자식 노드를 가진 노드를 삭제할 경우

13을 이동시킨 이유는 이진 탐색 트리는 부모 노드의 왼쪽은 부모 노드보다 작은값, 오른쪽은 큰 값이 되어야 하므로 13을 이동시켰음. 18을 이동시켜도 상관없음

 

구현

• [BinaryTree.java]
  

  package BinarySearchTree;
  
  public class BinaryTree {
      BTreeNode createBTreeNode() {
          BTreeNode newNode = new BTreeNode();
          newNode.leftNode = null;
          newNode.rightNode = null;
  
          return newNode;
      }
  
      int getData(BTreeNode node) {
          return node.data;
      }
  
      void setData(BTreeNode node, int data) {
          node.data = data;
      }
  
      BTreeNode getLeftSubTree(BTreeNode node) {
          return node.leftNode;
      }
  
      BTreeNode getRightSubTree(BTreeNode node) {
          return node.rightNode;
      }
  
      void createLeftSubTree(BTreeNode parent, BTreeNode child) {
          if (parent.leftNode != null){
              parent.leftNode = null;
          }
  
          parent.leftNode = child;
      }
  
      void createRightSubTree(BTreeNode parent, BTreeNode child) {
          if (parent.rightNode != null) {
              parent.rightNode = null;
          }
  
          parent.rightNode = child;
      }
  
      // 중위 순회
      void InorderTraverse(BTreeNode node) {
          if (node == null){
              return;
          }
  
          InorderTraverse(node.leftNode);
          System.out.println(node.data);
          InorderTraverse(node.rightNode);
      }
  
      // 전위 순회
      void PreorderTraverse(BTreeNode node) {
          if (node == null) {
              return;
          }
  
          System.out.println(node.data);
          PreorderTraverse(node.leftNode);
          PreorderTraverse(node.rightNode);
      }
  
      // 후위 순회
      void PostorderTraverse(BTreeNode node) {
          if (node == null) {
              return;
          }
  
          PostorderTraverse(node.leftNode);
          PostorderTraverse(node.rightNode);
          System.out.println(node.data);
      }
  }​

• [BTreeNode.java]
  

  package BinarySearchTree;
  
  public class BTreeNode {
      int data;
      BTreeNode leftNode;
      BTreeNode rightNode;
  }

• [BST.java]
  

  package BinarySearchTree;
  
  public class BST extends BinaryTree {
      private BTreeNode rootNode = null;
  
      public void insert(int data) {
          // 첫 데이터가 추가됐을 때
          if (rootNode == null) {
              rootNode = new BTreeNode();
              setData(rootNode, data);
              return;
          }
  
          BTreeNode curNode = rootNode;
          BTreeNode parentNode = null;
          // 현재 노드에 데이터가 없을때까지 반복
          while(curNode != null) {
              // 키는 유일해야 하므로 중복값이 있을 경우 빠져나옴
              if (getData(curNode) == data) {
                  return;
              }
  
              // 자식노드가 없을 때 데이터 추가를 위해 부모노드의 값을 유지하고 있어야 함
              parentNode = curNode;
              // 현재 노드의 값이 삽입할 데이터의 값보다 크면 현재 노드의 왼쪽 서브트리에 데이터가 있다는 것이 되므로 왼쪽을 반환
              if (getData(curNode) > data) {
                  curNode = getLeftSubTree(curNode);
              }
              else {
                  curNode = getRightSubTree(curNode);
              }
          }
  
          BTreeNode newNode = new BTreeNode();
          setData(newNode, data);
  
          // 부모 노드의 값이 삽입할 데이터보다 크면 부모 노드의 왼쪽에 데이터를 삽입해야 하므로 왼쪽에 데이터를 등록함
          if (getData(parentNode) > data) {
              createLeftSubTree(parentNode, newNode);
          }
          else {
              createRightSubTree(parentNode, newNode);
          }
      }
  
      // 단순 검색 (존재 유무만 판단함)
      public boolean search(int data) {
          BTreeNode curNode = rootNode;
  
          // 현재 가리키고 있는 노드가 null일 때까지 반복해서 확인
          while(curNode != null) {
  
              // 현재 노드의 값이 찾으려는 대상과 같으면 true
              if (getData(curNode) == data) {
                  return true;
              }
              // 현재 노드의 값이 찾으려는 대상의 값보다 크면 왼쪽 서브트리에 찾을 대상이 있다는 것이므로 현재 노드의 왼쪽을 반환
              else if (getData(curNode) > data){
                  curNode = getLeftSubTree(curNode);
              }
              else {
                  curNode = getRightSubTree(curNode);
              }
          }
  
          return false;
      }
  
      public boolean remove(int data) {
          // 삭제할 노드가 있는지 검색
          BTreeNode deleteNode = rootNode;
          BTreeNode deleteParentNode = null;
          while (deleteNode != null && getData(deleteNode) != data) {
              deleteParentNode = deleteNode;
  
              if (getData(deleteNode) > data) {
                  deleteNode = getLeftSubTree(deleteNode);
              }
              else {
                  deleteNode = getRightSubTree(deleteNode);
              }
          }
  
          // 찾는 데이터가 없다면 false
          if (deleteNode == null) {
              return false;
          }
  
          // 단말노드 삭제 시
          if (getLeftSubTree(deleteNode) == null && getRightSubTree(deleteNode) == null) {
              if (getLeftSubTree(deleteParentNode) == deleteNode) {
                  removeLeftSubTree(deleteParentNode);
              }
              else {
                  removeRightSubTree(deleteParentNode);
              }
          }
          // 자식노드가 하나인 노드 삭제 시
          else if (getLeftSubTree(deleteNode) == null || getRightSubTree(deleteNode) == null) {
              // 삭제할 데이터가 부모노드의 왼쪽에 있는지 오른쪽에 있는지 확인
              if (getLeftSubTree(deleteParentNode) == deleteNode) {
                  // 부모노드의 왼쪽값이 null이 아니면 왼쪽에 데이터가 있다는 것이므로
                  // 부모노드의 왼쪽과 삭제할 데이터의 왼쪽을 연결해 이어줌
                  if (getLeftSubTree(deleteNode) != null) {
                      deleteParentNode.leftNode = deleteNode.leftNode;
                  }
                  // 부모노드의 오른쪽값이 null이 아니면 오른쪽에 데이터가 있다는 것이므로
                  // 부모노드의 왼쪽과 삭제할 데이터의 오른쪽을 연결해 이어줌
                  else {
                      deleteParentNode.leftNode = deleteNode.rightNode;
                  }
              }
              else {
                  if (getRightSubTree(deleteNode) != null) {
                      deleteParentNode.rightNode = deleteNode.rightNode;
                  }
                  else {
                      deleteParentNode.rightNode = deleteNode.leftNode;
                  }
              }
          }
          // 자식노드가 둘인 노드 삭제 시
          else {
              // 이진 탐색 트리의 특성 상 부모의 오른쪽 서브트리에서 가장 작은 값으로 부모노드를 변경해주어야 함
              BTreeNode replaceNode = getRightSubTree(deleteNode);
              BTreeNode replaceParentNode = deleteNode;
              while(getLeftSubTree(replaceNode) != null) {
                  replaceParentNode = replaceNode;
                  replaceNode = getLeftSubTree(replaceNode);
              }
              // 위 로직을 거치면 deleteNode는 삭제할 노드 대신 들어갈 노드를 가리키고,
              // deleteParentNode는 대신 들어갈 노드의 부모를 가리키게 됨.
  
              setData(deleteNode, getData(replaceNode));
  
              // 대신 들어갈 노드의 부모 노드의 왼쪽이 대신 들어갈 노드라면
              // 대신 들어갈 노드의 오른쪽 서브트리를 부모 노드의 왼쪽으로 연결한다.
              if (getLeftSubTree(replaceParentNode) == replaceNode) {
                  replaceParentNode.leftNode = replaceNode.rightNode;
              }
              // 대신 들어갈 노드의 부모 노드의 오른쪽이 대신 들어갈 노드라면
              // 부모 노드의 오른쪽을 대신 들어갈 노드의 오른쪽 노드와 연결한다.
              else {
                  replaceParentNode.rightNode = replaceNode.rightNode;
              }
          }
  
          return true;
      }
  
      private void removeLeftSubTree(BTreeNode node) {
          BTreeNode removeNode = node.leftNode;
          node.leftNode = null;
          removeNode = null;
      }
  
      private void removeRightSubTree(BTreeNode node) {
          BTreeNode removeNode = node.rightNode;
          node.rightNode = null;
          removeNode = null;
      }
  
      // 중위 순회
      void InorderTraverse(BTreeNode node) {
          if (node == null){
              return;
          }
  
          InorderTraverse(node.leftNode);
          System.out.print(node.data + " ");
          InorderTraverse(node.rightNode);
      }
  
      public void showAll() {
          InorderTraverse(rootNode);
          System.out.println();
      }
  }​

• [BSTMain.java]
  

  package BinarySearchTree;
  
  public class BSTMain {
      public static void main(String[] args) {
          BST bst = new BST();
  
          bst.insert(5); bst.insert(8);
          bst.insert(1); bst.insert(6);
          bst.insert(4); bst.insert(9);
          bst.insert(3); bst.insert(2);
          bst.insert(7);
          bst.showAll();
  
          bst.remove(3); bst.showAll();
          bst.remove(8); bst.showAll();
          bst.remove(1); bst.showAll();
          bst.remove(6); bst.showAll();
      }
  }​

• 테스트
  

  

두 개의 자식 노드가 있는 노드를 삭제할 때 헷갈린 부분이 있었다.

처음에는 대체할 부모의 노드의 왼쪽은 당연히 대체할 노드일 것이라고 생각해서 위 코드가 이해가 되지 않았다. 그러나 아래 그림을 삭제에 대입해서 생각해보니 당연한 얘기였다.

12를 삭제 시 위 코드의 if문에 들어가게 되고, 8을 삭제 시 else 문을 들어가게 된다. 데이터는 12, 8, 4, 6, 9, 10, 17, 13, 21 을 넣고 테스트해보면 된다.