반응형
이진트리
트리
트리란 정점과 간선을 갖는 그래프에서 부모와 자식의 계층 구조를 갖는 자료구조를 의미한다. 이진트리를 정리하기에 앞서 트리에 대해 간단하게 정리해보자.
- 트리는 다음과 같이 계층 구조를 갖고 있다. 위에 있는 노드(정점)가 아래에 있는 노드의 부모가 되며, 같은 높이에 있는 노드 간은 형제 노드라고 부른다. 최상위 노드는 루트노드, 최하위 노드는 리프노드라고 칭한다.
- 트리는 정점(V), 간선(E) 관계에서
E = V-1속성을 갖는다.
- 트리에는 레벨, 높이, 깊이를 나누어서 비교한다. 레벨의 경우 루트 노드가 있는 곳은 Level 0로 시작하고, 트리의 높이는 (리프 노드의 레벨 - 루트 노드의 레벨)로 정해진다. 트리의 깊이는 지정한 노드로 부터의 깊이를 의미하며 예를 들어서 C 노드의 깊이는 2다.
이진트리
- 이진트리란 모든 부모노드가 2개 이하의 자식 노드를 갖는 트리를 의미한다. 즉, 위의 트리 예시에서 보여졌던 모든 트리는 이진트리이다. 정이진 트리, 완전 이진 트리, 변질 이진 트리, 포화 이진 트리, 균형 이진 트리 등이 존재한다.
- 정이진 트리란 모든 노드가 0개 또는 2개의 자식노드를 갖는 이진 트리를 의미한다.
- 완전 이진 트리란 자식 노드를 왼쪽에서 부터 채우는 이진 트리를 의미한다.
- 변질 이진 트리란 한쪽으로만 치우친 이진 트리를 의미하며 편향 이진트리라고도 불린다.
- 포화 이진 트리란 모든 자식 노드가 2개의 자식 노드를 갖는 꽉찬 이진 트리를 의미한다.
- 균형 이진 트리란 모든 노드의 왼쪽 자식 노드의 깊이와 오른쪽 자식 노드의 깊이 차이가 1이하인 노드를 의미한다. 균형 이진 트리는 AVL, Red-Black Tree 등에 사용된다.
이진 트리 탐색
순회는 모든 노드를 탐색하는 것으로, 순회의 방법에 따라 노드를 방문하는 순서가 다르다. 이진 트리 순회에서는 전위,중위,후위,레벨 순회가 존재한다.
전위 순회
- 전위 순회는 전체 트리의 관점에서 부모 노드를 선 방문 후 좌측 서브 트리와 우측 서브 트리를 방문하는 방식이다. 리프 노드에 도착한 경우 백트래킹 관점으로 이전 분기점으로 이동한다.
public static preOrder(Node parent) {
if (parent == null) {
return;
}
visit(parent);
preOrder(parent.left);
preOrder(parent.right);
}- 부모, 좌측, 우측 순서대로 재귀함수를 호출한다.
중위 순회
- 중위 순회는 전체 트리의 관점에서 좌측, 부모, 우측노드를 방문하는 방법이다.
후위 순회
- 후위 순회는 전체 트리의 관점에서 좌측, 우측, 부모노드를 방문하는 방법이다.
레벨 순회
- 레벨 순회는 기존과 다르게 스택 방식을 사용한 재귀적인 코드가 아닌 큐를 이용하여 레벨 별로 순회하는 방법이다.
public static void levelOrder() {
Queue<Node> queue = new LinkedList();
if (root == null) return;
queue.offer(root);
while(!queue.isEmpty()) {
Node parent = queue.poll();
visit(parent);
if (parent.left != null) queue.offer(parent.left);
if (parent.right != null) queue.offer(parent.right);
}
}- 큐를 사용하여 부모 노드에서 부터 좌측, 우측 자식 노드의 존재 여부를 확인하고 존재한다면 큐에 삽입하는 방식으로 사용한다.
이진 탐색 트리 (BST)
트리를 사용하는 이유는 일반적으로 데이터를 빠르게 탐색하기 위해 사용한다. 기존에 배열 또는 리스트 방식은 앞이나 뒤에서 부터 데이터를 찾을 때까지 순차적으로 탐색해야 하기 때문에 최악의 경우 N번의 탐색이 필요하다.
반면에 이진 탐색 트리는 부모 노드를 기준으로 좌측 노드는 부모보다 작은 값을, 우측 노드는 부모보다 큰 값을 갖는 특정한 규칙을 통해 데이터를 빠르게 찾을 수 있다.
- 다음과 같이 이진 탐색 트리를 사용하면 데이터를 O(log N)으로 탐색할 수 있다. 하지만 편향이진트리와 같이 한 곳에 모여있는 경우(최악) log(N)의 시간복잡도를 갖는다. 이 문제를 해결하기 위해 트리의 균형을 맞춰주는 AVL 트리와 레드-블랙 트리가 존재한다.
- 이진 탐색 트리는 삽입 또는 삭제 시 마다 규칙을 유지하면서 관리해야한다. 삭제를 하려는 노드의 기준으로 좌측 노드에서 가장 큰 노드 또는 우측에서 가장 작은 노드와 자리를 교환한 후, 리프노드로 올때까지 swap 과정을 거친 후 삭제한다.
- 다음과 같이 좌측을 선택했을 경우 가장 큰 (가장 우측 하단에 있는 노드) 노드와 swap한 후 현재 위치에서 리프 노드인 8이 존재하기 때문에 다시 8과 swap 후 12를 삭제한다.
이진 탐색 트리의 순회를 통해 오름차순과 내림차순으로 방문할 수 있다. 내림차순으로 방문하고 싶다면 좌측 중위 순회를, 오름차순으로 방문하고 싶다면 우측 중위 순회를 사용하면 된다.
REFERENCES
https://ratsgo.github.io/data%20structure&algorithm/2017/10/21/tree/
반응형
