[알고리즘👽] 16. 이진 검색 트리

해당 포스팅은 알고리즘 이진 검색 트리에 대해 다룹니다. Udemy JavsScript 알고리즘 & 자료구조 마스터 클래스를 공부하며 정리한 내용입니다.

트리 소개

트리는 연결 리스트보다는 약간 더 상위 단계이고 더 복잡하다.

목표

• 트리 정의
• 트리, 연결 리스트, 배열 비교
• 여러 가지 종류의 트리의 차이점 설명
• 이진 탐색 트리에 대해 사용되는 동작 코딩

트리란?

연결 리스트처럼 노드로 이루어진 데이터 구조이다. 해당 노드사이에 부모- 자신 관계가 존재한다.

리스트는 선형 구조(linear), 트리는 비선형 구조이다(nonlinear)

노드는 형제 관계의 노드를 가리킬 수 없다. 무조건 부모-자식만 가능하다. 출발 지점은 단 하나여야한다.

트리 용어

• Root - 트리 노드의 가장 위
• Child - 루트에서 멀어지는 방향으로 연결된 노드
• Parent - 자식의 반대 개념
• Siblings - 같은 부모를 가지는 노드를 뜻한다.
• Leaf - 자식이 없는 노드
• Edge - 한 노드에서 다른 노드로 향하는 화살표

트리사용

사용처

• HTML DOM
• 네트워크 라우팅
• 추상 구문 트리
• 인공지능
• 운영 체제에서 폴더
• Json

이진 트리 소개

트리 종류

• 트리
• 이진 트리 - 각 노드가 최대 두 개의 자식을 가짐
• 이진 탐색 트리
  • 데이터가 순서대로 정리됨
  • 부모 노드의 왼쪽에 있는 모든 노드는 언제나 부모보다 작다
  • 부모 노드보다 오른쪽에 있는 모든 노드는 부모보다 크다

이진 검색 트리 찾기

Why

무언가를 찾아보는 것을 아주 빠르고 쉽게 만들어준다. 무언가를 추가하는 것과 노드의 자리를 찾는 것도 쉽게 해준다. 그래서 이진 탐색 트리에서 무언가 찾는 것은 정렬되지 않은 트리와 비교하면 매우 빠르다. 기본적으로 매번 비교할 때마다 우리가 봐야하는 숫자가 반으로 줄어든다.

트리 클래스

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

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

var tree = new BinarySearchTree();
tree.root = new Node(10);
tree.root.right = new Node(15);
tree.root.left = new Node(7);
tree.root.left.right(8);

이진 검색 트리 : Insert

의사코드

새로운 노드를 만들어서 제대로 된 자리에 그 노드를 놓습니다.

솔루션

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

의사코드

솔루션

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,
            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;
    }
    contains(value){
        if(this.root === null) return false;
        var current = this.root,
            found = false;
        while(current && !found){
            if(value < current.value){
                current = current.left;
            } else if(value > current.value){
                current = current.right;
            } else {
                return true;
            }
        }
        return false;
    }
}

//      10
//   5     13
// 2  7  11  16

var tree = new BinarySearchTree();
tree.insert(10)
tree.insert(5)
tree.insert(13)
tree.insert(11)
tree.insert(2)
tree.insert(16)
tree.insert(7)

이진 검색 트리 빅오 (Big O)

Insertion	O(log n)
Searching	O(log n)

항상 그렇지만은 않다.