[Udemy] 이진 검색 트리(Binary Search Tree)란?

정의

이진 검색 트리를 설명하기 전 트리 자료구조에 대해 먼저 설명하자면,

트리 자료구조는 비선형 자료구조로, 부모가 자식을 가리키는 구조이다.

이진 검색 트리

위 사진처럼 최상위 노드를 '루트'라고 부르고,

'루트'에서 하위 노드 방향으로 연결된 자료구조를 '트리' 자료구조라고 한다.

 

이진 트리는 노드당 최대 2개의 자식을 가지며,

이진 검색 트리는 추가로 부모 노드보다 작은 숫자는 좌측노드, 부모 노드보다 큰 숫자는 우측노드로 정렬되어 있다는 특징이 있다.

 

 

용어

- 루트(root) : 최상위 노드

- 자식노드(child) : 같은 부모를 가지는 노드, 루트와 먼쪽으로 이동할 때 직접적으로 연결된 노드

- 부모노드(parent) : 자식을 가진 노드

- 형제노드(siblings) : 동일한 부모를 갖는 노드 그룹

- 리프노드(leaf) : 자식노드가 없는 노드

- 엣지(edge) : 노드를 연결한 화살표

 

 

코드

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

 

Node 클래스의 기본 프로퍼티는 value, left, right로 값과 좌측, 우측을 가리키는 포인터로 구성된다.

BinarySearchTree 클래스는 삽입과 검색 메서드를 포함한다.

 

삽입과 검색 시 값을 토대로 대소비교를 하면서 원하는 위치에 삽입하거나 지정된 값을 찾는 로직을 구현한다.

 

 

시간복잡도

삽입 - O(log n)

검색 - O(log n)

 

삽입과 검색 모두 시간복잡도는 O(log n)이다.

그 이유는 각 노드 별로 최대 2개의 자식 노드를 가질 수 있으므로

이는 n이 늘어날 수록 n의 1/2로 계산 과정이 늘어나기 때문이다.

 

 

참조

Udemy - Js 알고리즘 & 자료구조 강의