학습 일자 : 2023.04.25

트리

계층적인 자료를 나타내는 데 자주 사용되는 자료구조

부모 노드가 0개 이상의 자식 노드들을 가질 수 있음

순환구조를 가질 수 없는 계층형 구조

• 순환 구조 : 한 노드에서 출발하여 다시 자기 자신의 노드로 돌아오는 구조 (순환 구조를 가진 자료 구조는 그래프임)

이진 탐색 트리

이진속성과 탐색속성을 적용한 트리

• 이진 속성 : 탐색 트리 중 자식 노드가 최대 2개 가지고 있는 자료구조.
• 탐색 속성 : 자신의 노드보다 작은 값들은 왼쪽, 큰 값들은 오른쪽에 위치 → 정렬이 보장 됨.

이진탐색을 통한 탐색영역을 절반으로 줄여가며 탐색 가능 → 탐색에 유용함

이진탐색트리의 시간복잡도

기본적으로 조건에 맞지 않는 절반은 신경 쓸 필요가 없는 컨셉이기 때문에 효율적임.

but, 이진탐색트리의 노드들이 한쪽 자식으로만 추가되는 불균형 발생 가능함. 이 경우 탐색영역이 절반으로 줄여지지 않기 때문에 시간복잡도 증가할 수 있음.

→ 불균형한 트리는 접근, 탐색, 삽입, 삭제 모두 O(n)을 가지는 자료구조가 됨. ⇒ 이진트리의 한계

이러한 현상을 막기 위해 자가균형기능을 추가한 트리의 사용이 일반적임.

대표적인 방식으로 Red-Black Tree, AVL Tree 등이 있음

→ 균형을 맞추기 위해 우회전, 좌회전 기능을 씀

Red-Black Tree

이진 트리 순회

노드 구조에서 값을 언제 확인하는냐에 따라서 순회 종류나 나뉜다.

• 전위순회

  데이터 > Left > Right

  A → B → D → H → I → E → J → K → C → F → G

• 중위 순회

  Left > 데이터 > Right

  H → D → I → B → J → E → K → A → F → C → G

  💡 이진탐색 트리는 중위 순회를 함

• 후위 순회

  Left > Right > 데이터

  H → I → D → J → K → E → B → F → G → C → A