[자료구조] 이진탐색트리의 개념과 구현(Java)

이진 탐색트리(Binary Search Tree)

• 이진 탐색트리는 이진 트리의 종류로
• 부모노드의 오른쪽자식은 자신보다 크고
• 왼쪽자식은 자신보다 작다
• 연결리스트로 표현한다.

이진 탐색트리 연산

• 삭제
• 삽입
• 삭제

이진 탐색트리의 탐색

만약 15라는 수를 찾는다면

 

root node 부터 탐색한다. 비교하는 수와 현재 노드의 수를 비교해 크면 오른쪽 작으면 왼쪽에서 찾는다.

 

15는 10보다 크므로 오른쪽으로 간다. 

 

15는 20보다 작으므로 왼쪽으로 간다.

 

15를 찾았으므로 true 반환 만약 못찾으면 null을 만나므로 false 반환

이진 탐색트리의 삽입

 

• 삽입은 무조건 맨아래 노드에 삽입한다
• 어디에 삽입할지는 이진 탐색을 통해 이루어진다

위 예시에서 13을 삽입하고 싶으면 우선 13이 어디에 삽입 해야하는지 탐색해야한다.

 

탐색 연산을 이용해서 13의 위치를 찾는다.

 

탐색 결과 15의 왼쪽 노드의 위치가 적합하다.

 

이러면 이진탐색트리를 유지하면서 삽입 연산이 가능하다.

 

 

이진 탐색 트리의 최댓값 최소값

• 이진탐색 트리의 특징으로 인해 최대값은 제일 오른쪽 자식 노드
• 최소값은 제일 왼쪽 자식 노드이다

이진 탐색 트리의 삭제

• 이진 탐색의 삭제는 어렵다
• 일단 삭제하고자하는 노드를 찾는다
• 찾고 경우를 나눈다
  • 찾은 노드가 자식이 없는 경우
  • 자식이 1개있는 경우
  • 자식이 2개있는 경우
• 자식이 없는 경우는 찾은 노드의 부모에 NULL 찾은 노드 free
• 자식이 1개 있는 경우는 찾은 노드의 부모가 1개를 가리키고 찾은노드는 free
• 자식이 2개있는 경우는 자신 보다 큰 노드들 중 제일 작은 값과 교환후 재귀호출
  • 만약 1개만 있는 경우 그런 예외는 따로 조건식으로 처리
• 주의) 찾은 노드가 첫 루트노드일 경우를 생각을 해야한다

 

1)위 예시에서 8을 삭제한다고 하면(자식이 없는 경우)

 

탐색 연산으로 8을 찾아내고 8을 없엔다. 그 후 부모노드인 6노드의 오른쪽 연결을 끊는다.

 

 2) 20을 없엔다고 하면 (자식이 1개 있는 경우)

탐색으로 20을 찾고 1개 있는 자식 노드를 찾는다.

 

그리고 부모 노드의 오른쪽 자식의 자리에 15를 넣는다.

 

 

3) 10을 삭제 해보자 (자식이 2개 있는 경우)

 

이진 탐색트리를 유지하기 위해서는 10대신 10노드 위치에 올 노드를 찾아야한다.

 

위 트리 숫자를 나열해보면 3 6 10 13 15 이다 이중 대체하기 적합한 노드는 6아니면 13일 것이다.

 

그럼 여기서 선택을 해보자 이 예시에서는 13을 선택을 해보겠다. (13이 적합한지 어떻게 알까?)

 

트리를  전부 탐색하고 그 중 10보다 큰 숫자 중 제일 작은 값을 찾을 수 있다(매우 비효율적)

 

위에서 설명했듯이 이진탐색 트리중 제일 최솟값은? 제일 왼쪽 노드 값이다.

 

10보다 큰 노드가 모여있는 트리는 위 그림의 오른쪽 트리이다.

 

이 서브 트리중 제일 왼쪽노드가 10보다 크면서 제일 작은 값이다.

 

이 상태에서 재귀호출로 10을 삭제 (자식이 없거나 1개있는 노드 삭제 연산)을 사용하여 삭제 할 수 있다.

 

 

이진 탐색 트리 연산 수행시간

이진탐색트리는 탐색 연산이 O(logn)의 수행시간이 걸리므로 매우 효율적이다.
다른 삭제 삽입 연산도 탐색 연산 후 위치 재조정만 하면 되므로 O(logn)의 수행시간이 걸린다. 

 

하지만 이진 탐색 트리는 균형이 매우 중요하다

 

삽입 순서를 3 6 10 13 15이렇게 삽입하면 이런식의 균형이 안잡혀 있는 트리가 나오고

 

이때 연산의 수행시간은 O(N)의 수행시간이 나온다.

 

이런 단점을 해결하기 위해 AVL트리 , 레드- 블랙 트리 등이 사용될 수 있다.(이는 나중에 다루도록 하겠다.)

 

구현 (Java)

public class BinarySearchTree {
    static class Node{
        public int data;
        public Node left;
        public Node right;
        public Node(int data){
            this.data = data;
            this.left = null;
            this.right = null;
        }

    }
    private Node root;
    private Node cur;
    private Node pre;
    public BinarySearchTree(){
        root = null;
        cur = null;
        pre = null;
    }
    public boolean Search(int data){
        if (root == null) {
            return false;
        }
        else{
            cur = root;
            pre = null;
            while (cur != null) {
                if (cur.data > data) {
                    pre= cur;
                    cur = cur.left;
                }
                else if(cur.data < data){
                    pre = cur;
                    cur = cur.right;
                }
                else{
                    break;
                }
            }
            if (cur == null) {
                return false;
            }
            else{
                return true;
            }
        }
    }
    public void Insert(int data){
        Node newnode = new Node(data);
        newnode.data = data;
        if (root == null) {
            root = newnode;
            return;
        }
        else{
            if (Search(data)){
                System.out.println("중복된 데이터"+data);
                return;
            }
            else{
                if (pre.data > data){
                    pre.left = newnode;
                }
                else{
                    pre.right = newnode;
                }
            }
        }
    }
    public void Delete(int data){
        if (root == null) {
            System.out.println("값이 없음");
            return;
        }
        else{
            if (Search(data)){
                if (cur.left == null && cur.right == null) {
                    if (root == cur){
                        root = null;
                        cur = null;
                        return;
                    }
                    if (pre.left == cur){
                        pre.left = null;
                        cur = null;
                    } else if (pre.right == cur) {
                        pre.right = null;
                        cur = null;
                    }
                    return;
                }
                if (cur.left == null || cur.right == null){
                    if (cur == root){
                        if (cur.left != null){
                            root = cur.left;
                            cur = null;
                            return;
                        }
                        else{
                            root = cur.right;
                            cur = null;
                            return;
                        }
                    }
                    if (cur.left != null) {
                        if (pre.left == cur) {
                            pre.left = cur.left;
                        }
                        else{
                            pre.right = cur.left;
                        }
                    }
                    else{
                        if (pre.left == cur) {
                            pre.left = cur.right;
                        }
                        else{
                            pre.right = cur.right;
                        }
                    }
                    cur = null;
                    return;
                }
                if (cur.left != null && cur.right != null) {

                    Node temp = cur;
                    pre = cur;
                    cur = cur.right;
                    while (cur != null) {
                        pre = cur;
                        cur = cur.left;
                    }
                    int t = pre.data;
                    this.Delete(pre.data);
                    temp.data = t;
                    pre = null;
                    return;

                }

            }
            else{
                System.out.println("값을 못찾음");
                return;
            }
        }

    }

    public Node getRoot() {
        return root;
    }
    public void Inorder(Node temp){
        if(temp == null){
            return;
        }
        else{
            Inorder(temp.left);
            System.out.print(temp.data + "->");
            Inorder(temp.right);
            return;
        }
    }



}