트리
노드 기반 자료구조
- 트리는 하나의 루트 노드를 가진다
- 루트 노드는 0개 이상의 자식 노드를 가진다
- 그 자식 노드 또한 0개 이상의 자식 노드를 가질 수 있다.
- 트리에는 순환 사이클이 존재할 수 없다.
- 각 노드는 어떠한 자료형으로도 표현될 수 있다.
대표적인 사용처가 힙과 컴퓨터 디렉토리
폴더에서 폴더로 넘어가는것처럼, 계층적인 구조를 가지는 것이 트리이다
노드: 트리를 구성하는 기본 원소
루트노드: 트리에서 부모가 없는 최상위 노드. 트리의 시작점
부모노드: 루트 노드 방향으로 직접 연결된 노드
자식노드: 루트 노드 반대방향으로 직접 연결된 노드
형제노드: 같은 부모를 갖는 노드들
리프노드: 루트 노드를 제외한 차수가 1인 정점(자식이 없는 노드)
경로: 한 노드에서 다른 한 노드로 이르는 길 사이에 있는 노드들의 순서
길이: 출발 노드에서 도착 노드까지 연결된 간선의 개수
깊이: 루트경로의 길이
레벨: 루트 노트부터 노드까지 연결된 간선 수의 합
높이: 트리의 최고 레벨
차수: 각 노드들의 자식의 개수
크기: 노드의 개수
너비: 가장 많은 노드를 갖고 있는 레벨의 크기
텍스트내부: 정점 차수가 2 이상인 정점
포레스트
서로 독립인 트리들의 모임(하나 이상의 트리들이 모인 집합)
방향 트리
방향을 무시하고 생각했을때 트리인 유향 그래프는 방향트리이다.
자료구조의 트리는 방향트리의 일종
이진트리
자식 노드의 개수를 최대 2개로 제한하는 트리의 가장 간단한 형태
반드시 왼쪽 자식과 오른쪽 자식을 구분하는 트리이다
왼쪽자식, 오른쪽 자식 용어를 사용한다.
힙 = 이진트리
트리의 순회
전위 순위
- 자신을 처리한다
- 왼쪽 자식을 방문한다
- 오른쪽 자식을 방문한다
중위 순위
- 왼쪽 자식을 방문한다
- 자신을 처리한다
- 오른쪽 자식을 방문한다
후위 순위
- 왼쪽 자식을 방문한다
- 오른쪽 자식을 방문한다
- 자신을 처리한다
이진 탐색 트리
BST, Binary Search Tree
정렬된 이진트리. 다음과 같은 규칙을 가지고 있다.
- 노드의 왼쪽 자식에는 노드보다 작은 키가 있는 노드만 포함된다.
- 노드의 오른쪽 자식에는 노드보다 큰 키가 있는 노드만 포함된다.
- 왼쪽 or 오른쪽 자식트리도 각각 이진 탐색트리어야 한다.
- 중복된 키를 허용하지 않는다.
힙
항상 완전 이진트리의 형태를 띄어야 하고, 부모의 값은 항상 자식의 값보다 크거나 작아야 하는 규칙이 있다.
(따라서 루트노드 참조로 최대값이나 최소값을 O(1)만에 찾을 수 있다)
데이터의 삽입과 삭제는 모두 O(LogN)이 소요된다
루트의 값이 항상 최대값이거나 최소값이므로, 이를 이용하여 우선순위 큐를 구현하거나,
힙 정렬을 만드는 등의 일을 할 수 있다.
삽입:
- 가장 끝의 자리에 노드 삽입
- 그 노드와 부모 노드를 서로 비교
- 규칙에 맞으면 그대로 두고, 아니면 부모와 교환한다
- 규칙에 맞을때 까지 3번 과정 반복
삭제:
최댓값 혹은 최솟값이 저장된 루트 노드만 제거할 수 있다.
1. 루트 노드를 제거한다
2. 루트 자리에 가장 마지막 노드를 삽입한다
3. 올라간 노드와 그의 자식들을 비교한다
4. 조건에 만족하면 그대로 두고, 그렇지 않으면 자식과 교환한다
5. 조건을 만족할 때까지 4의 과정을 반복한다
레드 블랙 트리
이진트리의 일종. 특정 조건을 지키면서 균형잡힌 이진트리가 되기 때문에
search, insert, delete연산을 최악의 경우에도 logN 안에 가능하다.
- 모든 노드는 빨간색 혹은 검은색이다
- 루트 노드는 검은색이다
- 모든 리프 노드(NIL)들은 검은색이다(NIL: null leaf. 자료를 갖지 않고 트리의 끝을 나타내는 노드)
- 빨간색 노드의 자식은 검은색이다 == 빨간색 노드가 연속으로 나올 수 없다 (검은색 노드는 연속으로 나올 수 있다)
- 모든 리프 노드에서 Black Depth는 같다 == 루트에서 NIL로 가는데 거쳐가는 검은 노드의 수는 같다
- 새로운 노드는 항상 빨간 노드로 삽입된다.
레드 블랙 트리의 삽입과정![]
노드를 삽입할때 No Double Node규칙을 위반하는 경우가 생긴다. 이 문제를 해결하기 위해 2가지 전략을 사용한다
삼촌 노드(부모의 형제노드)가 검은색이라면 Restructuring을 수행한다
삼촌 노드가 빨간색이라면 Recoloring을 수행한다.
Restructuring:
1.새로운 노드, 부모 노드, 조상 노드를 오름차순으로 정렬한다.
2.셋 중 중간값을 부모로 만들고, 나머지 둘을 자식으로 만든다
3.새로 부모가 된 노드를 검은색으로 만들고, 나머지 자식들을 빨간색으로 만든다
Restructuring 3step
(7은 5의 자식 노드였으므로 딸려가게 된다)
이후 새롭게 부모가 된 3을 검은색으로 바꿔주고, 나머지 두 자식인 2,5의 색을 빨간색으로 바꿔주면 문제가 해결된다.
ReColoring
1. 새로운 노드와 부모와 삼촌을 검은색으로 바꾸고, 조상을 빨간색으로 바꾼다
-1-1: 조상이 루트노드라면 검은색으로 바꾼다(루트노트는 검은색이라는 규칙을 위해)
-1-2: 조상을 빨간색으로 바꿨을때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행하여 발생하지 않을때까지 반복
