알고리즘, 자료구조
[자료구조-JS] 이진탐색트리 너비우선탐색(BFS) 구현
너비우선탐색이란 무엇인가? 트리나 그래프를 탐색하는 기법 중 하나로써 너비(Breadth)를 우선적으로 탐색하는 방법이다. 너비우선탐색 구현을 위해서 보통 큐(Queue) 자료구조를 이용한다. 너비우선탐색의 동작 루트 노드부터 탐색을 시작한다. 기준 노드에 자식 노드들이 존재한다면 큐에 추가하고, 자기 자신은 큐에서 나온다. 위의 과정을 반복한다. 큐에 아무것도 존재하지 않게 된다면 탐색이 종료된다. 너비우선탐색 주의사항 만약 너비가 넓은 트리나 그래프라면 큐에 저장해야하는 너비 요소들이 많아지므로 공간복잡도가 증가한다. 따라서 너비우선탐색을 효과적으로 사용하기 위해서는 너비가 좁은 트리나 그래프를 대상으로 사용하는 것이 좋다. 구현 // 트리 구현체 class BST { constructor() { t..
