자료구조 트리가 트리인 이유는 나무처럼 생겼기 때문이다. (정확히는 나무를 뒤집어 놓은 것 같다.)
간단한 예로 HTML 구조가 있다. root(뿌리)부터 시작해서 아래로 가지치기를 한다. 제일 마지막에 위치한 노드는
Leaf(잎)이라고 한다. 제일 위는 root이고, 제일 아래는 leaf이니깐 나무를 거꾸로 뒤집어 놓은 모양을 연상할 수 있다 :-)
여기서. root도 leaf도 아닌 노드들은 내부 노드라고 부른다.
노드와 노드 사이를 이어주는 것은 branch나 edge라고 부른다. 시작점은 반드시 root 하나여야 한다.
HTML이 트리를 본딴 구조이기 때문에 유사성을 갖는다.
위 첨부 그림에서 볼때, document 부터 마지막 text까지 가는 길을 경로(path)라고 부른다. 그리고 부모 노드에서 자식 노드 사이의 edge 개수를 높이(height)라고 부른다. 예를 들면, 위의 경우에서 document root에서 Text "DOM Tree"까지의 높이는 4이다.(화살표를 4개를 거쳐왔다. 이렇게 계산하면 보다 간편하다)
트리에서 유의해야할 점은 트리의 아랫 부분도 모두 트리라는 것이다 트리 아래에 계속 트리가 나오기 때문에 재귀 함수가 사용된다.
실생활에도 트리는 엄청 많이 사용된다. 대진표, 지휘계통 등 단계나 계층이 있는 곳에서는 어김없이 사용된다.
이진트리
이진트리는 중복데이터가 없다는 가정 하에 크다와 작다를 쉽게 구분할 수 있다. 따라서 한번 정렬하면 원하는 데이터를 빠르게 찾을 수 있다.
이진 트리에서 가장 작은 숫자는 가장 왼쪽에, 가장 큰 숫자는 가장 오른족에 있다. 트리는 지금까지의 자료구조와 코드의 복잡성이 차원이 다르다. 트리에 데이터를 넣을때나 찾을때, 그리고 제거할때 대부분 재귀를 사용한다. 자료구조에서 처음으로 비공개함수(Private)가 사용되었다.
var Tree = (function() {
function Tree() {
this.count = 0;
this.root;
}
function Node(data) {
this.data = data;
this.left;
this.right;
}
function _insert(root, node) {
if(!root) return node;
if(node.data < root.data) {
root.left = _insert(root.left, node);
return root;
} else {
root.right = _insert(root.right, node);
return root;
}
return root;
}
Tree.prototype.add = function(data) {
var node = new Node(data);
if (this.count === 0) {
this.root = node;
} else {
_insert(this.root, node);
}
return ++this.count;
}
function _get(data, node) {
if (node) {
if (data < node.data) {
return _get(data, node.left);
} else if (data > node.data) {
return _get(data, node.right);
} else {
return node;
}
} else {
return null;
}
}
Tree.prototype.get = function(data) {
if (this.root) {
return _get(data, this.root);
} else {
return null;
}
};
function _remove(root, data) {
var newRoot, exchange, temp;
if (!root) return false;
if (data < root.data) {
root.left = _remove(root.left, data);
} else if (data > root.data) {
root.right = _remove(root.right, data);
} else {
if(!root.left) {
newRoot = root.right;
// root 메모리 정리
return newRoot;
} else {
exchage = root.left;
while (exchange.right) exchange = exchange.right;
temp = root.data;
root.data = exchage.data;
exchange.data = temp;
root.left = _remove(root.left, exchange.data);
}
}
return root;
}
Tree.prototype.remove = function(key) {
var node = _remove(this.root, key);
if (node) {
this.root = node;
this.count--;
if (this.count === 0) this.root = null;
}
return true;
};
return true;
})();var tree = new Tree();
tree.add(5); // 1
tree.add(3); // 2
tree.add(4); // 3
tree.add(2); // 4
tree.add(7); // 5
tree.add(6); // 6
tree.root.left.data; // 3
tree.root.left.left.data; // 2;
tree.root.left.right.data; // 4
tree;
tree.remove(3);
tree.root.left.data;추가하는 것은 원하는 위치를 찾을 때까지 오른쪽 왼쪽 찾아가며 재귀를 통해 도달한다. 지우고자 하는 데이터를 재귀를 통해 찾아 지우면 되겠지만, 지운 후 트리가 이진 검색 트리 조건을 만족하는지 확인해야 한다.
따라서 삭제의 경우 세가지를 고려하게 된다.
- 왼쪽 자식 노드가 없을 때
- 오른쪽 자식 노드가 없을 때
- 왼쪽, 오른쪽 자식 노드 둘 다 있을때
**양쪽 자식 노드가 모두 없을 때는 1. 왼쪽 노드가 없을 때와 같이 처리한다.(노드를 뺸 것과 돌일)
왼쪽 자식 노드가 없다면(숫자 10의 경우) 오른쪽 노드를 끌어올려 지워진 공간을 채우면 되고, 오른쪽 자식 노드가 없다면 (숫자 14) 왼쪽 노드를 끌어올리면 되는데,
자식이 양쪽 아 있을 때(숫자 8의 경우)는 조금 다른 전략이 필요하다. 일단 지우고자 하는 8 노드와 8의 왼쪽 자식 노드 중 가장 큰 노드(7)를 교환한다. 그래야 이진 검색 트리 조건이 유지된다.
이제 7이 루트가 되고, 8은 7자리로 교환된다. 이후 3을 루트로 하는 트리에서 8을 지우면 된다. 현재 노드8은 양쪽 자식이 모두 없으므로, 1.왼쪽 자식 노드가 없을때의 조건에 해당한다.
8을 지워버리면 새로운 이진 검색 트리가 완성된다. 이전 검색 트리의 삭제 기능은 노드의자식 위치와 개수에 따라 분기 처리를 해주어야 해서 조금 더 복잡하다.
출처
