참고
Tree 란?
NOTE
Tree ⇒ 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조!
Tree 구조
•
데이터를 계층적이고 효율적으로 관리할 수 있는 구조다.
•
이진 트리, 이진 검색 트리(BST), 균형 트리(B+, B- Tree)가 존재한다.
•
트리는 재귀적인 구조를 가지며, 자기 자신을 재귀적으로 정의해서 탐색하거나 조작할 때 재귀 알고리즘을 사용하기 적합하게 만든다.
기본 용어
•
노드(Node)
◦
트리를 구성하는 기본 단위, 데이터와 다른 노드를 가리키는 포인터를 포함한다.
•
루트(Root)
◦
트리의 최상위 노드다.
◦
이 노드에서 모든 트리 순회가 시작된다.
•
리프(Leaf)
◦
자식 노드가 없는 노드를 의미한다.
◦
Tree가 나무라면 Leaf 노드는 나뭇잎이다.
•
레벨(Level)
◦
Tree에서 같은 깊이에 있는 노드들의 집합을 나타낸다.
◦
ex) 루트 노드 (0, 1 레벨), 루트 자식 노드는 2레벨
Tree 사용사례
NOTE
•
계층적 데이터 저장
◦
데이터를 계층 구조로 저장할 떄 사용한다.
◦
ex) 파일 및 폴더는 계층적 트리로 저장된다.
•
효율적인 검색 속도
◦
O(log n)의 평균시간으로 삽입, 삭제, 검색을 진행할 수 있다.
•
힙(Heap)
◦
힙도 트리로 구성된 자료구조다.
•
데이터베이스 인덱싱
◦
데이터 베이스 인덱싱을 구현하는데 트리를 사용한다.
◦
ex) B-Tree, B+Tree, AVL-Tree
•
Trie
◦
사전을 저장하는데 사용되는 특별한 종류의 트리다.
Binary Search Tree(BST) - 검색에 특화된 이진트리
NOTE
이진 트리 ⇒ 트리를 구성하는 노드와 자식이 최대 2개인 트리를 의미한다!
예시 이미지 1
얘시 이미지 2 (최악의 경우중 하나)
•
데이터 셋을 이분할 때, 무엇을 기준으로 이분할지에 따라서 특화된 이진 트리를 만들 수 있다.
◦
그 중 하나가 이진 검색 트리!
이진 트리 vs 이진 검색 트리
NOTE
이진 검색 트리 ⇒ 이진 트리가 “특별한 규칙”에 따라 데이터를 저장하는 형태의 자료구조!
•
특별한 규칙
1.
최상위 레벨에 루트 노드가 존재하면서, 각 노드는 최대 2개의 자식 노드를 가진다.
2.
특정 노드를 기준으로 자신의 왼쪽 하위 트리의 모든 노드는 자신보다 작아야 한다.
3.
특정 노드를 기준으로 자신의 오른쪽 하위 트리의 모든 노드는 자신보다 크거나 같아야 한다.
이진 검색 트리 - 검색
NOTE
8을 탐색하는 과정.
public static Node search(Node node, int data){
if(node == null) return null;
if(node.data == data) return node;
if(data < node.data) return search(node.left, data);
else return search(node.right, data);
}
Java
복사
구현 코드 (재귀 구현)
•
찾고자 하는 값이 현재 노드 보다 작다면, 왼쪽 하위 트리로 이동한다.
•
찾고자 하는 값이 현재 노드 보다 크다면, 오른쪽 하위 트리로 이동한다.
•
시간 복잡도
◦
평균 O(long n)
◦
최악의 경우 O(n) - 한 쪽으로만 쏠린 트리의 경우
이진 검색 트리 - 삽입
NOTE
7, 13, 40 순으로 삽입하는 과정
public static Node insert(Node node, int data){
if(node == null) return new Node(data);
if(node.data > data) node.left = insert(node.left, data);
else node.right = insert(node.right, data);
return node;
}
Java
복사
구현 코드(재귀 구현)
•
새로운 값을 추가할때 BST에 해당 값을 가진 노드가 없어야 한다.
•
시간 복잡도 : O(log n)
이진 검색 트리 - 삭제
NOTE
자식 노드가 1개인 경우 삭제 (그냥 붙이면됨)
자식 노드가 2개인 경우 삭제 (이때부터 고민해야한다)
public static Node delete(Node node, int data){
if(node == null) return null;
if(node.data > data) node.left = delete(node.left, data);
else if(node.data < data) node.right = delete(node.right, data);
else {
// 1. 리프노드 제거 경우
if(node.left == null && node.right==null) return null;
// 2. 자식 노드가 하나인 노드삭제
else if(node.left == null) return node.right;
else if(node.right == null) return node.left;
// 3. 자식 노드가 2개임
else{
Node prevNode = findMaxInLeftSubtree(node.left);
node.data = prevNode.data;
node.left = delete(node.left, prevNode.data);
}
}
return node;
}
// 가장 가까운값 찾는 함수
private static Node findMaxInLeftSubtree(Node node) {
if(node.right != null) return findMaxInLeftSubtree(node.right);
else return node;
}
Java
복사
구현 코드(재귀)
•
노드(40)을 삭제할 때, 노드(34)나 노드(49)중에 하나를 선택하면 트리가 깨진다.
•
정렬된 트리에서 값을 제거한 후 여전히 정렬을 유지해야 하므로, 다음과 같은 전략이 필요하다.
1.
이진 탐색으로 삭제할 노드(40) 검색
2.
정렬된 트리에서 노드(40)보다 작으면서 가강 가까운 값을 찾는다.
⇒ 노드(40)의 왼쪽 하위트리에서 가장 오른쪽에 있는 리프 노드
3.
두 값을 교환하고 리프 노드를 삭제한다.
•
시간 복잡도 : O(log n)
시간/공간 복잡도, BST 문제점
NOTE
BST 이외에도 Tree가 많다.
- BST는 평균과 최악의 시간복잡도가 다르다.
•
이진 검색 트리는 항상 효율성을 보장하지 않는다.
◦
트리의 형태가 불균형하게 될 경우, 이는 사실상 연결 리스트와 다음없는 연산의 시간 복잡도를 가진다.
•
이러한 문제를 해결하기 위해 고안된 것이, 균형 이진 검색트리(Balanced Binary Search Tree)다!
AVL Tree
AVL 트리는 어떻게 균형을 유지하는가?
NOTE
AVL 트리는 삽입이나 삭제 연산이 이루어진 직후에 트리의 균형을 유지하기 위해 “회전 연산”을 수행한다!
AVL 트리는 모든 노드의 왼쪽/오른쪽 자식 노드의 높이가 최대 1의 차이만 허용함
•
Blance Factor(균형 요소)를 활용한다.
◦
BF(K) ⇒ K의 왼쪽 서브트리의 높이 - K의 오른쪽 서브트리의 높이
◦
AVL의 트리는 모든 노드의 BF가 -1~1의 범위여야 한다.
◦
이를 벗어나면 회전이 필요하다!
회전 알고리즘
NOTE
AVL 트리에서는 회전의 유형으로 LL, LR, RR, RL이 존재하며 알파벳은 높이가 불균형한 서브트리의 방향을 나타낸다!
•
1번째 알파벳은 다른 노드에 비해 높이가 높은 서브트리의 방향을 나타낸다.
•
2번째 알파벳은 그 서브트리 내에서 높이가 높은 부분의 방향을 나타낸다.
LL (left-left) 회전
Right 회전을 거친다.
LR (left-right) 회전
Left → Right 회전을 거친다.
RR (right-right) 회전
left 회전을 거친다.
RL (right-left) 회전
Right - Left 회전을 거친다.
AVL Tree 구현의 핵심
NOTE
public void balance(type, Node node) {
switch type:
case LL:
rotateRight(node);
case LR:
rotateLeft(node); // 이 과정에서 tree를 LL 유형으로 만듬.
balance(LL, node);
case RR:
rotateLeft(node);
case RL:
rotateRight(node); // 이 과정에서 tree를 RR 유형으로 만듬.
balance(RR, node);
}
Java
복사
public void rotateRight(Node y) {
// 1. 노드 y의 왼쪽 자식을 x라고 합니다.
Node x = y.left;
// 2. x의 오른쪽 자식을 y의 왼쪽 자식으로 만듭니다.
y.left = x.right;
// x의 오른쪽 자식이 null이 아닌 경우, 해당 자식의 부모 포인터를 y로 업데이트합니다.
if (x.right != null) {
x.right.parent = y;
}
// 3. x의 부모 노드를 y의 부모 노드로 설정합니다.
x.parent = y.parent;
// 4. y의 부모 노드가 null이 아닌 경우 (y가 root가 아닌 경우),
// y의 부모 노드의 자식을 x로 업데이트합니다.
if (y.parent == null) {
// y가 루트였다면, 이제 x가 루트가 됩니다.
this.root = x;
} else {
if (y == y.parent.right) {
y.parent.right = x;
} else {
y.parent.left = x;
}
}
// 5. x의 오른쪽 자식을 y로 설정합니다.
x.right = y;
// 6. y의 부모 노드를 x로 설정합니다.
y.parent = x;
}
Java
복사
public void rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != null) {
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null) {
// x was the root
this.root = y;
} else {
if (x == x.parent.left) {
x.parent.left = y;
} else {
x.parent.right = y;
}
}
y.left = x;
x.parent = y;
}
Java
복사