📌 Tree 트리
원소들 간에 1:N 관계를 가지는 비선형 자료구조
원소들 간에 계층관계를 가지는 계층형 자료구조
상위원소에서 하위원소로 내려가며 확장되는 트리(나무) 모양의 구조
트리는 노드와 간선으로 구성
트리에 사이클 존재 불가
노드 : 트리의 원소 → A,B,…,L 전체 다
루트 노드 : 트리의 시작 노드 → A
간선 : 노드를 연결하는 선. 부모노드와 자식 노드를 연결
형제 노드 : 같은 부모 노드의 자식 노드들 → B,C,D는 형제 노드
조상 노드 : 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들 → K의 조상 노드는 F,B,A
자손 노드 : 서브 트리에 있는 하위 레벨의 노드들 → B의 자손 노드는 E,F,K,L
서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리
- 각 노드는 자식 노드의 개수만큼 서브트리를 가진다
→ D는 3개의 서브트리를 가짐
차수
- 노드의 차수 : 연결된 자식 노드의 수를 의미 → A의 차수 3, B의 차수 2, C의 차수 1
- 트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값 → 트리 A의 차수는 3
단말노드 / 리프노드 : 차수가 0인 노드로, 자식 노드가 없는 노드 의미
- 비단말노드는 차수가 0이 아닌 노드
높이
- 노드의 높이 : 루트에서 노드에 이르는 간선의 수. 노드의 레벨 → B의 높이 1, F의 높이 2
- 트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값. 최대 레벨 → 트리A의 높이 3
레벨 : 높이와 비슷한 의미로 사용. 루트 노드의 레벨은 0,1을 혼용적으로 사용
📌 트리의 표현
해당 트리를 리스트만 이용하여 나타낼 경우 공간 낭비가 심해짐
어디를 어떻게 연결할건지, 얼마나 들어올건지 알 수가 없음
위와 같이 노드구조를 왼쪽 자식, 오른쪽 형제로 표현하여 이진트리 만들 수 있음
이렇게 바꿔주면 left child, right sibling만 연결하면 되므로 확장성이 매우 좋아짐
방법
- 첫번째 자식 노드 간선만 남기고 나머지 간선 제거
- 형제노드를 간선으로 연결
- 시계방향으로 45도 회전
📌 이진 트리
한 노드는 최대 두 개의 가지
왼쪽 서브트리와 오른쪽 서브트리 구별
0개의 노드를 가질 수 있음
⇒ 공백이거나 루트와 왼쪽 서브트리, 오른쪽 서브트리의 두 개의 분리된 이진 트리로 구성된 노드의 유한 집합
일반 트리와 이진 트리의 차이점
- 공백 이진 트리 존재
- 자식의 순서를 구별 → 아래 사진은 서로 다른 이진 트리임
편향 이진 트리 : 높이가 k일때 k개의 노드를 가지면서 모든 노드가 왼쪽이나 오른쪽 중 한 방향으로만 서브트리를 갖는 트리 → 즉, 한방향으로만 뻗어있다는 뜻
완전 이진 트리 : 값이 순서대로 들어와 있는 트리 (순서는 위, 왼쪽에서부터 1,2,3..)
포화 이진 트리 : 모든 레벨에 노드가 포화상태로 꽉 차있는 이진 트리
📌 이진 트리의 표현
-
배열을 활용한 표현
1차원 배열에 노드를 저장높이가 h인 이진 트리의 노드 번호를 배열의 인덱스로 사용
인덱스 0번 : 비워둠
→ 왼쪽 자식 노드는 2 오른쪽 자식 노드는 2 + 1
→ 이 번호를 찾기 쉽게 하기위해서 0번 인덱스는 비워둔다
인덱스 1번 : 루트 저장
단점은 낭비가 생길 수 있음
완전 이진 트리의 경우 낭비되는 공간 없음
편향 트리의 경우 공간 낭비 → 높이에 따라 배열 크기를 설정하므로, 최악의 경우 깊이 k의 편향 트리는 2^k -1개 중 k개만 사용
- 연결 자료구조를 이용한 이진 트리의 표현
노드 : 왼쪽 자식 노드 + 데이터 + 오른쪽 자식 노드
📌 이진 트리 순회
트리 순회 : 트리에 있는 모든 노드를 한 번씩만 방문
L 왼쪽이동, V 노드 방문, R 오른쪽 이동 → LVR, RLV, VLR 등등… 순회 방법 여러가지
왼쪽을 오른쪽보다 먼저 방문 한다고 한정할 경우(LR)
- LVR : 중위순회
수식 이진 트리를 중위 순회하면 수식에 대한 중위 표기식 구할 수 있음
→ + E D / C A B
- VLR : 전위순회 값을 먼저 확인
- LRV : 후위순회
📌 우선순위 큐
우선순위가 가장 높은(낮은) 원소를 먼저 삭제
임의의 우선순위를 가진 원소 삽입 가능
내부 요소는 힙으로 구성되어 이진트리 구조로 이루어짐
시간복잡도 O(nlogn)
import java.util.PriorityQueue;
import java.util.*;
//낮은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueLowest = new PriorityQueue<>();
//높은 숫자가 우선 순위인 int 형 우선순위 큐 선언
PriorityQueue<Integer> priorityQueueHighest = new PriorityQueue<>(Collections.reverseOrder());
동일하게 add / offer로 삽입. add는 성공시 true, offer는 실패시 exception
삽입 : 먼저 마지막에 넣고, 부모와 비교해서 더 작으면 교환하는 과정를 반복한다
삭제(루트노드) : 루트와 마지막 노드를 스왑하고 루트를 제거한 후 나머지 트리 올바르게 정렬
📌 최대 / 최소 힙
최대(최소) 트리 : 각 노드의 키 값이 그 자식의 키 값보다 작지(크지) 않은 트리 → 루트 노드의 값이 최대(최소)
최대 힙 : 최대 트리이면서 완전 이진 트리
최소 힙 : 최소 트리이면서 완전 이진 트리
최대 힙에서의 삽입
- 마지막 위치에 새로 삽입할 노드를 저장
- 부모원소와 비교하면서 {현재 부모의 값 ≥ 삽입 원소의 값} 관계가 성립하지 않으면 부모와 자리를 교환 → 즉 삽입원소 값이 부모보다 크면 교환한다는 것
- 관계가 성립할 때 까지 반복
최소힙의 경우 {현재 부모의 값 ≤ 삽입 원소의 값} 관계 성립하지 않으면 교환 → 즉, 삽입원소 값이 부모보다 작으면 교환
시간복잡도는 O(logn)
최대 힙에서의 삭제
- 루트의 원소를 삭제
- 마지막 노드를 루트 자리로 올림
- 최대 힙의 조건 만족시까지 부모노드와 자식노드의 비교 및 교환 반복
자바에서는 우선순위 큐라는 자료구조 라이브러리로 힙 지원
📌 이진 탐색 트리
이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조
이진 탐색의 탐색 시간복잡도 O(logn) + 연결 리스트의 삽입 삭제 시간복잡도 O(1)
효율적인 탐색,삽입, 삭제
모든 원소는 서로 다른 유일키를 가짐
왼쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 작다
오른쪽 서브트리에 있는 원소의 키들은 그 루트의 키보다 크다
왼쪽 서브트리와 오른쪽 서브트리도 이진 탐색 트리이다
이진 탐색 트리의 탐색
루트노드부터 시작하여 더 작으면 왼쪽, 크면 오른쪽으로 이동하며 비교
이진 탐색 트리의 삽입
루트노드부터 시작하여 비교한 후 맞는 위치에 삽입
이진 탐색 트리의 삭제
- 리프 노드의 삭제 : 그냥 삭제하면됨. 부모의 자식 필드에 0 삽입
- 하나의 자식을 가진 비리프 노드의 삭제 : 삭제된 노드의 자식을 삭제된 노드의 자리에 위치
- 두개의 자식을 가진 비리프 노드의 삭제 : 왼쪽 서브트리에서 가장 큰 원소나, 오른쪽 서브트리에서 가장 작은 원소로 대체
이진 탐색 트리의 탐색, 삽입, 삭제 시간복잡도 O(h) = O(logn) → h는 높이
최악의 경우(편향 트리) 시간복잡도 O(n) → AVL 트리, red-black tree로 해결
📌 Java & Red-Black Tree
java에서 treeset은 이진 탐색 트리 중에서도 성능을 향상시킨 레드 블랙 트리로 구현됨
TreeMap과 treeset의 차이점은 treeMap은 키와 값이 저장된 map, entry를 저장
TreeSet<Integer> set = new TreeSet<Integer>();//TreeSet생성
set.add(7); //값추가
set.add(4);
set.add(9);
set.remove(7);
set.clear(); //모든 값 제거레드 블랙 트리
- 각 노드의 색은 red or black
- 루트 노드는 black
- 모든 리프 노드는 black (없으면 NIL → 이것도 black)
- red노드의 자식들은 모두 black → 즉 red 연속 등장 불가
- 루트 노드에서 시작해서 자손인 리프노드에 이르는 모든 경로에 동일한 개수의 black 노드가 존재
실행 원리
새로 들어온 노드는 무조건 빨간색으로 한다
레드 노드는 연속 등장이 불가능함
더블 레드 발생 시 → 삼촌 노드 보기
- 삼촌이 빨간색이라면 : 리컬러링 → 부모들을 다 검은색으로 칠해버리고 할아버지는 레드, 만약 루트 노드가 있다면 그건 블랙으로 다시 칠함
- 삼촌이 검은색이라면 : restructuring → 나, 아버지, 할아버지를 정렬해서 위치를 다시 정해줌. 자식이 있는 노드가 있다면 그냥 원래 노드 따라감 → 왼 중 오 이렇게 바뀐다면 중간(위로 올라간)노드만 블랙, 나머지는 레드
하나가 삽입되었을때 이것을 여러번 진행할 수 도 있음
📌 AVL tree
Balance Factor = 왼쪽 높이 - 오른쪽 높이
→ Balance Factor의 절대값이 2 이상이면 안됨
문제터진 노드 기준으로 마지막에 들어온 노드로의 경로 판단해서 LL, LR, RR, RL 회전
RR : 왼쪽애를 꺾어내림
LL : 오른쪽애를 꺾어내림
LR : RR → LL
RL : LL → RR
