이진 검색트리(Binary Search Tree) 구현해보기

트리

어떤 계층 구조를 표현하고자 할 때, 트리(Tree)라는 자료구조를 사용할 수 있다.

상위 계층이 아래에 있는 하위 계층들을 포함하며 가지를 치는 모습이 마치 나무와 같다고 하여 트리(Tree)라고 명명되었다 한다.

계층 구조

어떤 데이터로 트리를 구성하느냐, 자료들을 어떻게 배치하느냐에 따라서 다양한 트리를 구성할 수가 있다.

---

트리의 구성요소

트리는 가질 수 있는 데이터(노드)와 노드들을 연결하는 간선으로 구성된다.

노드가 연결되었을 때, 그 두 노드 간에는 상 하 계층 관계가 성립이 되어야 한다.

트리 용어

• 부모 노드(parent node) : 연결된 노드 중 상위 노드
• 하위 노드(child node) : 연결된 노드 중 하위 노드
• 형제 노드(sibling node) : 부모 노드가 같은 노드
• 루트 노드(root node) : 트리에서 최상위 노드
• 잎 노드( 리프 노드, leaf node ) : 자식 노드가 없는 가장 하위의 노드
• 깊이 ( depth ) : 루트에서 특정 노드까지 가는데 거쳐야 하는 간선의 수
• 높이 ( height ) : 루트 노드에서 가장 깊숙이 있는 노드의 깊이

---

이진 검색 트리란?

트리로 구현할 수 있는 형태 중 가장 대표적인 형태인 이진 검색 트리(Binary Search Tree)에 대해서 살펴보고, 자바 코드로 구현해본다.

이진 검색 트리는 정렬된 형태로, 아래와 같은 속성을 가진다.

• 특정 노드의 왼쪽에는 해당 노드의 값보다 작은 값을 가진 노드만을 포함한다.
• 특정 노드의 오른쪽에는 해당 노드의 값보다 큰 값을 가진 노드만을 포함한다.
• 각 왼쪽, 오른쪽 서브 트리들도 각각 이진 검색 트리여야 한다.
• 각 노드들은 유일한 값을 가진다.
• 노드를 최대 2개까지 가질 수 있는 이진트리에서, 위 성질이 추가된 것을 이진 검색 트리라고 한다.

위 특징으로, 특정 값을 검색하는데 굉장히 효율적이다.

완전하게 정렬되어있는 이진 검색 트리라면 특정 원소를 검색하는데 O(logN)의 시간이 걸린다.

하지만, 특정 방향으로 치우쳐져 있는 균형 잡히지 않은 이진트리라면, O(N)의 시간이 걸리게 된다.

---

이진 검색 트리 구현해보기

해당 문서를 참고하여, 이진 검색 트리가 가질 수 있는 삽입, 삭제, 탐색 메서드를 위의 트리 형태로 구현해본다.

https://www.softwaretestinghelp.com/binary-search-tree-in-java/

트리노드(TreeNode) 클래스

트리 노드를 표현하는 TreeNode라는 정적 클래스를 생성한다.

static class TreeNode {
    int value;
    TreeNode left, right;

    TreeNode(int value) {
        this.value = value;
    }
}

• 왼쪽, 오른쪽도 TreeNode 형태로 선언해준다.
• 생성자로 TreeNode를 생성 시 value를 초기화할 수 있도록 한다.

이진 검색 트리 (BinarySearchTree) 클래스

이진 검색 트리 클래스를 구현해본다.

삽입, 삭제 메서드와 검색 작업은 전위, 중위, 후위 순회 메서드로 구현해본다.

• 삽입 : insert 메서드
• 삭제 : delete 메서드
• 순회
  • 전위(preorder)
  • 중위(inorder)
  • 후위(postorder)

기본 구조

• 트리의 가장 상위 노드인 root를 선언한다.
• 생성자에서 이 root를 null로 초기화할 수 있도록 한다.

삽입

• 이진 검색 트리에서 삽입의 구현은 나름 간단하지만, 재귀 방식을 사용하여 조금 난해할 수 있다.
• 해당 과정을 그림으로 그려가며 구현해본다.

public class BinarySearchTree {
    static class TreeNode {
        int value;
        TreeNode left, right;

        TreeNode(int value) {
            this.value = value;
        }
    }

    // 생성, 삭제
    TreeNode root;

    BinarySearchTree() {
        root = null;
    }

    public void insert(int value) {
        root = insert(root, value);
    }

    public TreeNode insert(TreeNode root, int value) {
        if(root == null) {
            root = new TreeNode(value);
            return root;
        }

        if(root.value > value) {
            root.left = insert(root.left, value);
        } else if(root.value < value) {
            root.right = insert(root.right, value);
        }

        return root; // 15를 가리키고 있는 객체 주소
    }
}

• 메서드 오버 로딩을 이용하여, 매개변수 1개짜리 insert와 재귀 작업을 수행할 매개변수 2개짜리 insert 메서드를 생성한다.

• 여기서, 재귀 작업이 어떻게 수행되는지를 알아보겠다.
• 매개변수가 root와 같이 같은 이름으로 넘겨지기 때문에 조금 헷갈릴 수 있다.

---

값을 70 -> 50 -> 90 -> 27 순으로 넣는 삽입 작업이 순서대로 진행된다고 가정한다.

 

1. 우선 BinarySearchTree 클래스를 하나 생성한다. 이 과정에서, root 가 null로 초기화된다.

---

2. 70을 insert 한다. 이 과정에서, root가 null이기 때문에 value가 70을 가지는 새로 TreeNode 객체를 생성하고, 해당 객체가 root를 대체하게 된다. root의 left와 right는 아직 null인 상태이다.

---

3. 추가로 50을 insert 한다.

3-1. root가 역시 가장 첫 insert에서 매개변수로 넘겨진다. 하지만 여기서 root는 null이 아니므로, 아래 비교문을 거치게 된다.

3-2. 추가할 value인 50은 root가 가지고 있는 root.value보다는 작다.

3-3. 따라서 해당 메서드가 수행된다. insert메서드에 root.left과 50을 넘겨서 insert메서드를 재수 행한다. 여기서 root.left는 null이다. 따라서 새로운 TreeNode 객체가 value 50을 가지고 생성되게 되고, 해당 객체가 root.left를 대체하게 된다.

3-4. 그리고 다시 root를 마지막에 리턴하게 된다. 여기서 root는 root.left가 방금 추가된 객체를 가지게 된다.

---

4. 그리고 90을 insert 한다. 위의 과정과 비슷하지만, 다른 조건문을 타게 된다.

4-1. root가 역시 가장 첫 insert에서 매개변수로 넘겨진다. 하지만 여기서 root는 null이 아니므로, 아래 비교문을 거치게 된다.

4-2. 추가할 value인 90은 root가 가지고 있는 root.value 보다 크다.

4-3. 따라서 해당 메서드가 수행된다. insert에 root.right과 90을 넘겨서, insert 메서드를 재수 행한다. 여기서 root.right은 null이다.

따라서 새로운 TreeNode 객체가 value 90을 가지고 생성되게 되고, 해당 객체가 root.left를 대체하게 된다.

4-4. 그리고 다시 root를 마지막에 리턴하게 된다. 여기서 root는 root.right가 방금 추가된 객체를 가지게 된다.

---

5. 마지막으로 27을 insert 해본다.

5-1. root가 역시 가장 첫 insert에서 매개변수로 넘겨진다. 하지만 여기서 root는 null이 아니므로, 아래 비교문을 거치게 된다. ( 70 > 27 ). 추가할 27은 70보다는 작다. 따라서 root.left로 넘겨지게 된다.

5-2. 하지만 여기서의 root.left는 null이 아니다. 따라서, 27과 root.left가 가지고 있는 값을 한번 더 비교한다.( 50 > 27 이 단계 안에서는, 넘어온 root.left가 root가 된다.). 값이 작으므로, 넘어온 root.left의 left가 해당 메서드로 다시 한번 재귀적으로 호출된다. root.left.left라 하겠다.

5-3. root.left.left가 null이기 때문에, 역시 새로 객체가 생성되고 리턴된다.

5-4. root.left.left가 value를 27로 가진 상태로 리턴된다.

5-5. 마지막으로, root.left가 root.left.left를 가지게 되고, root를 마지막으로 리턴한다.

 

이런 식으로, 신규 객체가 추가될 때에는 항상 위에 있는 root == null 구문에서 걸려 리턴되기 때문에, 메서드 가장 마지막에 위치한 return root 구문은 항상 트리의 최상위인 진짜 root(?)를 리턴하는 구문임을 알 수 있다.

---

삭제

• 삽입 과정을 그림으로 그려가며 간단히 알아보았다.
• 삽입보다는 삭제가 추가적인 과정이 있는데, 조금 더 추가되는 부분이 있다.
• 코드는 아래와 같다.

public void delete(int value) {
    root = delete(root, value);
}

public TreeNode delete(TreeNode root, int value) {
    if(root == null) {
        return null;
    }

    if(root.value > value) { // 이동 작업
        root.left = delete(root.left, value);
    } else if(root.value < value) { // 이동작업
        root.right = delete(root.right, value);
    } else { // 삭제 작업
        if(root.left == null) {
            return root.right;
        } else if(root.right == null) {
            return root.left;
        } // 실제로 자식이 없는 경우

        root.value = findMinValue(root.right);
        root.right = delete(root.right, root.value);
    }

    return root;
}

삭제의 종류

우선 이진트리를 삭제하는 경우는 크게 3가지로 구분할 수 있다.

• 자식이 없는 leaf node를 삭제하는 경우
• 자식이 1개인 노드를 삭제하는 경우
• 자식이 2개인 노드를 삭제하는 경우

삭제를 해야 하기 때문에, 값이 트리 내에 존재를 해야 하고, 그 때문에 조건식이 마지막에 하나 추가가 된다.(값이 작지도, 크지도 않은 경우)

---

자식이 없는 leaft node를 삭제하는 경우를 그림으로 살펴본다.

각 메서드가 실행되는 노드의 색깔로 구분하였다.

 

1. 32를 삭제하고자 한다. 가장 먼저 root부터 시작하여, 50과 비교하게 된다.

2. 50보다 값이 작으므로, root.left로 메서드를 재귀적으로 호출한다.

3. 핑크색 root.right는, 여기서는 root.right로 표현되지만 사실은 바로 전 메서드에서 넘어온 root.left의 right이다.

4. 핑크색의 값과 삭제하고자 하는 값이 같게 된다.

} else { // 삭제 작업
    if(root.left == null) {
        return root.right;
    } else if(root.right == null) {
        return root.left;
    } // 실제로 자식이 없는 경우

    root.value = findMinValue(root.right);
    root.right = delete(root.right, root.value);
}

따라서 위 사진에서처럼, 마지막 조건문에 걸리게 된다.

그래서 자식이 한 개도 없는 leaf 노드에서는, 항상 가장 첫 조건(root.left == null)에 먼저 걸리기 때문에, 항상 null이 리턴되게 된다. root.right 가 null이기 때문이다.

 

가장 마지막에 호출된 메서드에서 32 노드가 null로 치환되고, 오른쪽 노드가 null로 치환된 상태로 보라색 27 노드가 치환된다. 그리고 마지막으로 치환된 27 노드를 가지는 root가 반환되게 된다.

---

그렇다면 자식이 1개인 노드의 삭제 작업은 어떨까.

자식이 1개라는 소리는 왼쪽에도 값을 가질 수 있고, 오른쪽에도 값을 가질 수 있다는 의미가 된다.

역시 위와 동일한 과정을 거쳐 재귀 함수를 타게 되고, 역시 삭제할 값을 찾게 되면 동일한 아래 메서드 조건을 만나게 된다.

 

if와 else if 조건에 무조건 걸리게 된다.

} else { // 삭제 작업
    if(root.left == null) {
        return root.right;
    } else if(root.right == null) {
        return root.left;
    } // 실제로 자식이 없는 경우

    root.value = findMinValue(root.right);
    root.right = delete(root.right, root.value);
}

---

자식이 2개 이상인 경우는 조금 복잡하다. 왼쪽에도 자식이 있고, 오른쪽에도 자식이 존재한다.

자식이 2개 이상인 경우의 노드가 삭제될 경우, 오른쪽 서브 트리에서 가장 작은 값을 가지는 노드가 삭제될 값과 변경되어야 한다. 그래야 정상적인 이진 검색 트리가 성립되기 때문이다. 이 과정이 가장 마지막 두 줄에서 수행되게 된다.

삭제할 값을, minValue 메서드를 호출하여 오른쪽 서브 트리에서 가장 작은 값을 찾도록 한다.

가장 작은 값을 찾는 메서드에는 root.right를 넘겨준다. 이 root.right에서부터 시작해서, 왼쪽에 있는 노드들을 value가 null이 아닐 때까지 탐색한다. 그렇게 되면 그 값이 오른쪽 서브 트리에서 가장 작은 값이 된다.

그 리턴되는 값이 root.value로 치환된다.

root.value = findMinValue(root.right);

int findMinValue(TreeNode root) {
    int minValue = root.value;

    while(root.left != null) {
        minValue = root.left.value;
        root = root.left;
    }

    return minValue;
}

 

그리고 마지막으로 최솟값으로 찾은 값을, 오른쪽 서브 트리에서 삭제해주어야 한다.

root.right = delete(root.right, root.value);

위에서 root.value가 오른쪽 서브 트리의 최솟값으로 변경되었기 때문에,

delete 메서드를 동일하게 root.value를 넣어서 수행해주게 되면 해당 값이 삭제되게 된다.

---

순회

순회에는 3가지가 존재한다.

• 전위 ( preorder ) : root -> left -> right 순회한다.
• 중위 ( inroder ) : left -> root -> right 순으로 순회한다.
• 후위 ( postorder ) : left -> right -> root 순으로 순회한다.

---

전위 순회( preorder )

void preorder(TreeNode node) {
    if(node == null) {
        return;
    }

    System.out.println(node.value + " ");
    preorder(node.left);
    preorder(node.right);
}

중위 순회( inorder)

void inorder(TreeNode node) {
    if(node == null) {
        return;
    }

    inorder(node.left);
    System.out.println(node.value + " ");
    inorder(node.right);
}

후위 순회( postorder )

void postorder(TreeNode node) {
    if(node == null) {
        return;
    }

    postorder(node.left);
    postorder(node.right);
    System.out.println(node.value + " ");
}

---

최종 코드

public class BinarySearchTree {
    static class TreeNode {
        TreeNode left, right;
        int value;

        TreeNode(int value) {
            this.value = value;
        }
    }

    TreeNode root;

    BinarySearchTree() {
        root = null;
    }

    public void insert(int value) {
        root = insert(root, value);
    }

    public TreeNode insert(TreeNode root, int value) {
        if(root == null) {
            root = new TreeNode(value);
            return root;
        }

        if(value < root.value) {
            root.left = insert(root.left, value);
        } else if(value > root.value) {
            root.right = insert(root.right, value);
        }

        return root;
    }

    public void delete(int value) {
        root = delete(root, value);
    }

    public TreeNode delete(TreeNode root, int value) {
        if(root == null) {
            return root;
        }

        if(root.value > value) {
            root.left = delete(root.left, value);
        } else if(root.value < value) {
            root.right = delete(root.right, value);
        } else {
            if(root.left == null) {
                return root.right;
            } else if(root.right == null) {
                return root.left;
            }

            root.value = minValue(root.right); // 오른쪽 subtree에서의 최솟값
            root.right = delete(root.right, root.value); // 해당 값을 삭제
        }

        return root;
    }

    int minValue(TreeNode root) {
        int minval = root.value;

        while(root.left != null) {
            minval = root.left.value;
            root = root.left;
        }

        return minval;
    }

    // preorder : root -> left -> right : 전위 순회
    void preorder(TreeNode node) {
        if(node == null) {
            return;
        }

        System.out.print(node.value + " ");

        preorder(node.left);

        preorder(node.right);
    }

    // inorder : left -> root -> right : 중위 순회
    void inorder(TreeNode node) {
        if(node == null) {
            return;
        }

        inorder(node.left);

        System.out.print(node.value + " ");

        inorder(node.right);
    }

    // postorder : left -> right -> root : 후위 순회
    void postorder(TreeNode node) {
        if(node == null) {
            return;
        }

        postorder(node.left);

        postorder(node.right);

        System.out.print(node.value + " ");
    }

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();

        bst.insert(20);
        bst.insert(24);
        bst.insert(7);
        bst.insert(3);
        bst.insert(9);

        System.out.println("--- Preorder ---");
        bst.preorder(bst.root);

        System.out.println("\n--- Inorder ---");
        bst.inorder(bst.root);

        System.out.println("\n--- Postorder ---");
        bst.postorder(bst.root);

        bst.delete(7);

        System.out.println("\n\n< Node 7 삭제 후 >");

        System.out.println("\n--- Preorder ---");
        bst.preorder(bst.root);

        System.out.println("\n--- Inorder ---");
        bst.inorder(bst.root);

        System.out.println("\n--- Postorder ---");
        bst.postorder(bst.root);
    }
}

7 삭제 후 전위, 중위, 후위 순회의 값은 한번 체크해보시길 바랍니다.

위의 설명에서 틀린 부분이나, 잘못된 부분이 있을 수 있으니 있다면 댓글 부탁드립니다.