[자료구조]이진 검색 트리(Binary Search Tree)

✅ 트리(Tree)란?

부모와 자식 관계를 가진 노드로 구성된 데이터 구조이다. 리스트는 선형구조이다. 한 가지가 있고, 그다음에 하나 그다음에 하나 이런 식으로 모든 것이 한 줄로 늘어서 있다. 트리는 비선형구조로 여러 가지들로 뻗을 수 있다. 그리고 트리는 부모가 자식을 가리키는 형태이지 형제를 가리키거나 자식이 부모를 가리키면 안 된다. 

• 루트(Root) - 트리의 최상위 노드.
• 자식(Child) - Root로부터 멀어지는 방향으로 다른 노드와 직접적으로 연결된 노드.
• 부모(Parent) - 자식의 반대 개념.
• 형제(Siblings) - 같은 부모를 가지는 노드들의 그룹이다.
• 리프(Leaf) - 자식이 없는 노드.
• 간선(Edge) - 한 노드에서 다른 노드로 향하는 화살표이다. 노드와 노드를 연결한다.

👍 트리 사용 사례

• HTML DOM(Hyper Text Markup Language, Document Object Model) - HTML을 보면 그 자체로 트리와 같은 구조를 가지고 있다. 여러 요소들이 있고, 요소 안에 자식에 해당하는 다른 요소들로 중첩되어 있다.
• Network Routing
• Abstract Syntax Tree - 추상 구문 트리
• Artificial Intelligence - 인공 지능
• Operating System의 Folders

✅ 이진트리(Binary Tree)

이진트리란 자식이 최대 두 개인 노드들로 구성된 트리이다. 이진트리의 종류는 많다.

 

✅ 이진 검색 트리(Binary Search Tree)

이진트리를 사용하기 위해 저장할 데이터의 크기에 따라 노드의 위치를 정의한 것을 말한다. 

• 모든 원소는 서로 다른 유일한 키를 갖는다.
• 왼쪽 서브트리에 있는 원소의 크기는 루트의 키보다 작다.
• 오른쪽서브트리에 있는 원소의 크기는 루트의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 탐색 트리다.

부모보다 큰 것은 오른쪽에, 작은 것들은 왼쪽에 두는 방식은 무언가를 찾아보는 것을 아주 빠르고 쉽게 만들어준다. 무언가를 추가하는 것과 노드의 자리를 찾는 것도 쉽게 해 준다. 이진 검색 트리에서의 탐색은 정렬되지 않은 트리와 비교하면 아주 빠르다. 

🔥 Insert 의사코드

• 새 노드를 만든다.
• root가 있는지 확인하고 없다면, 새 노드가 root가 된다.
• root가 있다면, 새 노드의 값이 루트보다 큰지 작은지 확인한다.
• root 보다 크다면, 오른쪽에 노드가 있는지 확인하고, 있다면 해당 노드로 옮겨가서 단계를 반복하고, 없다면 right 속성에 노드를 추가한다.
• root보다 작다면 왼쪽에서 위와 같은 단계를 반복하며 right가 아닌 left propery에 추가한다.

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

class BinarySearchTree {
    constructor() {
        this.root = null;
    }
    insert(value) {
        let newNode = new Node(value);
        if (this.root === null) {
            this.root = newNode;
            return this
        }
        let 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의 의사코드

• root에서 시작
• root가 있다면, 루트의 값과 찾는 값을 비교한다. root가 없다면 searching을 종료.
• 찾으려는 값이 root의 값보다 큰지 작은지 확인한다.
• 더 크다면, right에 값이 있는지 확인하고, 있다면 해당 노드로 이동하고 단계를 반복한다.
• right에 값이 없다면, searching 종료
• 더 작다면, left에서 위와 같은 단계 반복.

find(value) {
    if(this.root === null) return false;
    let current = this.root;
    let 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;
}

위는 찾은 노드를 반환, 아래는 true&false를 반환

contains(value) {
    if (this.root === null) return false;
    let current = this.root;
    let 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;
}

🟢 이진 검색 트리의 Big O

Insertion - O(log n)

Searching - O(log n)