[CS스터디] 트리 & 이진 탐색 트리

지영·2023년 5월 29일
0

CS

목록 보기
14/77
post-custom-banner

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. 레드 블랙 트리

: 이진탐색트리의 균형 문제를 해결하는 자료구조, 루트는 블랙으로 하며 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.

profile
꾸준함의 힘을 아는 개발자📍
post-custom-banner

0개의 댓글