1. 트리
그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다.
나무처럼 가지를 뻗어나가는 모양새를 닮아 트리라고 부르며 계층적인 자료를 표현하는데 사용한다. 컴퓨터의 디렉토리 구조가 대표적인 예이다.
트리의 최상위 노드를 루트 노드(root node)라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다.
자식 노드가 없는 노드를 리프 노드(leaf node) 또는 말단 노드 (terminal node)라고 한다. 리프 노드가 아닌 노드를 내부 노드(internal node)라고 한다.
또한, 트리는 다음과 같은 조건을 충족한다.
트리의 조건
- 트리는 하나의 루트 노드를 갖는다.
- 루트 노드는 0개 이상의 자식 노드를 갖는다.
- 자식 노드 또한 0개 이상의 자식 노드를 갖는다.
- 노드(Node)들과 노드들을 연결하는 간선(Edge)들로 구성되어 있다.
2. 용어
트리에 관한 용어 중 헷갈리기 쉬운 것들이 있다. 깊이, 높이, 차수가 있는데 하나하나 짚어보도록 하자.
트리의 깊이(depth)는 루트 노드로부터의 거리를 의미하며 높이(height)는 트리의 깊이 중 최댓값을 말한다. 차수(degree)는 각 노드의 간선의 갯수이다.
상단 그림의 트리를 예시로 들어보자.
해당 트리의 2가 들어있는 노드, 즉 루트 노드의 깊이는 0이다. 루트 노드의 자식 노드들의 깊이는 1이 될 것이며 그 아래로 내려갈수록 깊이는 1씩 증가한다.
높이는 그러한 노드들의 깊이 중 최댓값을 말하는 것이므로, 트리의 가장 아래에 위치한 노드의 깊이를 말하는 것이다. 그림에서는 5, 11, 4를 담고 있는 노드가 해당되겠다. 그들의 깊이는 3이므로, 해당 트리의 높이는 3이 된다.
차수는 각 노드의 간선의 갯수이므로, 부모 노드가 가리키고 있는 자식 노드의 수와 같다. 따라서 루트 노드의 차수는 2, 루트 노드의 자식 노드들의 차수는 왼쪽부터 각각 2, 1이다.
3. 이진 트리(Binary tree)
각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조
이진 트리의 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 예시로 보았던 바로 위의 그림의 트리 또한 이진 트리에 속한다. 자식으로 이진 트리 혹은 공집합을 허용하기 때문이다.
종류
-
정 이진 트리(full binary tree): 모든 트리의 자식은 0개나 2개다.
-
포화 이진 트리(perfect binary tree): 모든 리프 노드의 높이가 같고 리프 노드가 아닌 노드는 모두 2개의 자식을 갖는다.
-
완전 이진 트리(complete binary tree): 모든 리프노드의 높이가 최대 1 차이가 나고, 모든 노드의 오른쪽 자식이 있으면 왼쪽 자식이 있는 이진트리이다. 다시 말해 트리의 원소를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간 형태이다.
트리 순회
1. 전위 순회(pre-order traversal): 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문하는 순회 방법.
2. 중위 순회(in-order traversal): 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문하는 순회 방법. 이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다.
3. 후위 순회(post-order traversal): 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문하는 순회 방법.
4. 이진 탐색 트리(Binary Search Tree)
이진 트리의 일종으로, 노드의 왼쪽 가지에는 부모 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있도록 정렬된 트리이다.
이진 탐색 트리는 BST라고도 한다. 그림의 트리처럼 부모 노드를 기준으로 값이 작은 노드는 왼쪽, 값이 큰 노드는 오른쪽에 정렬되는 방식이다.
이런 식으로 정렬해놓았을 때, 어떤 값을 탐색하는 경우 루트 노드의 값과 비교해 더 작은 값이라면 왼쪽, 더 큰 값이라면 오른쪽 가지의 노드들만 탐색하는 방식으로 탐색 시간을 줄일 수 있다.
값을 탐색할 뿐 아니라 삽입, 삭제의 경우에도 해당되므로 시간복잡도는 모두 O(logN)이 된다.
구현
BST를 간단하게 자바스크립트로 구현해보자.
class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
}
//중복값이 없다고 가정한다.
class BST {
constructor() {
this.root = null;
}
find(data) {
if(!this.root) return "찾는 노드가 없습니다.";
let current = this.root;//현재 탐색 중인 노드
while(current.data !== data) {
current = current.data > data ? current.left : current.right;
}
return current;
}
insert(data) {
if(!this.root) {
this.root = new Node(data);
return;
}
let current = this.root; //현재 탐색 중인 노드
while(current) {
if(current.data > data) {
if(!current.left) {
current.left = new Node(data);
return;
}
current = current.left;
}
else {
if(!current.right) {
current.right = new Node(data);
return;
}
current = current.right;
}
}
}
delete(data) {
if(!this.root) return "삭제할 노드가 없습니다.";
let current = this.root; //현재 탐색 중인 노드
let prev = null; //current의 부모 노드
while(current.data !== data) {
prev = current;
current = current.data > data ? current.left : current.right;
}
//1. 삭제할 노드에 자식 노드가 없는 경우
if(!current.left && !current.right) {
if(!prev) {
this.root = null;
return;
}
if(prev.left === current) prev.left = null;
else prev.right = null;
}
//2. 삭제할 노드에 자식 노드가 2개 있는 경우
//삭제한 노드의 자리를 채울 자식노드를 선택한다.
//여기서는 삭제 노드의 우측 서브트리 최소값인 successor를 선택한다.
//successor는 우측 서브트리의 왼쪽 자식을 끝까지 타고 갔을 때 찾을 수 있다.
else if(current.left && current.right) {
let successor = current.right;
while(!successor) {
successor = successor.left;
}
if(prev !== null){
if(prev.left === current) {
prev.left.data = successor.data;
}
else {
prev.right.data = successor.data;
}
}
else { //삭제하는 노드가 루트 노드일 때
this.root.data = successor.data;
}
this.delete(successor);
}
//3. 삭제할 노드에 자식 노드가 1개 있는 경우
//유일한 자식이 삭제된 부모 노드를 그대로 대체한다.
else {
let child = current.left === null ? current.right : current.left;
if(prev.left === current) prev.left = child;
else prev.right = child;
}
}
}
const bst = new BST();
bst.insert(10);
bst.insert(3);
bst.insert(14);
bst.insert(20);
console.log(bst.find(10));
// Node {
// data: 10,
// left: Node { data: 3, left: null, right: null },
// right: Node {
// data: 14,
// left: null,
// right: Node { data: 20, left: null, right: null }
// }
console.log(bst.find(14));
// Node {
// data: 14,
// left: null,
// right: Node { data: 20, left: null, right: null }
// }
console.log(bst.delete(10));
console.log(bst.find(1));
//console.log(bst.delete(20));
출처
https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0
https://gmlwjd9405.github.io/2018/08/12/data-structure-tree.html
