트리(BFS, DFS, 이진 검색 트리)

  트리 구조  

순서 트리와 무순서 트리

• 순서 트리(ordered tree) : 형제 노드의 순서 관계 존재
• 무순서 트리(unordered tree) : 형제 노드의 순서 관계 없음

 

순서 트리의 검색

- 너비 우선 검색(BFS, breadth-first search)

낮은 레벨부터 왼쪽에서 오른쪽으로 검색, 한 레벨에서 검색 마치면 다음 레벨로 내려감

 

- 깊이 우선 검색(DFS, depth-first search)

리프에 도달할때까지 아래로 내려가면서 검색하는 것을 우선

리프에 도달해서 더 이상 검색 대상 없으면 다시 부모 노드로 돌아가 검색

 

DFS의 스캔 방법

• 전위 순회(preorder) : 노드 방문 -> 왼쪽 자식 -> 오른쪽 자식
• 중위 순회(inorder) : 왼쪽 자식 -> 노드 방문 -> 오른쪽 자식
• 후위 순회(postorder) : 왼쪽 자식 -> 오른쪽 자식 -> 노드 방문

 

  이진 트리와 이진 검색 트리  

이진 트리(binary tree)

노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리(자식 없거나 한쪽만 있어도 됨)

 

이진 검색 트리(binary search tree)

이진 검색 트리 조건

• 왼쪽 서브트리 노드의 키값은 자신의 노드 키값보다 작다
• 오른쪽 서브트리 노드의 키값은 자신의 노드 키값보다 크다

=> 키값 같은 노드 복수로 존재 x

 

이진 검색 시간복잡도 : O(log n)       n = 배열의 길이