[Data Structure] BST (Binary Search Tree)

BST (Binary Search Tree)에 대해 정리하였습니다.

---

< BST >

Binary Search Tree 즉 이진탐색트리는 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지는 이진 트리입니다.

 

 

Binary Search Tree (BST)에서 값이 같은 노드, 즉 중복된 값을 처리하는 방법은 다양합니다.
1. 중복 값을 허용하지 않기
2. 중복 값을 왼쪽 서브트리에 삽입
3. 중복 값을 오른쪽 서브트리에 삽입
4. 중복된 값의 카운트를 증가시키기

 

 

---

< 장/단점 >

[ 장점 ]

• 탑색 속도가 빠릅니다: 이진 탐색 트리는 데이터가 정렬된 상태를 유지하므로 탐색 속도가 빠릅니다. 이진 탐색 트리에서 데이터를 찾는 데 필요한 평균 시간 복잡도는 O(log n)입니다.
• 간단한 구현: 이진 탐색 트리의 구현은 상대적으로 간단합니다.

 

[ 단점 ]

• 불균형 트리의 가능성: 데이터가 삽입되는 순서에 따라 이진 탐색 트리는 불균형해질 수 있습니다. 이 경우 탐색의 시간 복잡도가 O(n)으로 증가할 수 있습니다.

 

 

---

 

< 주요 연산 >

1. 삽입 (Insertion)
   • 삽입할 데이터를 이진 탐색 트리의 루트부터 시작합니다. 
   • 삽입할 데이터가 현재 노드의 데이터보다 작으면 왼쪽 서브트리로 이동하고, 크면 오른쪽 서브트리로 이동합니다.
   • 삽입할 위치에 도달하면 새로운 노드를 만들어 해당 위치에 추가합니다.
2. 삭제 (Deletion)
   • 삭제할 데이터를 이진 탐색 트리에서 찾습니다.
   • 시 제할 노드의 자식 노드의 개수에 따라 세 가지 경우로 나눕니다.
     1. 자식이 없는 경우: 삭제할 노드를 단순히 제거합니다.
     2. 하나의 자식을 가진 경우: 삭제할 노드를 해당 자식 노드로 대체합니다.
     3. 두 개의 자식을 가진 경우: 삭제할 노드를 오른쪽 서브트리에서 가장 작은 노드로 대체합니다.
   • 삭체된 노드의 위치에서 다시 삭제를 수행합니다. 
3. 탐색 (Search)
   
   • 탐색할 데이터를 이진 탐색 트리의 루트부터 시작합니다.
   • 현재 노드의 데이터와 탐색할 데이터를 비교합니다.
   • 탐색할 데이터가 현재 노드의 데이터보다 작으면 왼쪽 서브트리로 이동하고, 크면 오른쪽 서브트리로 이동합니다.
   • 해당 데이터를 찾을 때까지 위의 과정을 반복합니다.

 

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

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

    // 삽입 연산
    insert(data) {
        const newNode = new Node(data);
        
        if (this.root === null) {
            this.root = newNode;
        } else {
            this.insertNode(this.root, newNode);
        }
    }

    insertNode(node, newNode) {
        if (newNode.data < node.data) {
            if (node.left === null) {
                node.left = newNode;
            } else {
                this.insertNode(node.left, newNode);
            }
        } else {
            if (node.right === null) {
                node.right = newNode;
            } else {
                this.insertNode(node.right, newNode);
            }
        }
    }

    // 탐색 연산
    search(data) {
        return this.searchNode(this.root, data);
    }

    searchNode(node, data) {
        if (node === null) {
            return false;
        } else if (data < node.data) {
            return this.searchNode(node.left, data);
        } else if (data > node.data) {
            return this.searchNode(node.right, data);
        } else {
            return true;
        }
    }

    // 삭제 연산
    remove(data) {
        this.root = this.removeNode(this.root, data);
    }

    removeNode(node, key) {
        if (node === null) {
            return null;
        } else if (key < node.data) {
            node.left = this.removeNode(node.left, key);
            return node;
        } else if (key > node.data) {
            node.right = this.removeNode(node.right, key);
            return node;
        } else {
            if (node.left === null && node.right === null) {
                node = null;
                return node;
            }

            if (node.left === null) {
                node = node.right;
                return node;
            } else if (node.right === null) {
                node = node.left;
                return node;
            }

            const aux = this.findMinNode(node.right);
            node.data = aux.data;
            node.right = this.removeNode(node.right, aux.data);
            return node;
        }
    }

    findMinNode(node) {
        if (node.left === null) {
            return node;
        } else {
            return this.findMinNode(node.left);
        }
    }
}

// 테스트
const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(3);
bst.insert(7);
bst.insert(12);
bst.insert(17);

console.log("Search 7:", bst.search(7)); // true
console.log("Search 11:", bst.search(11)); // false

bst.remove(5);
console.log("Search 5 after removal:", bst.search(5)); // false

 

 

---

< Traverse >

[ Pre Order Traverse ]

: 현재 노드를 먼저 방문한 뒤, 왼쪽 서브트리를 순회하고 오른쪽 서브트리를 순회합니다.  

• 트리의 구조를 볼 때 유용합니다. 트리의 깊이를 알고자 할 때, 혹은 특정 조건에 따라 노드를 빠르게 확인하고자 할 때 사용됩니다.

// 전위 순회 (Pre-order traversal)
preOrderTraversal(node = this.root) {
    if (node !== null) {
        console.log(node.data);
        this.preOrderTraversal(node.left);
        this.preOrderTraversal(node.right);
    }
}

 

 

[ In Order Traverse ]

: 왼쪽 서브트리를 순회한 뒤 현재 노드를 방문하고, 오른쪽 서브트리를 순회합니다. 이로 인해 노드들이 오름차순으로 방문됩니다. 

• BST에서 노드들을 정렬된 순서로 방문하고자 할 때 사용됩니다. 예를 들어, BST에 저장된 데이터를 정렬된 순서로 출력하거나 검색하는 경우에 활용됩니다.

// 중위 순회 (In-order traversal)
inOrderTraversal(node = this.root) {
    if (node !== null) {
        this.inOrderTraversal(node.left);
        console.log(node.data);
        this.inOrderTraversal(node.right);
    }
}

 

 

[ Post Order Traverse ]

: 왼쪽 서브트리를 순회한 뒤, 오른쪽 서브트리를 순회한 뒤 마지막으로 현재 노드를 방문합니다.

• 트리의 하위 구조를 처리하거나, 트리의 깊이를 파악할 때 유용합니다. 또한, 트리의 높이를 계산하거나 트리에서 특정한 패턴을 찾을 때 사용됩니다.

// 후위 순회 (Post-order traversal)
postOrderTraversal(node = this.root) {
    if (node !== null) {
        this.postOrderTraversal(node.left);
        this.postOrderTraversal(node.right);
        console.log(node.data);
    }
}