[자료 구조] - 트리 자료 구조 (4)-이진 탐색 트리 자바로 구현하기 :: Binary Search Tree implementation by java

이진 탐색 트리를 이해하기 위해서는 트리에 대한 기본 개념 및 용어 와 이진 트리의 종류와 기본에 대한 지식이 있어야 원활한 이해가 가능하니 아직 이해가 부족한 사람들은 꼭 한 번 가볍게 읽고 오는 것을 추천한다.

이진 탐색 트리 Binary Search Tree

이진 탐색 트리는 다음과 같은 조건을 만족하는 이진 트리를 Binary Search Tree라고 한다.

기본 전제 : 트리의 키에는 값이 반드시 존재하며 값들은 비교할 수 있는 집단이 존재하는 전순서 여야 한다.

• 조건 1 : 어떤 노드 N을 기준으로 왼쪽 서브 트리 노드의 모든 키 값은 노드 N의 키 값 보다 작아야 한다.
• 조건 2 : 오른쪽 서브 트리 노드의 키 값은 노드 N의 키 값보다 커야 한다.
• 조건 3 : 같은 키의 값을 갖는 노드는 존재하지 않는다.

조건을 간단하게 정리하자면 한 노드가 있을 때 해당 노드보다 작으면 왼쪽, 크면 오른쪽으로 배치가 된 것들이 이진 탐색 트리(BST)가 된다는 것이다.

이제 간단하게 왜 이진 탐색 트리를 사용하는지에 대해서 알아보자면

이런 이진 탐색 트리가 존재한다고 해보자.

 

이 탐색 트리를 중위 연산으로 하면 키 값의 오름 차순으로 간단한 구조로 노드를 얻을 수 있게 된다.

 

이 것을 실제로 구현해보며 이해해보자.

이진 탐색 트리 만들기

이진 탐색 트리를 만들기 위해서는 연결 리스트를 활용해야 한다.

 

연결 리스트에 대한 정보를 얻고 싶다면 연결 리스트로 가서 가볍게 읽고 오는 것을 추천한다.

노드 클래스 만들기

BST의 개별 노드를 나타내는 것이 바로 Node클래스 이다. 이는 다음과 같이 3개의 필드로 구성된다.

• data : 노드가 갖는 실질적 데이터
• left : 노드의 왼쪽 자식
• right : 노드의 오른쪽 자식

Node<K, V>

이제 노드 클래스를 만들었으므로 노드의 생성자와 getter/setter 메서드를 추가한 클래스를 만들어보자.

public class BinarySearchTree {

    public class Node {

        public Node root;

        private int data;
        private Node left;
        private Node right;

        /* 생성자 */
        public Node(int data){
            this.setData(data);
            setLeft(null);
            setRight(null);
        }


        /* 각종 getter / setter */
        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }

        /*탐색 연산*/
        public boolean find(int key){
            Node currentNode = root;
        }
    }

    public Node root; // bst의 루트 노드

    public BinarySearchTree(){ // bst 생성자
        root = null;
    }

}

이제 기본적인 트리 노드를 만들었으니 이진 탐색 트리가 되기 위한 삭제와 삽입 연산에 대해서 구현하기 전에 필수적으로 구현을 해야 하는 것이 있다. 바로 탐색 연산인데, 삭제나 삽입은 모두 탐색의 과정을 거친 후에 이루어지므로 먼저 탐색을 시작해보자.

탐색 연산

탐색연산에서 중요한 점은, 바로 BST의 특성(왼쪽 자식 노드의 값은 현재 노드보다 항상 작아야한다)과 (오른쪾 자식 노드의 값은 현재 노드의 값 보다 항상 커야 한다.)라는 특징을 만족한다고 가정하고 연산을 한다는 것이다.

/*탐색 연산*/
    public boolean find(int key){
        Node currentNode = root;
        while(currentNode != null){
            // 현재 노드와 찾는 값이 같으면
            if(currentNode.getData() == key){
                return true;
            }else if(currentNode.getData() > key){ // 찾는 값이 현재 노드보다 작으면
                currentNode = currentNode.left;
            }else {// 찾는 값이 현재 노드보다 크면
                currentNode = currentNode.right;
            }
        }
        return false;
    }

삽입 연산

삽입 연산에서 가장 먼저 하는 일은 root노드가 존재하는지 확인하는 것이다.

root노드가 존재하지 않는다는 소리는 해당 트리의 노드가 없다는 뜻이므로 새로운 newNode를 root노드로 만들어주고 return을 한다.

그렇지 않다면 노드의 값을 비교해서 클 때와 작을 때 서로 비교한 뒤, 자리에 알맞는 노드에 삽입하면 된다.

/*삽입 연산*/
    public void insert(int data) {
        Node newNode = new Node(data); // 왼쪽, 오른쪽 자식 노드가 null 이며 data 의 값이 저장된 새 노드 생성
        if(root == null){// 루트 노드가 없을때, 즉 트리가 비어있는 상태일 때,
            root = newNode;
            return;
        }
        Node currentNode = root;
        Node parentNode = null;

        while(true) {

            parentNode = currentNode;

            if(data < currentNode.getData()) { // 해당 노드보다 클 떄.
                currentNode = currentNode.getLeft();
                if(currentNode == null) { // 더 이상 자식 노드가 없을 때, 즉 삽입 할 수 있는 때
                    parentNode.setLeft(newNode);
                    return ;
                }
            }else { // 해당 노드보다 작을 때.
                currentNode = currentNode.getRight();
                if(currentNode == null){ // 더 이상 자식 노드가 없을 때, 즉 삽입 할 수 있는 때
                    parentNode.setRight(newNode);
                    return ;
                }
            }
        }
    }

삭제 연산

삭제 연산은 조금 까다로운 부분이 있다.

우리가 만약 자식이 모두 있는 트리의 노드를 삭제했다고 한다면, 삭제한 노드의 자식들은 어떤 순서에 의해 배치될까?

이것이 모호하기 때문에 우리는 삭제 연산에서 케이스를 나눠서 연산을 한다. 케이스튼 크게 3가지가 있다.

 

1. 자식 노드가 없는 경우
2. 하나의 자식 노드를 갖는 경우
3. 두개의 자식 노드를 갖는 경우

삭제 연산 기본 세팅

/*삭제 연산*/
    public boolean delete(int data){
        Node parentNode = root;
        Node currentNode = root;
        boolean isLeftChild = false;

        while(currentNode.getData() != data) {
            parentNode = currentNode;
            if(currentNode.getData() > data) {
                isLeftChild = true;
                currentNode = currentNode.getLeft();
            }else {
                isLeftChild = false;
                currentNode = currentNode.getRight();
            }
            if(currentNode == null){
                return false;
            }
        }


        if(currentNode.getLeft() == null && currentNode.getRight() == null) { // 1. 자식 노드가 없는 경우
            if(currentNode == root) {
                root = null; // 해당 노드가 root node일 경우
            }
            if(isLeftChild) {
                parentNode.setLeft(null); // 삭제할 노드가 부모 노드의 왼쪽 자식일 경우
            }
            else {
                parentNode.setRight(null); // 삭제할 노드가 부모 노드의 오른쪽 자식일 경우
            }
        } else if(currentNode.getRight() == null){      // 2-1. 자식 노드가 하나인 경우(오른쪽 자식이 없을 때)
            parentNode.setLeft(currentNode.getLeft());
        } else if(currentNode.getLeft() == null) {      // 2-2. 자식 노드가 하나인 경우(왼쪽 자식이 없을 떄)
            parentNode.setRight(currentNode.getRight());
        } else {                                        // 3. 자식이 둘인 경우
                Node minimum = getMinumun(currentNode);
                if(currentNode == root) {
                    root = minimum;
                }else if (isLeftChild){
                    parentNode.setLeft(minimum);
                }else {
                    parentNode.setLeft(currentNode.getLeft());
                }
                minimum.setLeft(currentNode.getLeft());
        }
        return false;
    }

    Node getMinumun(Node deleteNode) {
        Node minimum = null;
        Node minimumParent = null;
        Node currentNode = deleteNode.getRight();
        while(currentNode != null) {
            minimumParent = minimum;
            minimum = minimumParent;
            currentNode = currentNode.getLeft();
        }
        if(minimum != deleteNode.getRight()){
            minimumParent.setLeft(minimum.getRight());
            minimum.setRight(deleteNode.getRight());
        }
        return minimum;
    }

전체 소스 코드

package theory.tree;

import java.util.Scanner;

public class BinarySearchTree {
    public class Node {
        private int data;
        private Node left;
        private Node right;

        /* 생성자 */
        public Node(int data){
            this.setData(data);
            setLeft(null);
            setRight(null);
        }


        /* 각종 getter / setter */
        public int getData() {
            return data;
        }

        public void setData(int data) {
            this.data = data;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }
    public Node root;
    BinarySearchTree(){
        root = null;
    }

    /*탐색 연산*/
    public boolean find(int key){
        Node currentNode = root;
        while(currentNode != null){
            // 현재 노드와 찾는 값이 같으면
            if(currentNode.getData() == key){
                return true;
            }else if(currentNode.getData() > key){ // 찾는 값이 현재 노드보다 작으면
                currentNode = currentNode.getLeft();
            }else {// 찾는 값이 현재 노드보다 크면
                currentNode = currentNode.getRight();
            }
        }
        return false;
    }

    /*삽입 연산*/
    public void insert(int data) {
        Node newNode = new Node(data); // 왼쪽, 오른쪽 자식 노드가 null 이며 data 의 값이 저장된 새 노드 생성
        if(root == null){// 루트 노드가 없을때, 즉 트리가 비어있는 상태일 때,
            root = newNode;
            return;
        }
        Node currentNode = root;
        Node parentNode = null;

        while(true) {

            parentNode = currentNode;

            if(data < currentNode.getData()) { // 해당 노드보다 클 떄.
                currentNode = currentNode.getLeft();
                if(currentNode == null) {
                    parentNode.setLeft(newNode);
                    return ;
                }
            }else { // 해당 노드보다 작을 때.
                currentNode = currentNode.getRight();
                if(currentNode == null){
                    parentNode.setRight(newNode);
                    return ;
                }
            }
        }

    }

    /*삭제 연산*/
    public boolean delete(int data){
        Node parentNode = root;
        Node currentNode = root;
        boolean isLeftChild = false;

        while(currentNode.getData() != data) {
            parentNode = currentNode;
            if(currentNode.getData() > data) {
                isLeftChild = true;
                currentNode = currentNode.getLeft();
            }else {
                isLeftChild = false;
                currentNode = currentNode.getRight();
            }
            if(currentNode == null){
                return false;
            }
        }


        if(currentNode.getLeft() == null && currentNode.getRight() == null) { // 1. 자식 노드가 없는 경우
            if(currentNode == root) {
                root = null; // 해당 노드가 root node일 경우
            }
            if(isLeftChild) {
                parentNode.setLeft(null); // 삭제할 노드가 부모 노드의 왼쪽 자식일 경우
            }
            else {
                parentNode.setRight(null); // 삭제할 노드가 부모 노드의 오른쪽 자식일 경우
            }
        } else if(currentNode.getRight() == null){      // 2-1. 자식 노드가 하나인 경우(오른쪽 자식이 없을 때)
            parentNode.setLeft(currentNode.getLeft());
        } else if(currentNode.getLeft() == null) {      // 2-2. 자식 노드가 하나인 경우(왼쪽 자식이 없을 떄)
            parentNode.setRight(currentNode.getRight());
        } else {                                        // 3. 자식이 둘인 경우
                Node minimum = getMinumun(currentNode);
                if(currentNode == root) {
                    root = minimum;
                }else if (isLeftChild){
                    parentNode.setLeft(minimum);
                }else {
                    parentNode.setLeft(currentNode.getLeft());
                }
                minimum.setLeft(currentNode.getLeft());
        }
        return false;
    }

    Node getMinumun(Node deleteNode) {
        Node minimum = null;
        Node minimumParent = null;
        Node currentNode = deleteNode.getRight();
        while(currentNode != null) {
            minimumParent = minimum;
            minimum = minimumParent;
            currentNode = currentNode.getLeft();
        }
        if(minimum != deleteNode.getRight()){
            minimumParent.setLeft(minimum.getRight());
            minimum.setRight(deleteNode.getRight());
        }
        return minimum;
    }
}