Traversing Tree - 트리 순회
목차
1. 트리 순회 소개
2. 너비 우선 탐색 소개
3. 너비 우선 탐색 솔루션 (BFS)
4. 깊이 우선 탐색 소개 – 전위 순회
5. 깊이 우선 탐색 솔루션 – 전위 순회 (PreOrder)
6. 깊이 우선 탐색 소개 – 후위 순회
7. 깊이 우선 탐색 솔루션 – 후위 순회 (PostOrder)
8. 깊이 우선 탐색 – 정위 순회
9. 깊이 우선 탐색 솔루션 – 정위 순회 (InOrder)
10. 너비 우선 탐색과 깊이 우선 탐색은 언제 사용되는가?
1. 트리 순회 소개
슬라이드 : Trees and Binary Search Trees (slides.com)
Trees and Binary Search Trees
A presentation created with Slides.
cs.slides.com
(방향에 따른) 두 가지 방법
1. BFS (Breadth-first Search) : 너비 우선 탐색( 👉 )
2. DFS (Depth-first Search) : 깊이 우선 탐색 ( 👇 ) - 3가지 방법 존재
최종코드
// Depth_First_Tree.js
class Node {
constructor(value){
this.value = value;
this.left = null;
this.right = null;
}
}
class BinarySearchTree {
constructor(){
this.root = null;
}
insert(value){
var newNode = new Node(value);
if(this.root === null){
this.root = newNode;
return this;
}
var current = this.root;
while(true){
if(value === current.value) return undefined;
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;
var current = this.root,
found = false;
while(current && !found){
if(value < current.value){
current = current.left;
} else if(value > current.value){
current = current.right;
} else {
found = true;
}
}
if(!found) return undefined;
return current;
}
contains(value){
if(this.root === null) return false;
var current = this.root,
found = false;
while(current && !found){
if(value < current.value){
current = current.left;
} else if(value > current.value){
current = current.right;
} else {
return true;
}
}
return false;
}
BFS(){
var node = this.root,
data = [],
queue = [];
queue.push(node);
while(queue.length){
node = queue.shift();
data.push(node.value);
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
return data;
}
DFSPreOrder(){
var data = [];
function traverse(node){
data.push(node.value);
if(node.left) traverse(node.left);
if(node.right) traverse(node.right);
}
traverse(this.root);
return data;
}
DFSPostOrder(){
var data = [];
function traverse(node){
if(node.left) traverse(node.left);
if(node.right) traverse(node.right);
data.push(node.value);
}
traverse(this.root);
return data;
}
DFSInOrder(){
var data = [];
function traverse(node){
if(node.left) traverse(node.left);
data.push(node.value);
if(node.right) traverse(node.right);
}
traverse(this.root);
return data;
}
}
var tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.BFS();
tree.DFSPreOrder();
tree.DFSPostOrder();
tree.DFSInOrder();
2. 너비 우선 탐색 소개
BFS 의사코드
단계 - 반복문으로
1. 큐(배열 or 클래스) 생성 & 방문한 노드의 값을 변수에 저장 (추가: Array.push, 제거: Array.shift -> FIFO)
2. 큐에 루트 노드를 넣음
3. 큐에 무언가 있다면 계속 루프를 돌림
3-1. 큐에서 dequeue를 함. (배열을 사용한 경우라면 shift()로 배열의 맨 앞에서 제거함) & 그 노드의 값을 변수에 저장
3-2. dequeue된 노드에 왼쪽 프로퍼티가 있다면, 그걸 큐에 넣음
3-3. dequeue된 노도에 오른쪽 프로퍼티가 있다면, 그걸 큐에 넣음
4. 루프가 끝나면, 모든 값을 저장한 변수(1번줄 값) 출력
3. 너비 우선 탐색 솔루션 (BFS)
class BinarySearchTree {
// ...
BFS(){ // here!
var node = this.root,
data = [], //리턴용 변수
queue = []; //순서 정렬용 변수
queue.push(node);
while(queue.length){
node = queue.shift();
data.push(node.value);
if(node.left) queue.push(node.left);
if(node.right) queue.push(node.right);
}
return data;
}
}
var tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.BFS();
// 10 <- node
// 6 15
// 3 8 20
동작 순서
-----1------------------
queue : [ 10, 6, 15 ]
data : [ 10 ]
-----2------------------
queue : [ 6 , 15, 3, 8]
data : [ 10, 6 ]
-----3------------------
queue : [ 15, 3, 8, 20]
data : [ 10, 6, 15 ]
-----4------------------
queue : [ 3 , 8, 20]
data : [ 10, 6, 15, 3 ]
-----5------------------
queue : [ 8 , 20]
data : [ 10, 6, 15, 3, 8 ]
-----6------------------
queue : [ 20 ]
data : [ 10, 6, 15, 3, 8, 20 ]
-----------------------
queue : [ ] → 반복문 종료!
data : [ 10, 6, 15, 3, 8, 20 ] → 리턴!
-----------------------
4. 깊이 우선 탐색 소개 – 전위 순회
전위 순회(preOrder) 의사코드
(단계 - 재귀적으로)
1. 방문했던 노드의 값을 저장하는 변수(data) 생성 (마지막에 리턴)
2. current라 부르는 변수 생성, 거기에 root 저장
3. node를 인자로 받는 헬퍼함수 생성
3-1. 값을 저장하는 변수(data)에 노드의 값을 저장
3-2. 만약에 노드가 왼쪽 프로퍼티를 가지고 있다면, 노드의 왼쪽 프로퍼티로 헬퍼 함수를 재귀 호출함
3-3. 만약에 노드가 오른쪽 프로퍼티를 가지고 있다면, 노드의 오른쪽 프로퍼티로 헬퍼 함수를 재귀 호출함
4. current 변수를 인자로 헬퍼 함수 호출 (제일 먼저 this.root 들어감)
5. 방문했던 값을 가진 배열(data) or 리스트를 리턴
5. 깊이 우선 탐색 솔루션 – 전위 순회(PreOrder)
🎁 크롬 디버거로 호출 스택확인해보기
class BinarySearchTree {
// ...
DFSPreOrder(){
var data = [];
function traverse(node){
data.push(node.value);
if(node.left) traverse(node.left);
if(node.right) traverse(node.right);
}
traverse(this.root);
return data;
}
}
var tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.DFSPreOrder();
// 10 <- node
// 6 15
// 3 8 206. 깊이 우선 탐색 소개 – 후위 순회
후위 순회(postOrder) 의사코드
전위 순회(preOrder)와 헬퍼함수 빼고 유사함
(단계 - 재귀적으로)
1. 방문했던 노드의 값을 저장하는 변수(data) 생성 (마지막에 리턴)
2. current라 부르는 변수 생성, 거기에 root 저장
3. node를 인자로 받는 헬퍼함수 생성
3-1. 만약에 노드가 왼쪽 프로퍼티를 가지고 있다면, 노드의 왼쪽 프로퍼티로 헬퍼 함수를 재귀 호출함
3-2. 만약에 노드가 오른쪽 프로퍼티를 가지고 있다면, 노드의 오른쪽 프로퍼티로 헬퍼 함수를 재귀 호출함
3-3. 값을 저장하는 변수(data)에 노드의 값을 저장
4. current 변수를 인자로 헬퍼 함수 호출 (제일 먼저 this.root 들어감)
5. 방문했던 값을 가진 배열(data) or 리스트를 리턴
7. 깊이 우선 탐색 솔루션 – 후위 순회(PostOrder)
🎁 크롬 디버거로 호출 스택확인해보기
class BinarySearchTree {
// ...
DFSPostOrder(){
var data = [];
function traverse(node){
if(node.left) traverse(node.left);
if(node.right) traverse(node.right);
data.push(node.value);
}
traverse(this.root);
return data;
}
}
var tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.DFSPostOrder();
// 10
// 6 15
// 3 8 20
// ↑
// root8. 깊이 우선 탐색 – 정위 순회(InOrder)
정위 순회(InOrder) 의사코드
전위 순회(preOrder)와 헬퍼함수 빼고 유사함
(단계 - 재귀적으로)
1. 방문했던 노드의 값을 저장하는 변수(data) 생성 (마지막에 리턴)
2. current라 부르는 변수 생성, 거기에 root 저장
3. node를 인자로 받는 헬퍼함수 생성
3-1. 만약에 노드가 왼쪽 프로퍼티를 가지고 있다면, 노드의 왼쪽 프로퍼티로 헬퍼 함수를 재귀 호출함
3-2. 값을 저장하는 변수(data)에 노드의 값을 저장
3-3. 만약에 노드가 오른쪽 프로퍼티를 가지고 있다면, 노드의 오른쪽 프로퍼티로 헬퍼 함수를 재귀 호출함
4. current 변수를 인자로 헬퍼 함수 호출 (제일 먼저 this.root 들어감)
5. 방문했던 값을 가진 배열(data) or 리스트를 리턴
9. 깊이 우선 탐색 솔루션 – 정위 순회(InOrder)
🎁 크롬 디버거로 호출 스택확인해보기
class BinarySearchTree {
// ...
DFSInOrder(){
var data = [];
function traverse(node){
if(node.left) traverse(node.left); //node.left && traverse(node.left) 가능
data.push(node.value);
if(node.right) traverse(node.right); //node.right && traverse(node.left) 가능
}
traverse(this.root);
return data;
}
}
var tree = new BinarySearchTree();
tree.insert(10);
tree.insert(6);
tree.insert(15);
tree.insert(3);
tree.insert(8);
tree.insert(20);
tree.DFSInOrder();
// 10
// 6 15
// 3 8 20
// ↑
// root10. 너비 우선 탐색과 깊이 우선 탐색은 언제 사용되는가?
만약 100개의 노드가 있다면, DFS 이든 BFS 이든 모든 노드 각각을 방문해야 한다.
같은 양의 시간 복잡도를 가진다.
그렇지만 무엇을 사용할지는 트리의 구조에 달려 있다.
만약에 트리가 아주 넓다면, BFS는 큐를 저장하는데 더 많은 공간을 사용한다.
만약에 트리가 아주 깊다면, DFS는 큐를 저장하는데 더 많은 공간을 사용한다.
Q. DFS (preOrder, postOrder, inOrder)는 언제 사용해야 하는가?
회고
1. 트리는 비선형(non-linear) 데이터 구조이고 루트 하나와 자식 노드들로 구성되어 있다.
2. 이진 트리(Binary Trees)는 어떠한 종류의 값을 가질 수 있다. 그러나 각 노드는 최대 2개의 자식을 가질 수 있다.
3. 이진 탐색 트리(Binary Search Trees)는 이진 트리의 특별한 경우이다. (tree -> binary tree -> binary search tree)
4. 이진 탐색 트리는 일종의 순서를 가지는, 정렬된 트리이다.
부모의 왼쪽에 있는 모든 노드는 부모보다 작고, 부모의 오른쪽에 있는 모든 노드는 부모보다 크다.
그러므로 이진 탐색 트리는 비교가 가능한 데이터 종류에만 사용할 수 있다.
5. BFS 와 DFS(inOrder, preOrder, postOrder)를 이용해서 트리를 탐색하거나 순회할 수 있다.