이진 탐색 트리(Binary Search Tree, BST)와 BFS, DFS

1. 이진 탐색 트리(Binary Search Tree)

 

이진 탐색 트리는 각 노드가 최대 두 개의 자식을 가지며, 왼쪽 자식은 현재 노드보다 작은 값, 오른쪽 자식은 큰 값을 가지는 특별한 형태의 이진 트리이다.

 

필수 구현 메서드:

• insert(value) - 새로운 값을 적절한 위치에 삽입
• find(value) - 특정 값을 찾아서 반환
• remove(value) - 특정 값을 가진 노드를 삭제
• getMin() - 최솟값(가장 왼쪽 노드) 반환
• getMax() - 최댓값(가장 오른쪽 노드) 반환

주요 구현 포인트:

 

1. 삽입 시 순서 결정:

if (value < node.value) {
    if (!node.left) node.left = new Node(value);
    else insert(node.left, value);
} else {
    if (!node.right) node.right = new Node(value);
    else insert(node.right, value);
}

 

 

2. 삭제 시 3가지 경우 처리:

• 리프 노드: 직접 삭제
• 하나의 자식: 자식을 현재 위치로 승격
• 두 개의 자식: 중위 후속자로 대체

3. 균형 관리:

• 트리가 한쪽으로 치우치지 않도록 관리
• 필요시 회전 연산 구현 (AVL, Red-Black 트리)

시간 복잡도:

• 평균 케이스: O(log n) - 검색, 삽입, 삭제
• 최악 케이스: O(n) - 트리가 한쪽으로 치우친 경우

활용 사례:

1. 데이터베이스 인덱싱
2. 파일 시스템 구조
3. 우선순위 큐 구현
4. 검색 알고리즘 최적화

이진 탐색 트리는 효율적인 검색과 정렬된 데이터 유지가 필요한 경우에 유용하다.

데이터의 삽입/삭제가 빈번한 동적 데이터 집합을 다루는 경우 이진 탐색 트리를 사용하는 경우가 많다.

 

구현

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

class BinarySearchTree {

	constructor() {
		this.root = null;
	}

	insert(value) {
		const newNode = new Node(value);
		if(this.root === null) {
			this.root = newNode;
			return this;
		}

		// 찾는 노드 역할을 하게 된다.
		let current = this.root;

		while(true) {
			if(value === current.value) return false;	// 이미 존재한다면 false 반환
			
			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) {	// current가 null이되거나 found가 true가 되면 깨진다.
			if(value < current.value) {	// 작으면 왼쪽이므로
				current = current.left;
			} else if (value > current.value) {	//크다면 오른쪽에 놓이므로
				current = current.right;
			} else {
				// 찾았다면
				found = true;	// 순회 탈출!
			}
		}
		if(!found) return undefined;
		return current;
	}


	// 해당 값이 있는지 확인하기 위한 메서드. find와 거의 유사
	contains(value) {
		if(this.root === null) return false;

		let current = this.root;

		while(current) {
			if(value < current.value) {
				current = current.left;
			} else if( value > current.value) {
				current = current.right
			} else {
				// 작거나 크지 않다면 같은 것만 남았으므로
				return true;
			}
		}	// 또는 current가 null이 되는 경우 순회문 탈출

		return false;
	}


	    // 트리에서 최솟값 찾기 (가장 왼쪽 노드)
    getMin() {
        if (!this.root) return null;
        
        let current = this.root;
        // 더 이상 왼쪽 자식이 없을 때까지 계속 왼쪽으로 이동
        while (current.left) {
            current = current.left;
        }
        return current.value;
    }

    // 트리에서 최댓값 찾기 (가장 오른쪽 노드)
    getMax() {
        if (!this.root) return null;
        
        let current = this.root;
        // 더 이상 오른쪽 자식이 없을 때까지 계속 오른쪽으로 이동
        while (current.right) {
            current = current.right;
        }
        return current.value;
    }

    // 노드 삭제하기
    remove(value) {
        if (!this.root) return false;

        let current = this.root;
        let parent = null;
        let isLeftChild = true;

        // 삭제할 노드 찾기
        while (current && current.value !== value) {
            parent = current;
            if (value < current.value) {
                isLeftChild = true;
                current = current.left;
            } else {
                isLeftChild = false;
                current = current.right;
            }
        }

        // 노드를 찾지 못한 경우
        if (!current) return false;

        // Case 1: 리프 노드인 경우
        if (!current.left && !current.right) {
            if (current === this.root) {
                this.root = null;
            } else if (isLeftChild) {
                parent.left = null;
            } else {
                parent.right = null;
            }
        }
        // Case 2: 하나의 자식만 있는 경우
        else if (!current.right) {  // 왼쪽 자식만 있는 경우
            if (current === this.root) {
                this.root = current.left;
            } else if (isLeftChild) {
                parent.left = current.left;
            } else {
                parent.right = current.left;
            }
        } 
        else if (!current.left) {   // 오른쪽 자식만 있는 경우
            if (current === this.root) {
                this.root = current.right;
            } else if (isLeftChild) {
                parent.left = current.right;
            } else {
                parent.right = current.right;
            }
        }
        // Case 3: 두 개의 자식이 있는 경우
        else {
            // 후계자 찾기 (오른쪽 서브트리의 최솟값)
            let successor = this.getSuccessor(current);
            
            if (current === this.root) {
                this.root = successor;
            } else if (isLeftChild) {
                parent.left = successor;
            } else {
                parent.right = successor;
            }
            
            successor.left = current.left;
        }

        return true;
    }

    // remove 헬퍼 메서드: 후계자(successor) 찾기
    getSuccessor(node) {
        let successorParent = node;
        let successor = node;
        let current = node.right;

        // 후계자 찾기 (오른쪽 서브트리에서 가장 작은 값)
        while (current) {
            successorParent = successor;
            successor = current;
            current = current.left;
        }

        // 후계자가 삭제할 노드의 직계 자식이 아닌 경우
        if (successor !== node.right) {
            successorParent.left = successor.right;
            successor.right = node.right;
        }

        return successor;
    }
    
    // 너비 우선 탐색: 수평적으로(시블링 노드 순으로) 이진탐색트리를 탐색 수집
    BFS() {
        let node = this.root;

        const data = [];    // 순회하면서 수집한 값들의 배열 visited로 치환 가능
        const queue = [];   // 아직 미방문한 노드들을 순서대로 저장하는 대기열. FIFO로 작동

        queue.push(node);   // 노드의 밸류를 넣어도 되고

        while(queue.length !== 0) { // while(queue.length) {
            node = queue.shift();
            data.push(node.value);  // data.push(node)로 하면 객체가 저장됨.

            if(node.left) queue.push(node.left);    // 왼쪽 자식이 있으면 큐에 추가
            if(node.right) queue.push(node.right);  // 오른쪽 자식이 있으면 큐에 추가
            /*
                여기가 바로 너비 우선 탐색의 핵심 로직. 
                그 자식들이 큐에 추가되고, 그것들이 데이터에 너비 순서대로(옆으로) 기록되고,
                그것의 레프트 라이트가  있으면 다시 큐에 추가되는 구조
            */
        }
        return data;    // 수집한(방문한) 노드들이 들어있는 배열
    }
    
    
        //깊이 우선 탐색 (전위 순회: 부모가 먼저 기록되고, 그 다음 왼쪽, 오른쪽 순으로 처리 ==>  노드 → 왼쪽 → 오른쪽)
    DFSPreOrder(current = this.root) {  // 이렇게 하면 서브트리를 순회시킬 수 있음.
        let data = [];

        function traverse(node) {
            data.push(node.value);
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);   // 만약 계속해서 외쪽이 존재한다면 이 라인은 대기하게 된다.
        }

        traverse(current) //아규먼트가 없으면 root 부터 순회 시작
        return data;
    }

    // 깊이 우선 탐색 (후위 - 자식들이 먼저 기록되고, 부모는 마지막에 처리 ==> 왼쪽 → 오른쪽 → 노드)
    DFSPostOrder(current = this.root) {
        let data = [];

        function traverse(node) {
            if(node.left) traverse(node.left);
            if(node.right) traverse(node.right);

            // 먼저 넣어주는 것이 아니라 왼쪽 오른을 살핀 뒤에 넣어준다.
            data.push(node.value)
        }

        traverse(current);

        return data;
    }
    
        // 깊이 우선 탐색 (중위(inOrder) -> 왼쪽 자식부터 기록되고, 왼쪽이 끝나면 해당 노드 기록, 그리고 오른쪽 자식 기록 ==> 왼쪽 → 노드 → 오른쪽 )
    DFSInOrder(current = this.root) {
        const data = [];

        function traverse(node) {
            if(node.left) traverse(node.left);

            // 왼쪽 기이 끝나면 해당 노드를 기록
            data.push(node.value);
            if(node.right) traverse(node.right);
        }
        traverse(current);
        return data;
    }





}

const bst = new BinarySearchTree();
bst.insert(10);
bst.insert(5);
bst.insert(15);
bst.insert(2);
bst.insert(7);

console.log(bst.getMin());  // 2
console.log(bst.getMax());  // 15
console.log(bst.contains(7));  // true
bst.remove(5);
console.log(bst.contains(5));  // false

 

 

2. 이진탐색트리의 BFS 와 DFS 의 예시

 

각 순회 방식의 특징:

• BFS: 레벨 순서대로 방문하여 같은 깊이의 노드들(형제 노드)을 순차적으로 처리
• DFS 전위: 부모를 먼저 방문한 후 자식들을 방문 (루트 우선)
• DFS 후위: 자식들을 모두 방문한 후 부모를 방문 (리프 노드 우선)
• DFS 중위: 왼쪽 자식, 부모, 오른쪽 자식 순으로 방문 (오름차순 정렬된 결과)

 

	10
       /    \
      6      15
    /  \    /  \
   3    8  13   20

 

트리 생성

const tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(13);
tree.insert(20);

 

BFS 예시

console.log(tree.BFS());
// 결과: [10, 6, 15, 3, 8, 13, 20]

/*

순회 과정:

레벨 0: 10
레벨 1: 6, 15
레벨 2: 3, 8, 13, 20

*/

 

 

DFS 예시

 

1) 전위 순회(pre-order)

console.log(tree.DFSPreOrder());
// 결과: [10, 6, 3, 8, 15, 13, 20]

/*

순회 과정:

루트(10) 방문
왼쪽으로 가서 6 방문
3 방문
8 방문
오른쪽으로 가서 15 방문
13 방문
20 방문

*/

 

 

2) 후위 순회(post-order)

console.log(tree.DFSPostOrder());
// 결과: [3, 8, 6, 13, 20, 15, 10]

/*
순회 과정:

가장 왼쪽 리프인 3 방문
8 방문
부모인 6 방문
13 방문
20 방문
15 방문
마지막으로 루트인 10 방문
*/

 

3) 중위 순회(in-order)

console.log(tree.DFSInOrder());
// 결과: [3, 6, 8, 10, 13, 15, 20]

/*
순회 과정:

가장 왼쪽 3 방문
부모인 6 방문
8 방문
루트인 10 방문
13 방문
15 방문
20 방문
*/

 

 

3. 이진탐색트리에 대해 BFS와 DFS를 선택하는 기준

 

BFS와 DFS의 선택은 문제의 성격과 트리의 구조에 따라 달라진다.

 

BFS(너비 우선 탐색)이 유리한 경우:

1. 트리가 깊고 좁은 경우 (메모리 관점)
   • 각 레벨에서 처리할 노드가 적어 큐의 크기가 작게 유지됨
   • 한 번에 저장되는 노드의 수가 적음
2. 최단 경로 찾기
   • 출발지에서 가장 가까운 노드부터 탐색
   • 예: 최단 거리, 최소 이동 횟수 문제
3. 레벨 단위의 처리가 필요한 경우
   • 트리의 각 층을 순서대로 처리해야 할 때
   • 예: 조직도에서 각 직급별 처리

DFS(깊이 우선 탐색)이 유리한 경우:

1. 트리가 넓은 경우 (메모리 관점)
   • 형제 노드가 많은 경우
   • 현재 경로의 노드만 스택에 저장하므로 메모리 효율적
2. 경로 탐색이 필요한 경우
   • 특정 경로의 존재 여부 확인
   • 예: 미로 찾기, 경로 존재 확인
3. 트리의 모든 노드를 방문해야 할 때
   • 예: 파일 시스템 탐색, 모든 하위 디렉토리 검색

각 DFS 순회 방식의 활용:

1. 전위 순회(Pre-order): 노드 → 왼쪽 → 오른쪽
   • 트리 구조 복사
   • 디렉토리 구조 출력
2. 중위 순회(In-order): 왼쪽 → 노드 → 오른쪽
   • 이진 검색 트리에서 정렬된 순서 얻기
   • 수식 트리에서 중위 표기식 생성
3. 후위 순회(Post-order): 왼쪽 → 오른쪽 → 노드
   • 트리 삭제 (자식부터 삭제)
   • 디렉토리 용량 계산 (하위 항목부터 계산)

 

넓은 트리의 경우:
         A
   /  /  |  \  \
  B  C   D   E  F

BFS: 큐에 [B,C,D,E,F] 모두 저장 → 많은 메모리 필요
DFS: 한 번에 한 경로만 저장 [A,B] → 메모리 효율적

깊은 트리의 경우:
  A
  |
  B
  |
  C
  |
  D

BFS: 큐에 한 번에 하나의 노드만 저장 → 메모리 효율적
DFS: 스택에 전체 경로 [A,B,C,D] 저장 → 더 많은 메모리 사용