[Section2] 04. 자료구조와 알고리즘 - Graph, Tree 1 / 20230515

🧑🏻‍💻 TIL(Today I Learned)

---

✔️ Tree, Graph

 

1. Tree(트리)

➡️ 그래프의 여러 구조 중 단방향 그래프의 한 구조
➡️ 하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무를 닮았다고 해서 트리 구조라고 부름

➡️ 데이터가 바로 아래에 있는 하나 이상의 데이터에 무방향으로 연결된 계층적 자료구조 
    : 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조 
       (트리구조는 계층적으로 표현이 되고 아래로만 뻗어나가기 때문에 사이클이 없음)

 

트리 구조

루트(Root)라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선(Edge)으로 연결, 
각 데이터를 노드(Node)라고 하며 두 개의 노드가 상하 계층으로 연결되면 부모/자식 관계 가짐 
자식이 없는 노드는 나무의 잎과 같다고 하여 리프 노드(leaf Node)라고 부름
같은 레벨에 나란히 있는 노드를 형제 노드(Sibling Node)라고 부름(같은 부모로부터 파생)

 

트리 구조의 레벨과 서브 트리

➡️ 자료 구조  Tree는 깊이와 높이, 레벨 등을 측정할 수 있음

• 깊이(depth)
  : 트리 구조에서는 루트로부터 하위 계층의 특정 노드까지의 깊이(depth) 표현할 수 있음 
    위 그림을 예로 들면 루트 노드는 지면에 있는 것처럼 깊이가 0, B와 C의 깊이는 1, D/E/F/G의 깊이는 2
• 레벨(level)
  : 트리 구조에서 같은 깊이를 가지고 있는 노드 묶어서 레벨(level)로 표현 가능 
    depth가 0인 루트 A의 레벨은 1, depth가 1인 B와 C의 레벨은 2, D/E/F/G의 레벨은 3 
• 높이(Height)
  : 트리 구조에서 리프 노드를 기준으로 루트까지의 높이(Height) 표현할 수 있음 
    리프 노드와 직간접적으로 연결된 노드의 높이를 표현, 부모 노드는 자식 노드의 가장 높은 Height 값 + 1 한 것을 높이로 가짐
    트리 구조의 높이를 표현할 때는 각 리프 노드의 높이를 0으로 놓음 
    위 그림을 예로 들면 H, I, E, F, J의 높이는 0 / D, G의 높이는 1 / B, C의 높이는 2 / A의 높이는 3
• 서브 트리(Sub Tree)
  : 트리 구조의 root에서 뻗어 나오는 큰 트리의 내부에 트리 구조를 갖춘 작은 트리
    위 그림을 예로 들면 (D, H, I) / (B, D, E) / (C, F, G, J)도 서브 트리 

 

✍🏻 Tree 의 장점

1. 효과적인 계층 구조 표현 
2. 정렬과 탐색에 활용
   → 이진 탐색 트리, 힙(Heap)과 같은 다양한 형태로 사용될 수 있고 정렬과 탐색을 위한 알고리즘을 구현하는 데에도 사용됨
3. 삽입과 삭제가 쉬움
   → 삽입 및 삭제 시에 해당 노드의 부모와 자식 노드만 수정하면 됨 
4. 구조 파악 용이
   → Tree 자료 구조는 시각화가 쉬워 이해하기 쉬움 
5. 다양한 분야에서 활용 

 

🔎 Binary Tree(이진 트리)

➡️ 자식 노드가 최대 두 개인 노드들로 구성된 트리 → 이 자식 노드들은 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있음 

➡️ 이진 트리는 이진 탐색 트리와 이진 힙 구현에 사용되며, 효율적인 검색과 정렬을 위해 사용됨

➡️ 이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리, 완전 이진 트리, 포화 이진 트리 세 가지로 나뉨

• 정 이진 트리(Full binary tree)
  :  각 노드가 0개 혹은 2개의 자식 노드를 가짐 
• 포화 이진 트리(Perfect binary tree)
  : 정 이진 트리이면서 완전 이진 트리인 경우, 모든 리프 노드의 레벨이 갖고 모든 레벨이 가득 채워져 있는 트리
• 완전 이진 트리(Complete binary tree)
  : 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 함

 

🔎 Binary Search Tree(이진 탐색 트리)

이진 탐색 트리

➡️ 이진 탐색의 속성이 이진 트리에 적용된 특별한 형태의 이진 트리 

📍 이진 탐색이란? 
: 정렬된 데이터 중에서 특정한 값을 찾기 위한 탐색 알고리즘 중 하나
  오름차순으로 정렬된 데이터를 같은 크기의 두 부분으로 나눈 후,
  두 부분 중 탐색이 필요한 부분에서만 탐색하도록 탐색 범위를 제한하여 원하는 값을 찾는 알고리즘

1. 전체 데이터 중간에서 내가 찾고자 하는 값이 있는지 확인
2. 중간값이 내가 찾고자 하는 값이 아닐 경우, 오름차순으로 정렬된 데이터에서 중간값보다 큰 값인지 작은 값인지 판단
3. 찾고자 하는 값이 중간값보다 작은값일 경우, 데이터의 맨 앞부터 중간값 전까지의 범위를 탐색 범위로 잡고 탐색 반복 수행
4. 찾고자 하는 값이 중간값보다 큰 값일 경우, 데이터 중간값의 다음 값부터 맨 마지막까지 탐색 범위로 잡고 탐색 반복 수행 

 

➡️ 이진 탐색 트리에서 트리의 루트 노드는 전체 데이터의 중간값이 됨 
     : 이진 탐색 알고리즘에 기반하여 루트노드의 왼쪽 서브 트리의 값은 모두 루트 노드의 값보다 작은 값들이고 루트노드의 오른쪽 서브
       트리의 값들은 루트노드의 값보다 큰 값들이 자리 잡고 있음 => 중요 특징!

➡️ 이진 탐색 트리는 균형 잡힌 트리가 아닐 때 입력되는 값 순서에 따라 한쪽으로 노드들이 몰릴 수 있음
     : 균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결하기 위해서 삽입과 삭제마다 트리의 구조를 재조정
       하는 과정을 거치는 알고리즘을 추가할 수 있음

 

 

✍🏻 이진 탐색 트리 탐색 과정 

➡️ 기존 이진 트리보다 탐색이 빠르다는 장점

➡️ 연산은 트리의 높이가 h(height) 라면 o(h)의 복잡도를 가지게 됨 

1. 루트 노드의 키와 찾고자 하는 값을 비교, 만약 찾고자 하는 값이라면 탐색 종료
2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색 진행
3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 탐색 진행

➡️ 위의 과정을 찾고자 하는 값을 찾을 때까지 반복해서 진행하고 만약 값을 찾지 못하면 그대로 연산 종료 
➡️ 위와 같은 탐색 과정을 거치면 최대 트리의 높이만큼 탐색을 진행함
    : 트리 안에 찾고자 하는 값이 없더라도 최대 h번(트리의 높이)만큼의 연산 및 탐색이 진행됨

 

 

✍🏻 이진 탐색 트리에서의 노드 추가

➡️ 노드의 값이 현재 노드보다 작으면 왼쪽 서브 트리에 크면 오른쪽 서브 트리에 추가 
     : 노드를 삽입하려는 위치까지 재귀적으로 탐색하여 이루어짐 

➡️ 삽입된 노드를 기준으로 다시 왼쪽과 오른쪽 서브 트리가 이진 탐색 트리의 특성을 만족하는지 확인하면서 트리 구조 유지

 

 

✍🏻 이진 탐색 트리에서의 노드 삭제 

➡️ 삭제할 노드가 리프 노드인 경우, 리프 노드는 자식 노드가 없기 때문에 그냥 삭제하면 됨

➡️ 삭제할 노드가 자식 노드가 하나인 경우, 삭제할 노드의 부모 노드와 삭제할 노드의 자식 노드를 연결해 주면 됨

• 만약 위 그림에서 3을 제거한다면 
  1. 3을 키로 가지는 노드를 제거하면서, 기존의 2라는 키를 가진 노드의 위치를 삭제된 데이터의 위치로 이동
  2. 삭제가 완료되며 정렬 완료됨

➡️ 삭제할 노드가 자식 노드가 두 개인 경우, 삭제할 노드를 대체할 노드를 찾아야 함 
    : 대체할 노드는 삭제할 노드의 오른쪽 서브 트리 중 가장 작은 값의 노드 혹은 삭제할 노드의 왼쪽 서브 트리 중 가장 큰 값의 노드 
      대체할 노드를 찾으면 삭제할 노드와 대체할 노드 교환, 그 다음 삭제

• 만약 위 그림에서 5를 삭제한다면
  1. 5를 가지고 있는 노드를 대체할 노드 찾기
  2. 좌측 자식에서 가장 큰 값을 가진 노드는 3, 우측 자식에서 가장 작은 값을 가진 노드는 6
  3. 3과 5의 위치 변경
  4. 5 삭제 
     → 지우는 과정은 5의 자식 유무에 따라 자식 노드가 없는 경우, 자식 노드가 하나인 경우, 자식 노드가 두 개인 경우에 따라 다시 삭제 작업을 재귀적으로 실행