트리(Tree) 란?
- 하나의 루트 노드를 갖고, 0개 이상의 자식노드로 이루어져 있는 구조.
- 자식노드 또한 0개 이상의 자식노드를 가질 수 있다.
트리(Tree) 종류
이진트리
- 각 노드가 최대 2개의 자식 노드를 갖는 트리
이진탐색트리
- 모든 노드가 특정 순서를 따르는 속성이 있는 이진트리를 일컫는다.
- "모든 왼쪽 자식들 ≤ n < 모든 오른쪽 자식들" 모든 노드 n 은 해당 조건을 반드시 충족해야한다.
- 바로 아래 자식 뿐만아니라 내 밑에있는 모든 노드가 충족되어야 한다.
- 모든 노드에 대해서 그 왼쪽 자식들의 값이 현재 노드 값보다 작거나 같도록 하고, 오른쪽 자식들의 값은 현재 노드의 값보다 반드시 커야 한다.
출처: 코딩 인터뷰 완전분석
완전 이진 트리
- 트리의 모든 높이에서 노드가 꽉 차 있는 이진 트리
- 마지막 단계는 꽉 차 있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져 있어한다.
출처: 코딩 인터뷰 완전분석
전 이진 트리 (full binary tree)
- 모든 노드에 자식이 없거나 정확히 두개 있는 경우이다.
- 하나만 있어선 안된다 .
출처: 코딩 인터뷰 완전분석
포화 이진 트리 (perfect binary tree)
- 전 이진 트리 + 완전 이진 트리
- 모든 말단 노드는 같은 높이에 있어야 한다.
- 2k-1 (k는 트리 높이) 개여야 하며 흔하게 나타나는 경우는 아니다.
- 면접에서 나온 트리가 포화 이진 트리 일것이라 생각하지 말자.
출처: 코딩 인터뷰 완전분석
최소 힙 삽입
- 최소 힙에는 insert 와 extract_min 이라는 핵심 연산 두 가지가 존재
- 삽입
- 최소 힙에서 원소를 삽입할 땐 항상 트리의 밑바닥에서부터 삽입을 시작한다.
- 완전 트리 속성에 위배되지 않게 밑바닥 가장 오른쪽 위치로 삽입된다.
- 새로 삽입된 원소가 제대로 된 자리를 찾을 때까지 부모 노드와 교환해 나간다.
- 이와 같은 방식으로 최소 원소를 위쪽으로 올린다.
- O (log n) 시간이 걸린다.
출처: 코딩 인터뷰 완전분석
- 최소 원소 뽑아내기
- 최소 원소를 제거한 후 힙에 있는 가장 마지막 원소와 교환한다.
- 최소 힙 성질을 만족하도록 해당 노드를 자식 노드와 교환해 나가며 밑으로 보낸다.
- 왼쪽 자식과 오른쪽 자식 중 더 작은 원소와 교환해 나간다.
- O (log n) 시간이 걸린다.
출처: 코딩 인터뷰 완전분석
트라이 (접두사 트리)
- n-차 트리 (n-ary tree) 의 변종
- 각 노드에 문자를 저장
- 트리 아래쪽을 순회하면 단어 하나가 나온다.
- 널 노드(null node) 라고 불리우는 '* 노드' 는 종종 단어의 끝을 나타낸다.
- 예를들어, MANY 이후에 '* 노드' 가 나오면 단어가 완성되었음을 알리는 것이다.
- 널 노드 대신 널 노드의 부모 노드 안에 불린 플래그(boolean flag)를 새로 정의하여 단어의 끝을 표현할 수 있다.
- 트라이에서 각 노드는 1개에서 ALPHABET_SIZE + 1개까지 자식을 갖고 있을 수 있다.
- 만약, '* 노드' 대신 불린 플래그로 표현했다면 0개 ~ ALPHABET_SIZE 까지
출처: 코딩 인터뷰 완전분석
- 접두사를 빠르게 찾아보기 위한 방식으로 모든 언어를 트라이에 저장해놓는 방식이 있다.
- 해시테이블을 이용하면 주어진 문자열이 유효한지 아닌지는 빠르게 확인할 수 있지만, 유효한 단어의 접두사인지 확인할 수는 없다.
- 트라이는 길이가 K인 문자열이 주어졌을 때 O(K) 시간에 해당 문자열이 유효한 접두사인지 확인할 수 있다.
- 해시 테이블도 검색하는 시간은 O(1) 이지만, 입력 문자열은 전부 읽어야하므로 길이가 K인 단어를 검색하는 데 걸리는 시간은 O(K) 이다.
이진 트리 순회
이진트리를 횡단하면서 모든 데이터를 가져오는 방법
- 중위(in-order), 후위(post-order), 전위(pre-order) 순회가 있다.
- 가장 빈번하게 사용되는 것은 중위(in-order) 순회이다.
- 중위 순회 (in-order traversal)
- 왼쪽 가지(branch) → 현재 노드 → 오른쪽 가지 순서로 노드를 방문하고 출력
- 이진 탐색 트리를 이 방식으로 순회한다면 오름차순으로 방문하게 된다.
출처: https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA
- 중위 순회 (in-order traversal)
- 자식 노드보다 현재 노드를 먼저 방문하는 방법
- 전위 순회에서 가장 먼저 방문하게 될 노드는 언제나 루트이다.
출처: https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA
- 후위 순회 (post-order trabersal)
- 모든 자식노드들을 먼저 방문한 뒤 마지막에 현재 노드를 방문하는 방법
- 후위 순회에서 가장 마지막에 방문하게 될 노드는 언제나 루트이다.
출처: https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA
이진 트리 구현
class Node {
int data;
Node left;
Node right;
}
class Tree {
public Node root;
public Node getRoot() {
return root;
}
public void setRoot(Node root) {
this.root = root;
}
/*
노드를 만드는 함수
데이터와 왼쪽, 오른쪽 노드를 받아 할당
*/
public Node makeNode(Node left, int data, Node right) {
Node node = new Node();
node.data = data;
node.left = left;
node.right = right;
return node;
}
public void inorder(Node node) {
if (node != null) {
inorder(node.left);
System.out.println(node.data);
inorder(node.right);
}
}
public void preorder(Node node) {
if (node != null) {
System.out.println(node.data);
preorder(node.left);
preorder(node.right);
}
}
public void postorder(Node node) {
if (node != null) {
postorder(node.left);
postorder(node.right);
System.out.println(node.data);
}
}
}
/*
(1)
(2) (3)
(4) (5)
Inorder (Left, Root, Right): 4 2 5 1 3
Prerder (Root, Left, Right): 1 2 4 5 3
Postorder (Left, Right, Root): 4 5 2 3 1
*/
public class Main {
public static void main(String[] args) {
Tree t = new Tree();
Node n4 = t.makeNode(null, 4, null);
Node n5 = t.makeNode(null, 5, null);
Node n2 = t.makeNode(n4, 2, n5);
Node n3 = t.makeNode(null, 3, null);
Node n1 = t.makeNode(n2, 1, n3);
t.setRoot(n1);
t.preorder(t.getRoot()); //1 2 4 5 3
t.inorder(t.getRoot()); //4 2 5 1 3
t.postorder(t.getRoot()); //4 5 2 3 1
}
}
참고자료
http://www.yes24.com/Product/Goods/44305533
https://www.youtube.com/channel/UCWMAh9cSkEn8v42YRO90BHA