☕️ [JAVA] 이진 탐색트리 구현

자바로 이진 탐색 트리를 구현했다. 

 

public class BinaryTree {
    Node head = null;

     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);
             return true;
         }
         // Case2. Node가 한개이상 있을 때
         Node findNode = this.head;
         while(true) {
             // Case2-1 현재 노드의 왼쪽에 들어가야할 때
             if (findNode.value > data && findNode.left != null) {
                 findNode = findNode.left;
             }
             if (findNode.value > data && findNode.left == null) {
                 findNode.left = new Node(data);
                 break;
             }
             // Case2-1 현재 노드의 오른쪽에 들어가야할 때
             if (findNode.value < data && findNode.right != null) {
                 findNode = findNode.right;
             }
             if (findNode.value < data && findNode.right == null) {
                 findNode.right = new Node(data);
                 break;
             }
             if (findNode.value == data) {
                 return false;
             }
         }
         return true;
     }

     public Node search(int data) {
         // Case1. Node가 하나도 없을 때
         if (this.head == null) {
             return null;
         }
         // Case. Node가 하나 이상일 떄
         Node findNode = this.head;
         while(findNode != null){
             if (findNode.value == data){
                 return findNode;
             }
             if (findNode.value > data){
                 findNode = findNode.left;
             }
             if (findNode.value < data) {
                 findNode = findNode.right;
             }
         }
         return null;
     }

     public boolean delete(int data) {

         boolean searched = false;
         Node parentNode = this.head;
         Node currNode = this.head;

         // Case1 트리에 아무것도 없을 떄
         if (this.head == null) {
             return false;
         }
         // Case2. 트리에 노드가 하나만 있고 해당 노드가 삭제할 노드일 떄
         if (this.head.value == data && this.head.left == null && this.head.right == null){
             this.head = null;
             return true;
         }
         // 삭제할 노드를 만나는 과정
         while (currNode != null){
             // 삭제할 노드를 만났으면 searched를 true로 바꾸고 반복문 break;
             if (currNode.value == data) {
                 searched = true;
                 break;
             }
             if (currNode.value > data) {
                 parentNode = currNode;
                 currNode = currNode.left;
             }
             else {
                 parentNode = currNode;
                 currNode = currNode.right;
             }
         }
         if (searched == false) {
             return searched;
         }
         // Case3. 삭제할 노드가 리프노드(자식이 없는경우)
         if (currNode.left == null && currNode.right == null && data < parentNode.value){
             parentNode.left = null;
             currNode = null;
             return true;
         }
         if (currNode.left == null && currNode.right == null && data > parentNode.value){
             parentNode.right = null;
             currNode = null;
             return true;
         }
         // Case4. 삭제할 노드가 자식이 한개인 경우
         // 그 한개가 왼쪽 자식 노드일 경우
         if (currNode.left != null && currNode.right == null && parentNode.value > data ) {
             parentNode.left = currNode.left;
             currNode = null;
             return true;
         }
         if (currNode.left != null && currNode.right == null && parentNode.value < data ) {
             parentNode.right = currNode.left;
             currNode = null;
             return true;
         }
         // 그 한개가 오른쪽 자식 노드일 경우
         if (currNode.left == null && currNode.right != null && parentNode.value > data) {
             parentNode.left = currNode.right;
             currNode = null;
             return true;
         }
         if (currNode.left == null && currNode.right != null && parentNode.value < data) {
             parentNode.right = currNode.right;
             currNode = null;
             return true;
         }
         //Case5-1 삭제할 노드가 자식이 두개인데 자식에게 자식이 없는경우
         // Case5. 삭제할 노드가 자식이 두개인 경우
         Node changeNode = currNode.right;
         Node changeParentNode = currNode.right;

         while (changeNode.left != null) {
             changeParentNode = changeNode;
             changeNode = changeNode.left;
         }
         if (changeNode.right != null) {
             changeParentNode.left = changeNode.right;
         }
         if (changeNode.right == null){
             changeParentNode.left = null;
         }
         if (currNode.left != null && currNode.right != null && parentNode.value > data) {
             parentNode.left = changeNode;
             if (currNode.right.right == null){
                 changeNode.left = currNode.left;
                 currNode = null;
                 return true;
             }
             changeNode.right = currNode.right;
             changeNode.left = currNode.left;
             currNode = null;
             return true;
         }
         else {

             parentNode.right = changeNode;
             if (currNode.right.right == null){
                 changeNode.left = currNode.left;
                 currNode = null;
                 return true;
             }
             changeNode.right = currNode.right;
             changeNode.left = currNode.left;
             currNode = null;
             return true;
         }
     }

    public static void main(String[] args) {
        BinaryTree myTree = new BinaryTree();
        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(myTree.delete(18));
    }
}

삽입과 조회는 금방 구현 했는데 삭제 기능만 하는데 3시간이 걸렸다. 

 

삭제할 노드의 자식이 두개이면서 그 자식이 아무런 자식을 갖고 있지 않을 경우를 예외처리 해주는 로직을 짜느라 오래걸렸다.

 

다른 이진 검색트리 구현 방법도 보고 수정해봐야겠다.