🌲 Tree
계층적인 구조를 나타내는 자료구조
Tree의 구성
- 노드(node)
트리를 구성하고 있는 각각의 요소
- 루트(root)
트리에서 최상위에 있는 노드
- 서브트리(subtree)
하나의 노드와 그 노드들의 자손들로 이루어진 트리
- 단말 노드(terminal node)
하위 노드가 없는 노드
- 비단말 노드(internal node)
적어도 하나의 하위 노드를 가지는 노드
Tree의 용어
- 레벨(level)
트리의 각 층의 번호
- 높이(height)
트리의 최대 레벨
- 차수(degree)
노드가 가지고 있는 하위 노드의 개수
Tree의 응용 분야
- 계층적인 조직 표현
- 파일 시스템
- 인공지능에서의 결정 트리
Binary Tree
모든 노드가 2개의 서브 트리를 가지고 있는 트리
- 서브 트리는 공집합일 수 있다.
- 이진 트리의 노드에는 최대 2개까지의 하위 노드가 존재한다.
- 모든 노드의 차수가 2 이하가 된다.
= 구현하기가 편리하다.
- 이진 트리에는 서브 트리 간의 순서가 존재한다.
Binary Tree의 성질
- 노드의 개수가
n
개이면 간선의 개수는 n-1
개
- 높이가
h
인 이진 트리의 경우, 최소 h
개의 노드를 가지며 최대 2
h
-1
개의 노드를 가진다.
n
개의 노드를 가지는 이진 트리의 높이는 최대 n
이거나 최소 log
2
(n+1)
Binary Tree의 분류
- Full Binary Tree(포화 이진 트리)
트리의 각 레벨에 노드가 꽉 차있는 이진 트리
- Complete Binary Tree(완전 이진 트리)
높이가 h
일 때 레벨 1
부터 h
까지는 노드가 모두 채워져 있고 마지막 레벨 h
에서는 왼쪽부터 오른쪽으로 순서대로 채워져 있는 이진 트리
Binary Tree의 표현
모든 이진 트리를 포화 이진 트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법
↙ A ↘
↙ B ↘ ↙ C ↘
↙ D ↘ ↙ E ↘ ↙ F ↘
포인터를 이용하여 상위 노드가 하위 노드를 가리키게 하는 방법
Binary Tree의 순회
- preorder traversal(전위 순회)
루트 → 왼쪽 하위 → 오른쪽 하위
- inorder traversal(중위 순회)
왼쪽 하위 → 루트 → 오른쪽 하위
- postorder traversal(후위 순회)
왼쪽 하위 → 오른쪽 하위 → 루트
- level-order traversal(레벨 순회)
루트부터 계층 별로 방문
수식 트리
산술식을 트리 형태로 표현한 것
- 비단말 노드(internal node) = 연산자(operator)
- 단말 노드(terminal node) = 피연산자(operand)
수식 트리 계산
후위 순회를 사용한다.
- 서브 트리의 값을 재귀 호출로 계산한다.
- 비단말노드를 방문할 때 양쪽 서브 트리의 값을 저장된 연산자를 이용하여 계산한다.
Thread Binary Tree
NULL 링크에 중위 순회 시에 후속 노드인 중위 후속자(inorder successor)를 저장시켜 놓은 트리
- 이진 트리의 NULL 링크를 이용하여 순환 호출 없이도 트리의 노드들을 순회한다.
- 단말 노드와 비단말노드의 구분을 위해
isThread
필드가 필요하다.
Binary Search Tree
탐색 작업을 효율적으로 하기 위한 자료 구조
- 이진 탐색 트리에 저장된 키는 유일하다.
- 왼쪽 서브 트리의 키 <= 루트 노드의 키 <= 오른쪽 서브 트리의 키
- 왼쪽/오른쪽 서브 트리도 이진 탐색 트리이다.
- 이진 탐색 트리를 중위 순회하면 오름차순으로 정렬된 값을 얻을 수 있다.
Binary Search Tree의 연산
탐색
- 비교한 결과가 같으면 탐색이 성공적으로 끝난다.
- 비교한 결과가 주어진 키 값이 루트 노드의 키 값보다 작으면 탐색은 이 루트 노드의 왼쪽 하위를 기준으로 다시 시작한다.
- 비교한 결과가 주어진 키 값이 루트 노드의 키 값보다 크면 탐색은 이 루트 노드의 오른쪽 자식을 기준으로 다시 시작한다.
삽입
- 이진 탐색 트리에 원소를 삽입하기 위해서는 먼저 탐색을 수행하는 것이 필요하다.
- 탐색에 실패한 위치가 새로운 노드를 삽입하는 위치가 된다.
삭제
- 삭제하려는 노드가 단말 노드일 경우
해당 노드만 삭제하면 된다.
- 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우
해당 노드를 삭제하고 서브 트리는 상위 노드에 붙여준다.
- 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우
해당 노드와 가장 비슷한 값을 가진 노드를 해당 노드 위치로 가져온다.
왼쪽 서브 트리에서 가장 큰 값과 오른쪽 서브 트리에서 가장 작은 값에서 가장 비슷한 값을 찾을 수 있다.
Binary Search Tree의 성능
이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는 트리의 높이 h
에 비례한다.
최선
- 이진 트리가 균형적으로 생성되어 있는 경우
- O(log2 n)
최악
- 한쪽으로 치우친 경사 이진 트리의 경우
- O(n)