1. 트리 자료 구조
트리
트리란 연결 리스트와 같이 노드로 이루어진 데이터 구조를 말한다. 또한 노드 간 Branches들을 통해 연결되어 부모-자식 관계를 갖는다. 배열과 연결 리스트는 선형적인 특성을 갖지만, 트리는 비선형성을 갖고 갈 수 있는 경로가 여러 갈래로 나뉘어 진다.
- 트리 구조에서 노드는 부모-자식 관계에 따라 자식인 노드만을 가리킬 수 있다. *역행할 수 없으며, 형제 노드 또한 가리킬 수 없다.
- 하나의 출발점(Root)을 갖는다.
- 자식 노드를 갖지 않는 끝단의 노드를 리프(Leaf)라 한다.
- 노드에는 정수 뿐 아니라, 문자열이나 배열 등 다양한 형태의 데이터가 들어올 수 있다.
예시
HTML DOM은 하위 요소로서 자식을 중첩해서 가지고 있는 형태의 대표적인 트리 구조이다. 외에도 개발 공부 준비 단계에서 흔히 보는 로드맵이나, 운영체제의 디렉토리 등도 트리 구조를 갖는다.
종류
- 트리
- 이진 트리 : 각 노드가 최대 두 개의 자식만 가질 수 있다고 제한 (0,1,2)
- 이진 탐색 트리 : 이진 트리의 특별한 종류로, 정렬 방식에 차이를 갖는다. 데이터가 횡방향으로 작은 수부터 오름차순으로 순서에 따라 저장되어 있다.
2. 이진 탐색 트리 (BST)
이진 탐색 트리는 탐색 측면에서 월등한 성능을 보인다. 루트부터 탐색을 시작하여, 노드를 타고 들어갈 때마다 연산량이 절반씩 감소한다. 앞의 설명을 정리해보면 일정한 플로우가 그려지는데, 왼쪽 혹은 오른쪽으로의 이동 방향을 결정하여 반으로 트리를 쪼개는 과정을 원하는 값을 찾을 때 까지 반복하게 된다.
노드 클래스 셋업
class Node {
constructor(val) {
this.val = val;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
}
}
var tree = new BST();
tree.root = new Node(10);
tree.root.right = new Node(15);
tree.root.left = new Node(7);
tree.root.left.right = new Node(9);
삽입 메서드
새로운 노드를 생성하여, 제대로 된 위치에 노드를 배치한다.
- 무한루프 순환식 혹은 재귀로 구현 가능하다.
- 노드를 생성하여, 루트가 존재하는지 확인한다. 루트가 없다면 생성한 노드가 루트로 지정된다.
- 기존의 루트가 존재한다면, 새로운 노드 값이 루트의 값보다 큰지 작은지 비교한다.
- 크다면 루트의 오른쪽으로 옮겨가고, 작다면 루트의 왼쪽 노드로 옮겨가 과정을 반복한다.
insert(val) {
var newNode = new Node(val);
if (this.root === null) {
this.root = newNode;
return this;
} else {
var current = this.root;
while (true) {
if (val === current.val) return undefined;
if (val < current.val) {
if (current.left === null) {
current.left = newNode;
return this;
} else {
current = current.left;
}
} else if (val > current.val) {
if (current.right === null) {
current.right = newNode;
return this;
} else {
current = current.right;
}
}
}
}
}
탐색 메서드
원하는 값이 해당 트리에 존재하는지 탐색한다. 노드를 타고 들어가는 것은 삽입 메서드의 과정과 비슷하다. 만약 트리의 끝단에 도달했는데 원하는 값과 일치하지 않는다면 그 값은 트리에 존재하지 않는다는 것을 의미한다.
find(val) {
if (this.root === null) return false;
var current = this.root;
var found = false;
// 원하는 값을 찾지 못했거나, 끝단에 도달하여
// current가 Null이 되기 전까지 루프
while (current && !found) {
if (val < current.val) {
current = current.left;
} else if (val > current.val) {
current = current.right;
} else {
// found = true;
return true;
}
}
return false;
}
3. 이진 탐색 트리 알고리즘의 빅오 복잡도
앞에서도 말했듯 노드를 한 번 거칠수록 연산량이 절반 줄어들기 때문에 일반적인 경우 삽입과 탐색 모두 O(log N) 복잡도를 갖는다. 그러나 1줄로 쭉 이어진 연결 리스트의 형태를 갖는 선형 트리에서는, 모든 노드를 한 번씩 순회하기 때문에 O(N)의 복잡도를 갖게 된다.
