이진 탐색 트리(BST) 알고리즘

 

개요

 이진 트리는 비선형 자료 구조에 속하며 부모 노드에 붙는 자식 노드가 최대 2인 구조이다. 각 노드마다 값이 존재하고 한 노드의 왼쪽 서브트리에는 자신보다 작은 값들만 위치하며, 한 노드의 오른쪽 서브트리에는 자신보다 큰 값들만 위치한다는 특징이 있다.

 

삽입

 이진 트리에서 삽입 연산은 현재 노드의 값과 새로 들어올 노드의 값을 비교한다. 현재가 더 크면 새로 들어올 노드는 현재 노드의 왼쪽 서브 트리에 놓게 된다. 이때 현재 노드의 왼쪽 자식 값이 null이면 새로 들어올 노드를 현재 노드의 왼쪽 자식에 삽입하고 null이 아니면 왼쪽 자식 노드에서 위의 연산을 반복하여 자리를 찾아간다. 

 반대로 현재가 작은 경우에는 오른쪽 서브 트리에 놓게 되며 위와 비슷한 과정을 거치며 자리를 찾아서 삽입해준다.

 

검색

 이진 트리의 검색 연산은 사실 위의 삽입 연산과 매우 유사하다. 현재 노드의 값과 검색할 자료의 값(편의상 key로 부르겠다)을 비교한다. key값이 작은 경우에는 왼쪽 서브 트리로 이동하고 큰 경우에는 오른쪽 서브 트리로 이동한다. 서브 트리에서도 값 비교를 key값과 현재의 노드의 값이 같을때까지 반복해가면서 찾는다.

 

삭제 

 삭제 연산은 위의 연산들에 비해서 복잡한 편이다. 삭제할때는 3가지의 경우의 수를 생각해야한다.

1.지우고자 하는 노드의 자식 노드가 둘 다 없는 경우

2.지우고자 하는 노드의 자식 노드가 하나만 있는 경우

3.지우고자 하는 노드의 자식 노드가 둘 다 있는 경우

가 된다.

 

1. 지우고자 하는 노드의 자식 노드가 둘 다 없는 경우

이 경우에는 간단하게 현재 자리에 null을 넣어주면 깔끔하게 해결된다.

2.지우고자 하는 노드의 자식 노드가 하나만 있는 경우

해당 노드를 삭제하고 그 부모랑 자신의 자식 노드를 연결해준다.

3.지우고자 하는 노드의 자식 노드가 둘 다 있는 경우

이 경우에 해결가능한 방법이 두 가지가 있다고 한다. 왼쪽 서브 트리에서 가장 큰 값을 현재 노드에 삽입해주거나 오른쪽 서브 트리에서 가장 작은 값을 현재 노드에 삽입해주면 된다. 보통은 후자를 많이 사용한다.

 

위와 같은 트리를 구성하고 삭제 연산을 직접 해보자.

Node 클래스 source

public class Node {
    public Node left;//왼쪽 노드
    public Node right;//오른쪽 노드
    public Chicken chicken;

    public Node(Chicken chicken){//생성자
        this.chicken = chicken;
    }

    public void add(Chicken chicken){//삽입 연산
        if(this.chicken.id > chicken.id){//현재 노드와 들어올 노드 값 비교시 현재가 크면
            if(this.left == null) this.left = new Node(chicken);//왼쪽 노드에 삽입
            else this.left.add(chicken);//만약 이미 왼쪽 노드에 무언가가 있다면 왼쪽 서브트리에서 위의 연산 반복
        } else{//현재가 작으면 오른쪽 서브 트리에 해당
            if(this.right == null) this.right = new Node(chicken);//오른 노드가 null이면 그 자리에 삽입
            else this.right.add(chicken);//null이 아니면 오른쪽 서브 트리에서 위의 연산 반복
        }
    }
    public void del(Node parent,int id){
        if(this.chicken.id == id){//삭제해야할 노드가 지금의 노드인 경우
            if(this.left == null && this.right == null){//자식 노드가 둘다 없으면
                if(this.chicken.id > parent.chicken.id){//부모의 오른쪽 노드면
                    parent.right = null;//부모의 오른쪽 노드 삭제
                }else//부모의 왼쪽 노드면
                    parent.left = null;//부모의 왼쪽 노드 삭제
                return;
            }
            if(this.left == null){//왼쪽 자식은 없고 오른쪽 자식이 있는 경우
                if(this.chicken.id > parent.chicken.id){
                    parent.right = this.right;
                }else{
                    parent.left = this.right;
                }
                return;
            }else if(this.right == null){//왼쪽 자식이 있고 오른쪽 자식은 없는 경우
                if(this.chicken.id > parent.chicken.id){
                    parent.right = this.left;
                }else{
                    parent.left = this.left;
                }
                return;
            }
            //자식이 둘 다 있는 경우
            //오른쪽 서브 트리에서 가장 작은 값을 찾아서 원래 값에 넣어줄 예정
            Node temp = getMin(this.right);//가장 작은값을 가진 Node 임의로 생성
            if(this.chicken.id > parent.chicken.id){//오른쪽 노드면
                parent.right = temp;//부모의 오른쪽에 오른쪽 서브트리에서 가장 작은 값을 받아와 삽입
            }else{//왼쪽 노드면
                parent.left = temp;//부모의 왼쪽에 가장 작은 값 삽입
            }
            temp.left = this.left;//temp의 왼쪽 노드에 현재 노드의 왼쪽 노드를 삽입

        }else if(this.chicken.id > id){//삭제해야할 노드가 왼쪽 서브트리일떄
            this.left.del(this,id);
        }else//삭제해야할 노드가 오른쪽 서브트리일때
            this.right.del(this,id);

    }
    private Node getMin(Node right) {
        Node parent = right;//오른쪽 서브트리에서 탐색이므로 둘다 right로 초기화
        Node current = right;

        while (current.left != null) {//작은 값은 왼쪽에 위치하므로 왼쪽 마지막에 위치한 값을 찾아야함
            parent = current;
            current = current.left;
        }

        parent.left = null;
        return current;//찾은 값을 return
    }

    public Node search(int id){//검색 연산
        if(this.chicken.id == id) return this;//현재의 값과 찾아야하는 값이 같으면 return
        if(this.chicken.id > id){//현재가 크면
            return this.left.search(id);//왼쪽 서브 트리에서 반복
        }else{//현재가 작으면
            return this.right.search(id);//오른쪽 서브 트리에서 반복
        }

    }
    @Override
    public String toString(){
        return String.format("%s(%d) %d원",this.chicken.menu,this.chicken.id,this.chicken.price);
    }

}

Chicken class source

public class Chicken {
    public int id;
    public String menu;
    public int price;

    public Chicken(int id,String menu,int price){//생성자
        this.id = id;
        this.menu = menu;
        this.price = price;
    }



    public void fry(){
        System.out.println(this.menu+"("+this.id+") "+"치킨을 튀긴당");
    }
    public void delivery(){
        System.out.println(this.menu+"("+this.id+") "+"배달중입니다");
    }


}

App class source

public class App {
    public static void main(String[] args) {
        Node root = new Node(new Chicken(8,"스노윙치킨",18000));
        root.add(new Chicken(13,"맛초킹",17000));
        root.add(new Chicken(5,"붐바스틱",21000));
        root.add(new Chicken(24,"허니콤보",18000));
        root.add(new Chicken(6,"핫갈비천왕",18000));
        root.add(new Chicken(10,"자메이카",21000));
        root.add(new Chicken(9,"레드콤보",16000));
        root.add(new Chicken(12,"김치킨",19000));

        root.del(null,5);
        root.del(null,10);
        //   Node search = root.search(6);
        //   System.out.println(search);
    }
}

main에서 위와 같은 연산을 한다면

5가 사라지면서 8의 왼쪽 자식에 6이 붙고 10이 있던 곳에 10의 오른쪽 서브트리에서 가장 작은 값인 12가 들어오게 된다. 디버깅해서 확인해본 결과

보기 불편하지만 8의 왼쪽 자식에 6이 단말 노드로 존재하고 오른쪽 자식에 13이 13의 왼쪽에는 12가 오른쪽에는 24가 위치한다. 다시 12의 왼쪽 자식으로 9를 가진걸 확인이 가능하다.

 

*참고 사이트

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC

이진 탐색 트리 - 위키백과, 우리 모두의 백과사전

https://mattlee.tistory.com/30

<이진 탐색트리> 탐색, 삽입, 삭제 알고리즘 및 시간복잡도 분석

https://swalloow.tistory.com/35

JAVA의 BinarySearchTree