16 이진 검색 트리

16.1 트리란?

  이진 검색 트리는 이진 트리의 한 종류이고, 이진 트리는 트리 자료 구조의 한 종류이다. 그렇다면 트리란 무엇일까?

트리란, 연결 리스트처럼 노드로 이루어진 데이터 구조이다. 하지만 연결 리스트와 다르게 부모-자식 관계를 가진다. 리스트는 선형 자료 구조이다. 말 그대로 하나의 줄로 이어져 있는 것처럼 보인다. 하지만 트리는 여러 갈래의 줄로 연결될 수 있기 때문에 비선형 자료 구조이다. 주의해야 할 점은 노드들이 자신보다 더 낮은 곳에 있지 않은 다른 노드를 가리키는 경우에는 트리 자료 구조가 아니다. 즉, 노드가 형제 노드를 가리키는 경우, 자식이 부모를 가리키는 경우에는 트리 자료 구조가 아니다. 트리에서는 모든 노드들이 루트노드에서 멀어지는 방식으로 연결된다. 루트는 하나이어야 하고 루트가 두 개인 경우에는 트리 자료 구조가 아니다. 즉, 출발점은 루트 단 하나다. 운영체제에서 폴더가 생성되는 방식을 떠올린다면 쉽게 이해할 수 있다.

 

※용어 정리

1) 루트 - 트리의 꼭대기에 있는 유일한 노드를 일컫는 말

2) 시빌링 - 같은 부모를 가지는 노드들을 일컫는 말

3) 리프 - 자식이 없는 노드를 일컫는 말

4) 간선 - 연결을 의미하는 용어

 

16.2 이진 검색 트리

  위에서 언급했듯이 트리의 한 종류로 이진 트리가 있다. 트리 데이터 구조는 많은 유형이 있지만 트리이기 때문에 기본적인 규칙은 동일하다. 다만 종류에 따라 조금씩 추가되는 규칙이 존재할 뿐이다. 그 중에서 이진 트리는 각 노드가 최대 두 개의 자식 노드를 가져야 한다는 특별한 조건이 추가된 트리의 종류이다. 이진 검색 트리는 위의 특성들에서 특별한 규칙이 더 추가된 자료 구조이다. '부모 노드의 왼쪽에 있는 모든 노드는 언제나 부모 노드보다 작은 값을 가지고 부모 노드보다 오른쪽에 있는 모든 노드는 언제나 부모보다 큰 값을 갖는다' 라는 규칙이 추가된다. 이진 검색 트리는 특정 데이터를 검색하는데 아주 효율적이다. 그리고 데이터를 추가하는 것과 노드의 알맞은 자리를 찾는 것도 용이하다.

트리	-노드들 사이에 부모-자식 관계를 갖는다. -부모 노드만이 자식 노드를 가리킨다. -루트는 하나이어야 한다.  -모든 노드들이 루트노드에서 멀어지는 방식으로 연결된다.
이진 트리	-트리의 특성 -각 노드가 최대 두개의 자식 노드를 가질 수 있다.
이진 검색 트리	-트리의 특성 -이진 트리의 특성 -부모노드 왼쪽은 더 작은 값, 오른쪽은 더 큰 값으로 연결

 

16.3 이진 검색 트리 & 노드 클래스

  노드는 왼쪽과 오른쪽을 가리키는 프로퍼티와 값을 가리키는 프로퍼티로 구성되며, 이진 검색 트리는 루트 프로퍼티를 만들어 루트 노드를 저장해 준다. 다시 말하지만 루트 노드는 하나만 존재해야 한다.

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
}

16.4 Insert 메서드

  Insert 메서드는 새로운 노드를 만들어서 이진 검색 트리 내에 알맞은 자리에 노드를 저장하는 기능을 한다. 일반적으로 데이터가 숫자인 경우에 이진 검색 트리를 많이 사용한다. 

 

◎수도코드

1) 새로운 노드를 만든다.

2) 이진 검색 트리에 루트 노드가 있나 확인한다.(없다면 루트 노드가 되면 된다)

3) 그게 아니라면, 새로운 노드의 값이 루트의 값보다 큰지 작은지 확인해야 한다.

4) 그리고 그 결과에 따라서 더 크다면 노드의 오른쪽에 값이 있나 확인한다.

5) 오른쪽 노드에 값이 있다면 새로운 노드와 비교하고 작다면 왼쪽으로, 크다면 오른쪽으로 이동하여 노드가 있나 확인한다.

6) 이러한 과정을 반복하여 더 이상 비교할 노드가 없는 자리에 도착하면 값을 저장한다.

 

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        
        var current = this.root;
        while(true){
            if(value === current.value) return undefined; // 이미 있는 값을 받아버리면 무한 루프에 빠짐
            //그래서 이걸 만들어 줘야 함(아래 조건문은 큰지 작은지만 비교하므로)
            
            if(value < current.value){
                if(current.left === null){ // 값이 없는 경우
                    current.left = newNode;
                    return this;
                }
                current = current.left; // 값이 있는 경우 포인터 이동
            } else {
                if(current.right === null){ // 값이 없는 경우
                    current.right = newNode;
                    return this;
                } 
                current = current.right; // 값이 있는 경우 포인터 이동
            }
        }
    }

16.5 Find or Search 메서드

  Find or Search 메서드는(이름은 중요하지 않음) 이진 트리를 가지고 인수로 받은 값이 트리에 있는지 검색하는 기능을 한다. 이 과정은 이진 검색 트리에서의 새로운 값의 삽입 과정과 아주 비슷하다.

 

◎수도코드

1) 루트 노드가 있나 확인한다.(루트가 없다면 바로 없다는 표현을 반환해주면 된다.)

2) 루트 노드가 있다면 확인하고자 하는 값과 루트의 값이 동일한지 확인한다.(동일하다면 끝)

3) 그게 아니라면 값이 더 큰지 작은지 확인한다.

4) 확인 후, 왼쪽 혹은 오른쪽에 노드가 있는지 확인하고, 값이 일치하는지 확인한다.

5) 이 과정을 반복한다.

 

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
    insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        
        var current = this.root;
        while(true){
            if(value === current.value) return undefined; // 이미 있는 값을 받아버리면 무한 루프에 빠짐
            //그래서 이걸 만들어 줘야 함(아래 조건문은 큰지 작은지만 비교하므로)
            
            if(value < current.value){
                if(current.left === null){ // 값이 없는 경우
                    current.left = newNode;
                    return this;
                }
                current = current.left; // 값이 있는 경우 포인터 이동
            } else {
                if(current.right === null){ // 값이 없는 경우
                    current.right = newNode;
                    return this;
                } 
                current = current.right; // 값이 있는 경우 포인터 이동
            }
        }
    }

    find(value){
        if(this.root === null) return false;
        var current = this.root
        var found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                found = true;
            }
        }
        if(!found) return undefined;
        return current;
    }
}

16.6 이진 검색 트리 빅오 표기법(가장 좋은 상황 & 평균적인 상황)

1) Insertion - O(log N)

2) Searching - O(log N)

주의 해야할 점은 최악의 경우에는 O(N) 시간 복잡도를 가질 수도 있다.(ex) 한 줄로만 쭉 노드들이 이어지는 경우) 이러한 경우에는 차라리 연결 리스트가 더 적합하다.