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

들어가기 전에...

해당 글은 유데미 JavaScript 알고리즘 & 자료구조 마스터클래스 강의를 바탕으로 작성되었다. 수도 코드를 보고 혼자 구현해보고, 이후 강의에서 주어진 코드를 참고하여 수정했다! 강의에 나온 코드를 최대한 효율적이고 수정했기에 강의 속 코드보다 좋은 코드일 것이라 생각한다.

✅ 이진 탐색 트리

출처: 위키백과

• 노드의 왼쪽에는 노드의 값보다 작은 숫자가 있어야 한다
• 노드의 오른쪽에는 노드의 값보다 큰 숫자가 있어야 한다
• 노드의 왼쪽과 오른쪽에 위치한 트리도 이진 탐색 트리여야 한다
  => 왼쪽 트리의 모든 값은 노드보다 작아야하고, 오른쪽은 커야 함

📌 구현 - 연결리스트

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

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

    // 노드 추가
    insert(val) {
        let newNode = new Node(val)

        // 트리가 없는 상태면 노드를 루트로 등록
        if(this.root === null) {
            this.root = newNode;
            return this;
        }
        else {
            let current = this.root;

            while(true) {
                // 노드보다 값이 작으면 왼쪽으로 이동
                if(current.value > val) { 
                    if(current.left) current = current.left;
                    else {
                        current.left = newNode;
                        return this;
                    }
                }
                // 노드보다 값이 크면 오른쪽으로 이동
                else if(current.value < val) {
                    if(current.right) current = current.right;
                    else {
                        current.right = newNode;
                        return this;
                    }
                }
                // 노드와 값이 같으면 중복된 값이므로 종료
                else if(current.value === val) return;
            }
        }
        return this;
    }

    // 해당 값을 가진 노드 찾기
    search(val) {
        if(this.root === null) return false;

        let current = this.root;

        while(current) {
            if(current.value === val) return true;
            else if(current.value > val) current = current.left;
            else if(current.value < val) current = current.right;
        }

        return false;
    }
}

💡 이진 탐색 트리인지 판별

leetcode의 98. Validate Binary Search Tree 문제의 풀이와 동일함

var isValidBST = function(root) {
    let queue = [root];
    let cur;

    // 트리의 모든 노드 순회
    while(queue.length) {
        cur = queue.shift(); 
        let leftChildQue = [], rightChildQue = []; // 현재 노드의 왼쪽 트리, 오른쪽 트리의 노드 저장할 큐
        let leftChild, rightChild; // 큐에 저장된 왼쪽, 오른쪽 트리의 각 노드

        if(cur.left) {
            leftChildQue.push(cur.left);
            queue.push(cur.left);
        }
        if(cur.right) {
            rightChildQue.push(cur.right);
            queue.push(cur.right);
        }

        // 왼쪽 트리 확인
        while(leftChildQue.length) {
            leftChild = leftChildQue.shift();
            if(leftChild.val >= cur.val) return false;
            if(leftChild.left) leftChildQue.push(leftChild.left);
            if(leftChild.right) leftChildQue.push(leftChild.right);
        }

        // 오른쪽 트리 확인
        while(rightChildQue.length) {
            rightChild = rightChildQue.shift();
            if(rightChild.val <= cur.val) return false;
            if(rightChild.left) rightChildQue.push(rightChild.left);
            if(rightChild.right) rightChildQue.push(rightChild.right);
        }
    }

    return true;
};

📌 시간 복잡도

• 삽입: O(logN)
• 검색: O(logN)