1. 트리란?
- 비선형 자료구조이다.
- 원소들 간에
1:N관계를 가지는 자료구조이다. - 원소들 간에 계층관계를 가지는 계층형 자료구조이다.
- 상위 원소에서 하위원소로 내려가면서 확장되는 트리모양의 구조이다.
용어정리
노드 (node): 트리의 원소간선 (edge): 노드를 연결하는 선, 부모 노드와 자식 노드를 연결한다.루트 노드 (root node): 트리의 시작 노드형제 노드 (sibling node): 같은 부모 노드의 자식들조상 노드: 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들서브 트리 (subtree): 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리자손 노드: 서브 트리에 있는 하위 레벨의 노드들노드의 차수: 노드에 연결된 자식 노드의 수트리의 차수: 트리에 있는 노드의 차수 중에서 가장 큰 값단말 노드 (리프 노드): 차수가 0인 노드, 자식 노드가 없는 노드노드의 높이: 루트에서 노드에 이르는 간선의 수, 노드의 레벨트리의 높이: 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨
2. 이진 트리
모든 노드들이 2개 이내의 서브 트리를 갖는 특별한 형태의 트리이며, 각 노드가 자식 노드를 최대한 2개까지만 가질 수 있다.
자식은 보통 왼쪽 자식 / 오른쪽 자식으로 구분한다.
이진 트리의 특성
- 한 노드가 가질 수 있는 자식은 최대 2개이다.
- 아래 레벨로 내려갈수록 들어갈 수 있는 노드의 수가 많아진다.
- 한쪽으로만 계속 이어질 수도 있고, 양쪽으로 가득 찰 수도 있다.
포화 이진 트리
모든 레벨의 노드가 빈자리 없이 꽉 차 있는 이진 트리이다.
특징
- 모든 부모 노드가 자식을 2개씩 가지고 있다.
- 마지막 레벨까지 모든 자리가 채워져 있다.
- 같은 높이의 이진 트리 중 노드가 가장 많다.
핵심 단어
모든 레벨이 꽉 참
완전 이진 트리
노드가 위에서 아래로, 왼쪽부터 차례대로 채워진 이진 트리이다.
특징
- 마지막 레벨을 제외한 위쪽 레벨은 모두 채워져 있다.
- 마지막 레벨은 전부 차 있지 않아도 된다.
- 마지막 레벨의 노드는 반드시 왼쪽부터 채워져 있어야 한다.
- 중간에 빈자리가 있으면 완전 이진 트리가 아니다.
핵심 단어
왼쪽부터 빈자리 없이 채움
편향 이진 트리
노드들이 한쪽 방향으로만 계속 연결된 이진 트리이다.
특징
- 대부분의 노드가 자식을 1개만 가지고 있다.
- 한쪽으로 길게 늘어진 형태이다.
- 왼쪽으로만 이어지면 왼쪽 편향 이진 트리이다.
- 오른쪽으로만 이어지면 오른쪽 편향 이진 트리이다.
핵심 단어
한쪽으로만 계속 이어짐
3. 이진 트리 표현
배열을 이용해 이진 트리를 표현
이진 트리는 각 노드에 번호를 붙이고, 노드 번호를 배열의 인덱스처럼 사용해서 표현할 수 있다.
- 루트 노드 번호는
1 - 위에서 아래로, 왼쪽에서 오른쪽 순서로 번호를 붙인다.
- 배열의
0번 인덱스는 보통 사용하지 않는다.
노드 번호의 규칙
현재 노드 번호가 i일 때
부모 노드 → i // 2
왼쪽 자식 노드 → i * 2
오른쪽 자식 노드 → i * 2 + 1예를 들어 5번 노드의 부모는 2번, 왼쪽 자식은 10번, 오른쪽 자식은 11번이다.
배열 표현의 특징
- 포화 이진 트리와 완전 이진 트리는 노드 번호가 연속적으로 배치되어 배열로 표현하기 좋다.
- 반면 편향 이진 트리는 한쪽으로만 노드가 이어지기 때문에 배열 중간에 빈 공간이 많이 생겨 비효율적이다.
완전 이진 트리 → 배열 표현에 적합
편향 이진 트리 → 빈 공간이 많이 발생부모·자식 관계를 배열에 저장
부모 번호를 인덱스로 자식 저장
트리의 관계 자체를 배열에 저장할 수도 있다.
부모 번호를 배열의 인덱스로 사용하고, 해당 부모의 자식 번호를 저장한다.
부모 1 → 자식 2, 3
부모 2 → 자식 4
부모 3 → 자식 5즉, 부모를 알고 있을 때 자식을 찾기 편한 방식이다.
자식 번호를 인덱스로 부모 저장
반대로 자식 번호를 배열의 인덱스로 사용하고, 해당 자식의 부모 번호를 저장한다.
자식 2 → 부모 1
자식 3 → 부모 1
자식 4 → 부모 2
자식 5 → 부모 3즉, 자식을 알고 있을 때 부모를 찾기 편한 방식이다.
부모를 계속 따라 올라가면 조상과 루트도 찾을 수 있다.
5 → 3 → 1여기서 1이 루트 노드가 된다.
배열 표현의 단점
배열을 이용한 이진 트리는 구현이 간단하지만 다음과 같은 단점이 있다.
- 편향 이진 트리는 사용하지 않는 배열 공간이 많이 생김
- 노드를 추가하거나 삭제할 때 배열 크기 변경이 불편함
이러한 단점을 보완하기 위해 연결 리스트를 이용한 표현을 사용할 수 있다.
연결 리스트를 이용한 이진 트리 표현
각 노드는 다음 세 가지 정보를 가진다.
왼쪽 자식 | 데이터 | 오른쪽 자식left: 왼쪽 자식 노드data: 현재 노드의 값right: 오른쪽 자식 노드
자식이 없는 경우에는 해당 위치를 null로 둔다.
배열처럼 공간을 미리 만들어두는 것이 아니라 필요한 노드끼리 직접 연결하는 방식이다.
3. 순회
트리의 각 노드를 중복되지 않게 전부 방문하는 것 이다.
3가지의 기본적인 순회 방법
- 전위 순회 VLR
- 부모 노드 방문 후, 자식 노드를 좌,우 순서로 방문한다.
-
현재 노드 n을 방문해 처리한다. → V
-
현재 노드 n의 왼쪽 서브트리로 이동한다 → L
-
현재 노드 n의 오른쪽 서브트리로 이동한다. → R
preorder_traversr(T): # 전위 순회 if T: visit(T) preorder_traverse(T.left) preorder_traverse(T.right)
-
- 중위 순회 LVR
- 왼쪽 자식 노드, 부모 노드, 오른쪽 자식 노드 순으로 방문한다.
-
현재 노드 n의 왼쪽 서브트리로 이동한다. → L
-
현재 노드 n을 방문해 처리한다. → V
-
현재 노드 n의 오른쪽 서브트리로 이동한다 → R
inorder_traverse(T): # 중위 순회 if T: inorder_traverse(T.left) visit(T) inorder_traverse(T.right)
-
- 후위 순회 LRV
- 자식 노드를 좌,우 순서로 방문 후, 부모 노드로 방문한다.
-
현재 노드 n의 왼쪽 서브트리로 이동한다. → L
-
현재 노드 n을 오른쪽 서브트리로 이동한다. → R
-
현재 노드 n을 방문해 처리한다. → V
postorder_traverse(T): # 후위 순회 if T: postorder_traverse(T.left) postorder_traverse(T.right) visit(T)
-
4. 이진 탐색 트리 (BST, Binary Search Tree)
탐색 작업을 효율적으로 하기 위한 자료구조이며, 모든 원소는 서로 다른 유일한 키를 가진다.
key(왼쪽 서브트리) <key(루트 노드) <key(오른쪽 서브트리)- 중위순회를 하면 오름차순으로 정렬된 값을 얻을 수 있다.
이진 탐색 트리의 성능
- 탐색 / 삽입 / 삭제 시간은 트리 높이에 비례한다.
- 평균의 경우: 트리가 적당히 균형 잡혀 있어서 빠르다
- 최악의 경우: 편향 트리가 되어 한쪽으로 길게 늘어지면 느리다.
탐색 연산
- 루트에서 시작
- 탐색할 키 값 x를 루트 노드의 키 값과 비교한다.
- 서브트리에 대해서 순환적으로 탐색 연산을 반복한다.
삽입 연산
- 먼저 탐색 연산을 수행한다.
- 탐색 실패한 위치에 원소를 삽입한다.
5. 힙 (Heap)
완전 이진 트리에 있는 노드 중에서 키 값이 가장 크거나, 작은 노드를 찾기 위해서 만든 자료구조이다.
- 최대 힙
- 키 값이 가장 큰 노드를 찾기 위한 힙이다.
- 항상 부모 노드의 키 값 > 자식 노드의 키 값 조건을 만족한다.
- 루트 노드: 키 값이 가장 큰 노드이다.
- 최소 힙
- 키 값이 가장 작은 노드를 찾기 위한 힙이다.
- 항상 부모 노드의 키 값 < 자식 노드의 키 값 조건을 만족한다.
- 루트 노드: 키 값이 가장 작은 노드이다.
