[자료구조] 트리

🎞️ Tree

자료를 계층적으로(hierarchically) 저장하기 위한 자료구조

• 노드와 링크로 구성
• 모든 노드는 부모-자식 관계
  • root node: 부모가 없는 노드 (구조상 가장 높은 곳의 노드)
  • leaf node(단말 노드): 자식이 없는 노드
  • edge: 부모와 자식을 잇는 선
  • sibling node: 같은 부모를 갖는 노드
  • ancestor node: 부모의 부모 등

🎞️ Binary Tree

트리 중 각 노드의 자식노드가 최대 두개인 트리

• 두 노드 사이의 거리: 두 노드를 연결하는 경로를 구성하는 엣지의 개수
• 노드의 높이(height): 노드의 자손 노드 중 가장 멀리 떨어진 leaf node까지의 거리
• 트리의 높이 = 루트 노드의 높이
• 노드의 레벨
  • 루트 노드의 레벨 = 0
  • 차례로 증가

포화 이진 트리 (Full Binary Tree)

모든 노드가 두 개의 자식 노드를 갖거나 자식 노드가 없음

완전 이진 트리 (Complete Binary Tree)

높이가 h일 때 레벨 h-1까지는 모든 노드가 두개의 자식 노드를 가지고,
레벨 h에서는 왼쪽 노드가 순서대로 채워진 이진트리

Perfect Binary Tree

모든 노드가 두 개의 자식 노드를 가짐 (Full BT 조건 만족)
모든 leaf node의 depth/level이 같음

🎞️ Binary Search Tree

다음과 같은 특징을 갖는 이진트리

• 각 노드에 중복되지 않는 키
• 루트 노드의 왼쪽 서브트리는 해당 노드의 키보다 작은 키를 갖는 노드로 이루어짐
• 루트 노드의 오른쪽 서브트리는 해당 노드의 키보다 큰 키를 갖는 노드로 이루어짐
• 좌우 서브 트리도 모두 이진 탐색 트리

🎞️ 그래프와 트리의 차이

그래프

노드와 노드 간을 연결하는 간선으로 구성된 자료구조

특징

• 그래프는 순환/비순환 구조를 이룸
• 그래프는 방향이 있는 그래프와 방향이 없는 그래프가 있음
• 루트 노드/부모자식 관계 개념 X
• 2개 이상의 경로가 가능함 (무방향/방향/양방향)
• 네트워크 모델

트리

트리는 사이클이 존재하지 않는 방향 그래프

특징

• 부모자식 관계가 존재 > 레벨 존재
• 노드가 N개일 때 간선은 N-1개 존재
• 각 레벨 k에 존재하는 노드는 2^k개
• 방향성 존재
• 사이클 X
• 계층형 모델

🎞️ 이진 탐색에서 순회

Preorder Traversal (전위순회)

뿌리 > 왼쪽 자식 > 오른쪽 자식 순으로 탐색

Inorder Traversal (중위순회)

왼쪽 자식 > 뿌리 > 오른쪽 자식 순으로 탐색
결과: 오름차순으로 정렬된 값들

Postorder Traversal (후위순회)

왼쪽 자식 > 오른쪽 자식 > 뿌리

Level-order Traverasl (레벨 순회)

레벨순으로 왼쪽부터 탐색

🎞️ 이진탐색트리 시간복잡도

BST의 검색/삽입/삭제 연산은 O(h)의 시간복잡도를 가짐 (h = BST의 height)

BST가 균형이 깨졌을 경우 (skewed BST)

• Height of BST = BST의 node 개수(n) 가 됨
• 검색: O(n)
  • 값을 찾기 위해 트리의 모든 레벨을 탐색
• 삽입: O(n)
  • 값을 비교해가며 삽입할 위치를 찾아야하기 때문에 탐색이 필수적임
• 삭제: O(n)
  • 값을 비교해가며 삽입할 값의 위치를 찾아야해서 탐색이 필수

균형 잡힌 BST

• BST의 height = log(n)이 됨
  • n: 노드의 개수
• 검색: O(log n)
  • 정렬된 트리를 탐색하기 때문에 모든 노드를 비교하기보다는 비교마다 범위를 좁혀갈 수 있음
• 삽입: O(log n)
  • 탐색이 필요
• 삭제: O(log n)
  • 탐색이 필요

🎞️ 이진탐색트리의 한계점

트리가 한쪽으로 치우치면 시간복잡도가 O(N)에 가까워짐

• 루트 노드보다 큰 값부터 시작해서 계속 그 값보다 더 큰 값을 삽입하거나
• 루트 노드보다 작은 값부터 시작해서 계속 그 값보다 더 작은 값을 삽입할 때

🎞️ 이진탐색트리의 값 탐색, 삽입, 삭제 방법

탐색

• 기존 이진트리보다 탐색이 빠름
  • 탐색 연산: O(h)
    • h: 트리의 height
• 탐색 과정
  • 1. 루트 노드의 key와 찾고자 하는 값을 비교. 찾고자 하는 값이면 탐색 종료
  • 2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색 진행
  • 3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색 진행

삽입

1. 삽입할 값을 루트 노드와 비교. 같다면 오류 발생 (중복 값 허용 X)
2. 삽입할 값이 루트 노드의 key보다 작으면 왼쪽 서브 트리 탐색
   비어있으면 추가. 비어있지 않으면 다시 비교
3. 삽입할 값이 루트노드의 키보다 크면 오른쪽 서브트리를 탐색
   비어있으면 추가. 비어이있지 않으면 다시 비교

삭제

• 1. 삭제하려는 노드가 단말 노드일 경우
  • 부모 노드의 자식 노드를 null로 설정
  • 해당 노드는 삭제 (메모리 해제)
• 2. 삭제하려는 노드의 자식이 하나인 경우
  • 삭제할 노드의 자식노드를 삭제할 노드의 부모노드로 설정
  • 해당 노드는 삭제
• 3. 삭제하려는 노드의 자식이 두 개인 경우
  • (1) 삭제할 노드의 왼쪽 서브트리에서 가장 큰 자손을 해당 노드의 자리에 올림
  • (2) 삭제할 노드의 오른쪽 서브트리에서 가장 작은 자손을 해당 노드의 자리에 올림

---

• [자료구조] 이진탐색트리(Binary Search Tree)의 개념, 이해 | C언어 이진탐색트리 구현