4.3 비선형 자료구조 (2)

트리: 그래프의 한 종류로 사이클이 없어서 계층적 관계를 표현

- 루트 노트: 부모 노드가 없는 노드

- 부모 노드: 루트 노드 방향으로 연결된 노드

- 자식 노드: 루트 노드의 반대 방향으로 연결된 노드

- 단말 노드: 자식 노드가 없는 노드

- 형제 노드: 부모 노드가 같은 노드

- 레벨: 루트 노드로부터 노드의 상대적 위치를 의미

- 높이: 트리의 최대 레벨 + 1

- 차수: 자식 노드의 개수를 의미 

 

*이진 트리

: 자식 노드가 최대 2개인 트리

① 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨에 노드가 채워져 있음

② 포화 이진 트리: 마지막 레벨까지 노드가 모두 채워져 있는 이진 트리
③ 이진 탐색 트리: 왼쪽 서브 트리는 해당 노드의 값보다 작은 값을 가진 노드로 구성되고, 오른쪽 서브 트리는 해당 노드의 값보다 큰 값을 가진 노드로 구성된 트리 -> 균형이 잡힌 이진트리 값 검색에 O(log n)이 소요

*균형 이진 탐색 트리

1.  레드-블랙 트리

: 노드가 검은색 또는 빨간색인 트리

2.  AVL 트리

: 자가 균형 이진 탐색 트리로, 왼쪽 서브 트리와 오른쪽 서브 트리의 높이 차이를 유지해 균형을 잡는 트리

 

① LL 불균형 

② RR 불균형

③ LR 불균형

④ RL 불균형