트리
보통 노드의 공통적인 부분을 하나의 클래스로 정의하고, 노드에 들어가는 데이터를 위해 서브 클래스를 만들어서 사용한다.
public abstract class Node{
private Node[] children;
public Node(Node[] children){
this.children = children;
}
public int getNumChildren(){
return Children.length;
}
public Node getChild(int index){
return children.get(index);
}
}
public class intNode extends Node{
private int value;
public IntNode(Node[] children, int value){
super (children);
this.value = value;
}
public int getValue(){
return this.value;
}
}2-1 이진트리 (binary Tree)
public class Node{
private Node left;
private Node right;
private int value;
public Node(Node left, Node right, int value){
this.left = left;
this.right = right;
this.value = value;
}
public Node getLeftNode(){
return this.left();
}
public Node getRightNode(){
return this.right();
}
public int getValue(){
return this.value();
}이진 검색 트리
BST에서 노드의 왼쪽 자식의 값이 반드시 자신의 값 이하이며, 오른쪽 자식의 값은 반드시 자신의 값 이상이다.
이러한 구조 덕에 룩업 연산(트리에 있는 특정 노드의 위치를 알아내는 연산)을 빠르게 처리할 수 있다
룩업 연산 :
- 루트 노트에서 시작
- 현재 노드가 널이 아닌 동안 반복
- 현재의 노드의 값이 찾고자 하는 값이면 현재 노드 리턴
- 현재 노드의 값이 찾고자 하는 노드의 값보다 작으면 오른쪽 자식을 현재 노드로 설정
- 현재 노드의 값이 찾고자 하는 값보다 크면 왼쪽 자식을 현재 노드로 설정
Node findNode (Node root, int value){
while (root != null){
int currval = root.getValue();
if (currval == value)
return break;
else if (currval < value)
root = root.getRightNode();
else if (currval > value)
root = root.getLeftNode();
}
}
return root;시간 복잡도는 log2(n) 수준이다. 삭제 삽입도 log 2 (n) 수준이다.
하지만, 이진트리에 자식이 모두 1개인 경우에는 어떨가..?
연결리스트와 마찬가지로 O(n)이 되어버린다 --> 이미 정렬되어 있는 데이터를 순서대로 BST에 추가하는 경우에도 그렇게 된다.
반복문이 아닌, 재귀로 풀었을 때
Node findNode(Node root, int value){
if (root.getValue() == value)
return root;
else if (root.getValue() > value)
return findNode(root.getLeftNode(), value);
else if (root.getValue() < value)
return findNode(root.getRightNode(), value);
}2-2 힙
노드의 자식들은 노드 자신의 값 이하여야 한다.
삽입, 삭제는 log (n)이지만, 룩업은 O(n)이다. <- 우선순위 부여
빠르게 최대값을 추출해야 한다면 힙을 사용한다. 이 연산은 상수 시간으로 처리된다.
2-3 트리의 검색 방법
BFS 너비 우선 검색
- 노드를 찾아내는데 걸리는 시간은 O(n)이기 때문에 큰 트리에 대해서 검색을 하지 않는 것이 좋다.
- 특정 층을 검색할 때 그 층에 있는 모든 노드의 자식 노드들을 저장해야하기 때문에 메모리 사용이 크다.
DFS 깊이 우선 검색
- 모든 자식 노드들을 저장해야 할 필요가 없기 때문에, BFS에 비해 메모리 사용량이 적다.
- 만약 트리 아래에 있을 것으로 추정되는 값을 탐색한다는 조건이 있다면, BFS에 비해 DFS가 빠를 확률이 높다.
2-4 종주 traversal
검색은 값을 찾으면 작업을 멈추지만, 종주는 모든 노드를 방문하면서 각 노드에 대해 어떤 작업을 수행하게 된다.
이진 트리에서의 종주
-
Preorder 종주
노드 자체에 대해 어떤 작업을 수행하고 왼쪽 자손을 처리한 다음 오른쪽 자손을 처리한다. 즉, 항상 노드를 자식들보다 먼저 방문한다.
-
Inorder 종주
우선 노드의 왼쪽 자손에 대해 작업을 수행한 다음 노드 자체에 대해 작업을 수행하고, 마지막으로 오른쪽 자손을 처리한다.
-
Postorder 종주
노드의 왼쪽 자손에 대해 작업을 수행한 다음 오른쪽 자손에 대해 작업을 수행하고, 마지막으로 그 노드 자체를 ㅊ처리한다.
종주 역시 재귀에 초점을 맞추고 구현하자.
