이진 탐색 트리 (Binary Search Tree) 구현해보기

이진 탐색 트리

현재 노드를 기준으로 왼쪽에는 작은 값, 오른쪽은 큰 값으로 정렬해 놓는 이진 트리 기반 자료 구조

구현 메서드

• 노드 추가: BinarySearchTree._insertNode(), BinarySearchTree.insert()
• 노드 탐색(최댓값): BinarySearchTree._maxNode(), BinarySearchTree.max()
• 노드 탐색(최솟값): BinarySearchTree._minNode(), BinarySearchTree.min()
• 노드 탐색(특정값): BinarySearchTree._searchNode(), BinarySearchTree.search()
• 노드 삭제: BinarySearchTree._findMinNode(), BinarySearchTree._removeNode(), BinarySearchTree.remove()

1. 중위 순회 기준

2. 노드 추가 및 중위 순회에 대한 print 메서드의 경우 이진 트리와 동일

_insertNode (node, value) {
        if (node === null) {
            node = new Node(value);
        } else if (value < node.value) {
            node.left = this._insertNode(node.left, value);
        } else if (value > node.value) {
            node.right = this._insertNode(node.right, value);
        }
        return node;
    }

insert (value) {
    this.root = this._insertNode(this.root, value);
}

_inOrderTraverseNode (node, callback) {
    if (node === null) return;

    this._inOrderTraverseNode(node.left, callback);
    callback(node);
    this._inOrderTraverseNode(node.right, callback);
}

inOrderTraverse (callback) {
    this._inOrderTraverseNode(this.root, callback);
    console.log("end");
}

3. 최대값 찾기 (_maxNode(), max())

1) 가장 최대값의 경우, 가장 오른쪽에 위치한 노드이다.

2) node.right가 null이 아닐 때까지 이동해서 해당 node를 리턴한다.

_maxNode (node) {
        if (node === null) return null;

        while (node && node.right !== null) {
            node = node.right;
        }
        return node.value;
    }

max () {
    return this._maxNode(this.root);
}

4. 최소값 찾기 (_minNode(), min())

1) 최소값의 경우, 가장 왼쪽에 위치한 노드이다.

2) node.left가 null이 아닐 때까지 이동해서 해당 node를 리턴한다.

_minNode (node) {
        if (node === null) return null;

        while (node && node.left !== null) {
            node = node.left;
        }
        return node.value;
    }

min () {
    return this._minNode(this.root);
}

5. 값을 만족하는 노드 찾기 (_searchNode, search())

1) _insertNode 메서드와 비슷하다.

2) node.value === value일 경우 바로 true를 리턴한다.

3) node.value < value일 경우, 다시 재귀를 통해 node.right에서 만족하는 노드를 찾는다.

4) node.value > value일 경우, 다시 재귀를 통해 node.left에서 만족하는 노드를 찾는다.

_searchNode (node, value) {
        if (node === null) return false;

        if (node.value === value) {
            return true;
        } else if (value < node.value) {
            return this._searchNode(node.left, value);
        } else if (value > node.value) {
            return this._searchNode(node.right, value);
        }
    }

search (value) {
    return this._searchNode(this.root, value);
}

6. 노드 삭제 (_removeNode(), remove())

1. child node가 하나도 없을 때, 바로 해당 노드를 null로 만든다.

2. child node가 1개일 때

   node의 오른쪽이 없을 경우, node = node.left가 되고

   node의 왼쪽이 없을 경우, node = node.right가 된다.

3. child node가 2개일 때

   1. 노드의 오른쪽을 기준으로 가장 작은 값을 삭제할 노드로 바꾼다.
   2. 노드의 오른쪽 중 가장 작은 값이 없어졌기 때문에, 가장 작은 노드를 찾아 삭제한다.

내가 삭제할 노드 찾기 → 바로 삭제를 할 수 있는가? (연결 고리) → 삭제한 노드를 this.root에 연결

_removeNode (node, value) {
        if (node.value === value) {
            // case 1: 0 child node
            if (node.left === null && node.right === null) {
                node = null;
            } 
            // case 2: 1 child node
            else if (node.left === null) {
                node = node.right;
            } else if (node.right === null) {
                node = node.left;
            }
            // case 3: 2child node
            else {
                let temp = this._findMinNode(node.right);
                node.value = temp.value;
                node.right = this._removeNode(node.right, temp.value);
            }
        } else if (node.value < value) {
            node.right = this._removeNode(node.right, value);
        } else if (node.value > value) {
            node.left = this._removeNode(node.left, value);
        }
        return node;
    }

remove (value) {
    this.root = this._removeNode(this.root, value);
}

관련 전체 코드는 Git에 업로드 해두었습니다.
Github_BinarySearchTree