이진 트리의 너비 우선 검색

이previous blog 게시물에서 우리는 이진 트리가 무엇인지, 어떻게 표현할 수 있는지, 이진 트리의 다양한 유형에 대해 배웠습니다. 결론적으로 다른 데이터 구조와 달리 이진 트리는 두 가지로 탐색할 수 있다고 말했습니다 호흡 우선 검색과 깊이 우선 검색의 다양한 방법.
이 게시물은 호흡 우선 검색에 중점을 둘 것입니다.

이 게시물은 호흡 우선 검색에 중점을 둘 것입니다.

너비 우선 탐색 트리 순회란 무엇입니까?

Breath-first search는 레벨별로 트리 레벨을 순회할 수 있는 알고리즘이므로 Level Order Traversal이라고도 합니다. 원칙은 다음 단계로 이동하기 전에 동일한 수준의 모든 노드를 표시하는 것입니다. 기본적으로 레벨 순서 순회를 따라 위의 트리를 순회하면 결과는 다음과 같아야 합니다.



보시다시피 순서는 트리의 수준을 따릅니다.

자바스크립트 구현

function bfs(root){
  const queue = [root]
  const result = []; 
  let current; 

  while(queue.length){
    current = queue.shift(); 
    result.push(current.val);

    if(current.left) queue.push(current.left);
    if(current.right) queue.push(current.right);
  }

  return result;
}

설명

레벨 순서 순회는 큐를 사용하여 구현됩니다. 대기열은 FIFO(First In First Out) 원칙을 따르는 기본 데이터 구조입니다.

함수는 트리 루트인 하나의 매개변수를 받습니다. 우리는 트리 루트로 큐를 초기화하고 순회 결과와 current라는 변수를 포함할 빈 배열을 선언합니다.

대기열이 비어 있지 않은 동안에는 통과할 노드가 있음을 의미합니다. 루프 내부에서 대기열이 FIFO 원칙을 따르기 때문에 대기열의 첫 번째 노드가 될 대기열의 노드를 얻습니다. current 내부의 값을 결과 테이블에 푸시하고 current에 자식이 있는지 확인합니다. 그렇다면 자식을 큐에 푸시합니다.

대기열은 FIFO 원칙을 따르기 때문에 동일한 수준의 노드는 다음 수준으로 이동하기 전에 결과 배열로 푸시됩니다.

삽화

설명을 위해 아래의 이진 트리를 순회합니다.



먼저 루트 노드로 대기열을 초기화하고 결과를 빈 배열로 초기화해야 합니다.



루프로의 첫 번째 랩 동안 루트 노드는 대기열에서 제거되고 해당 값은 결과로 푸시되고 하위 노드는 큐로 푸시됩니다.



대기열이 FIFO(선입선출)를 따르기 때문에 배열에서 제거될 다음 노드는 14입니다. 그런 다음 해당 값이 결과 배열에 추가되고 해당 자식도 대기열에 추가됩니다.



그의 차례에 35가 대기열에서 제거되고 그 값이 결과에 추가되며 대기열의 하위 항목이 추가됩니다.



마지막으로 큐에 남아있는 노드는 리프(자식이 없는 노드)이므로 결과에 하나씩 추가됩니다.

복잡성 분석

Level Order 순회는 전체 트리를 한 번만 순회하므로 시간 복잡도는 O(n)이고 순회 중에 노드를 저장하기 위해 대기열을 사용하기 때문에 공간 복잡도는 O(n)입니다.

결론

우리는 게시물의 끝에 있습니다. 이 글을 읽으면서 새로운 것을 배우기를 바랍니다.