[Javascript] 이진 탐색 트리

가장 활용도가 높은 이진 탐색트리를 자바스크립트로 구현해보겠습니다.

2021.09.30 - [Programming/자료구조] - 이진 탐색 트리

이진 탐색 트리

 

중복 코드와 로직부분은 private 멤버 함수로 선언했습니다.

코드가 좀 많이 길지만 내용은 간단합니다. 재귀를 통해 삽입, 삭제, 검색에서 연산을 진행하도록 설계했습니다.

class Tree {
    constructor() {
        this.root;	//루트 노드
        this.size = 0;	//트리 크기
    }

    _insertNode(root, node) {
        if (root === null) { //빈 트리
            return node;
        }

        //루트 노드 요소보다 삽입 노드 요소가 더 작으면 왼쪽 트리로
        if (node.data < root.data) {
            root.leftNode = this._insertNode(root.leftNode, node);

            return root;
        }
        //더 크면 오른쪽 트리로 삽입
        else {
            root.rightNode = this._insertNode(root.rightNode, node);

            return root;
        }
        return root;
    }

    insertNode(data) {
        const newNode = new Node(data);

        //트리 사이즈가 0이면 루트로 삽입
        if (this.size === 0) {
            this.root = newNode;
        }
        else {
            this._insertNode(this.root, newNode);
        }
    }

    _searchNode(data, node) {
        if (node) {
            //찾는 값이 현재 노드 요소값보다 작으면 왼쪽으로 탐색진행
            if (data < node.data) {
                return this._searchNode(data, node.leftNode);
            }
            //크면 오른쪽으로 탐색 진행
            else if (data > node.data) {
                return this._searchNode(data, node.rightNode);
            }
            else {
                return node;
            }
        }
        else {
            return null;
        }
    }


    searchNode(data) {
        if (this.root) {
            return this._searchNode(data, this.root);
        }
        else {
            return null;
        }
    }

    _deleteNode(root, data) {
        let newRootNode;
        let change;
        let temp;

        //트리에 노드가 없으면 false 반환
        if (root === null) {
            return false;
        }

        //삭제 데이터가 루트보다 작으면 왼쪽으로 삭제연산 진행
        if (data < root.data) {
            root.leftNode = this._deleteNode(root.leftNode, data);
        }
        //크면 오른쪽으로 삭제연산 진행
        else if (data > root.data) {
            root.rightNode = this._deleteNode(root.rightNode, data);
        }
        else {
            if (root.leftNode === null) {
                newRootNode = root.rightNode;
            }
            else if (root.rightNode === null) {
                newRootNode = root.leftNode;
            }
            else {
                change = root.leftNode;

                while (change.rightNode !== null) {
                    change = change.rightNode;
                }

                temp = root.data;
                change.data = temp;
                root.leftNode = this._deleteNode(root.leftNode, change.data);
            }
        }
    }

    deleteNode(key) {
        const node = this._deleteNode(this.root, key);

        if (node) {
            this.root = node;
            this.size--;

            if (this.size === 0) {
                this.root = null;
            }
        }
        
        return true;
    }
}

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/data-structure/BinarySearchTree.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록