1_1. 트리란?
: Node(값을 가진 노드)와 Edge(노드를 연결하는 간선)로 이루어진 자료구조
* 루트 노드 : 이미지 상에서 1을 가진 노드
* 모든 노드들은 0개 이상의 자식 노드를 가짐 (부모-자식 관계)✔️ 트리의 특성
- 사이클이 존재하지 않음 (그래프와의 차이점)
- 루트에서 한 노드로 가는 경로는 유일하다
- 노드의 개수가 N개면, 간선의 개수는 (N-1)개이다
1_2. 트리 순회 방식
1) 전위 순회 (pre-order)
: 루트 -> 왼쪽 -> 오른쪽, 각 루트를 순차적으로 방문
1 - 2 - 4 - 8 - 9 - 5 - 10 - 11 - 3 - 6 - 13 - 7 - 14
2) 중위 순회 (in-order)
: 왼쪽 -> 루트 -> 오른쪽, 왼쪽 하위 노드를 먼저 방문 후 루트를 방문
8 - 4 - 9 - 2 - 10 - 5 - 11 - 1 - 6 - 13 - 3 - 14 - 7
3) 후위 순회 (post-order)
: 왼쪽 -> 오른쪽 -> 루트 , 왼쪽 하위 트리부터 오른쪽 하위 트리까지 방문 후 루트를 방문
8 - 9 - 4 - 10 - 11 - 5 - 2 - 13 - 6 - 14 - 7 - 3 - 1
4) 레벨 순회 (level-order)
: 루트부터 계층 별로 방문
1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9 - 10 - 11 - 12 - 13
1_3. 트리의 종류
1) 이진 트리
: 기본적인 형태. 모든 노드의 차수가 2이하인 트리
2) 포화 이진 트리
: 모든 레벨이 꽉 찬 이진 트리
3) 완전 이진 트리
: 단말노드를 제외하고 모든 노드가 위에서 아래로, 왼쪽에서 오른쪽을 차곡차곡 채워진 트리
2. 이진 탐색 트리
: 효율적으로 데이터를 탐색하도록 만든 자료구조, 이진 트리의 한 종류.
특징
1. 각 노드에 중복되는 키(데이터)가 없다
2. 루트 노드의 왼쪽 서브 트리는 루트노드보다 작은 데이터를 갖는 노드들로 이루어 진다.
3. 루트 노드의 오른쪽 서브 트리는 루트노드보다 큰 데이터를 갖는 노드들로 이루어 진다.
4. 좌우 서브 트리도 모두 이진 탐색 트리여야 한다.
이진 탐색 트리의 시간 복잡도 ⏳
: 트리의 높이가 h라면 O(h)의 시간 복잡도를 가진다. (중위순회 방식으로 데이터를 읽음)
2_1. BST
- 핵심 연산 : 검색, 삽입, 삭제, 트리 생성, 트리 삭제
- 시간 복잡도
- 편향 트리 : 노드 개수가 N개일 때 O(N)
- 균등 트리 : 노드 개수 N개일 때 O(logN)
2_2. AVL
: 이진탐색트리의 균형 문제를 해결하는 자료구조, 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1 이하가 되도록 함
2_2. 레드 블랙 트리
: 이진탐색트리의 균형 문제를 해결하는 자료구조, 루트는 블랙으로 하며 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
