1. 트리 (Tree) 구조
트리 : Node와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조
실제로 어디에 많이 사용되나? 트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨
2. 알아둘 용어
- Node : 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
- Root Node : 트리 맨 위에 있는 노드
- Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 길이를 나타냄
- Parent Node : 어떤 노드의 다음 레벨에 연결된 노드
- Child Node : 어떤 노드의 상위 레벨에 연결된 노드
- Leaf Node (Terminal Node) : Child Node가 하나도 없는 노드
- Sibling (Brother Node) : 동일한 Parent Node를 가진 노드
- Depth : 트리에서 Node가 가질 수 있는 최대 Level
3. 이진 트리와 이진 탐색 트리 (Binary Search Tree)
- 이진 트리 : 노드의 최대 Branch가 2인 트리
- 이진 탐색 트리 (Binary Search Tree, BST) : 이진 트리에서 다음과 같은 추가적인 조건이 있는 트리
- 왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음!
4. 자료 구조 이진 탐색 트리의 장점과 주요 용도
주요 용도 : 데이터 검색 (탐색)
장점 : 탐색 속도를 개선할 수 있음
단점 :
이진트리와 정렬된 배열간의 탐색 비교
| 21 | ||||||||||||||
| 14 | 28 | |||||||||||||
| 11 | 18 | 25 | 32 | |||||||||||
| 5 | 12 | 15 | 19 | 23 | 27 | 30 | 37 |
| 5 | 11 | 12 | 14 | 15 | 18 | 19 | 21 | 23 | 25 | 27 | 28 | 30 | 32 | 37 |
5. 링크드 리스트 구현하기
public class Node {
private Integer value;
public Node left;
public Node right;
public Node(Integer value) {
this.value = value;
this.left = null;
this.right = null;
}
public Node(Integer value, Node right) {
this.value = value;
this.right = right;
}
public Integer getValue() {
return this.data;
}
}
public class NodeMgmt() {
private Node head; //root Node
public void init(Integer value) {
head = new Node(value);
}
public void insert(Integer value) {
Node node = head;
while(true) {
if (value < node.getValue()) {
if (node.left != null) {
node = node.left;
} else {
node.left = new Node(value);
break;
}
} else {
if (node.right != null) {
node = node.right;
} else {
node.right = new Node(value);
break;
}
}
}
}
public Boolean search(Integer value) {
Node node = head;
while (node) {
if (node.getValue() == value) {
return true;
} else if (value < node.getValue()) {
node = node.left;
} else {
node = node.right;
}
}
return false;
}
public Boolean delete(Integer value) {
Boolean searched = false;
Node node = head;
Node parent = head;
while (node) {
if (node.getValue() == value) {
searched = true;
break;
} else if (value < node.getValue()) {
parent = node;
node = node.left;
} else {
parent = node;
node = node.right;
}
}
if (searched == false) {
return false;
}
// 1. 삭제할 Node가 Leaf Node인 경우
if (node.left == null && node.right == null) {
if (value < parent.getValue()) {
parent.left = null;
} else {
parent.right = null;
}
}
// 2. 삭제할 Node가 Child Node를 한 개 가지고 있을 경우
if (node.left != null && node.right == null) {
if (value < parent.getValue()) {
parent.left = node.left;
} else {
parent.right = node.left;
}
} else if (node.left == null && node.right != null) {
if (value < parent.getValue()) {
parent.left = node.right;
} else {
parent.right = node.right;
}
}
// 3. 삭제할 Node가 Child Node를 두 개 가지고 있을 경우
if (node.left != null && node.right != null) {
if (value < parent.getValue()) {
Node changeNode = node.right;
Node changeNodeParent = node.right;
while (changeNode.left != null) {
changeNodeParent = changeNode;
changeNode = changeNode.left;
}
if (changeNode.right != null) {
changeNodeParent.left = changeNode.right;
} else {
changeNodeParent.left = null;
}
parent.left = changeNode;
changeNode.left = node.left;
changeNode.right = node.right;
} else {
Node changeNode = node.right;
Node changeNodeParent = node.right;
while (changeNode.left != null) {
changeNodeParent = changeNode;
changeNode = changeNode.left;
}
if (changeNode.right != null) {
changeNodeParent.left = changeNode.right;
} else {
changeNodeParent.left = null;
}
parent.right = changeNode;
changeNode.left = node.left;
changeNode.right = node.right;
}
}
return true;
}
}
6. 이진 탐색 트리의 시간 복잡도와 단점
6-1 시간 복잡도 (탐색시)
- depth (트리의 높이) 를 h라고 표기한다면, O(h)
- n개의 노드를 가진다면, h = log2n에 가까우므로, 시간 복잡도는 O(logn)
- 빅오 표기법에서 logn에서의 log의 밑은 10이 아니라 2
- 한번 실행시마다 50%의 실행할 수도 있는 명령을 제거한다는 의미, 즉 50%의 실행시간을 단축시킬 수 있음을 의미
6-2 이진 탐색 트리 단점
- 평균 시간 복잡도는 O(logn) 이지만 최악의 경우는 링크드 리스트 등과 동일한 성능을 보임 O(n)