[Data_Structure]Tree, Heap

Tree

1. 한 노드가 여러 노드를 가르킬 수 있는 비선형적 자료구조
2. 리스트나 큐, 스택은 데이터의 이전 데이터나 다음 데이터의 순서가 존재 했었음. 물론 트리도 순서 정보를 가지도록 구현이 가능. But, 트리라는 자료구조 자체에서 데이터의 순서는 그리 중요하지 않음
3. 그래프라는 자료구조의 일종
4. 데이터구조의 상하관계(계층적인) 개념 표현시 사용가능
5. 트리의 형태 도식화

이미지 출처 : https://www.tutorialandexample.com/tree-in-ds/

1. 용어 정리**

   • 부모가 없는 최상위 Node를 Root Node→ 트리의 시작점 (최대 1개의 Root Node)
   • Node를 연결하는 Node간선을 Edge
   • 계층적 속성에서 상위에 존재하는 Node→ Parent Node
   • Parent Node하위 → Children Node
   • 같은 부모를 갖는 Node = Sibling Node
   • 각 Node의 자식 수는 Degree로 표현 함 Ex) 자식이 3 ⇒ degree3
   • 자식이 없는 Node = Leaf Node(Terminal Node라고 함) 데이터의 끝부분 : 위 사진에서 H, I,K,O,P가 Leaf Node
   • 노드순서(경로) = path / 중복노드 포함 X
   • 노드에서 Root까지 길이를 Depth / 위 사진에서 Root 와 Level2 까지의 거리는 Depth2 / 가장 큰 Depth는 트리의 높이라고도 함
   • 같은 Depth를 가진 노드의 집합을 Level이라고 함
   • 위 사진에서 A는 당연히 Tree. B 또한 B를 Root로 하는 하나의 서브 Tree가 되는 것. B의 자식인 D도 마찬가지 ⇒ Tree는 재귀적인 구조를 갖고 있음
   • 트리의 모든 노드가 하나의 자식만을 갖는 트리를 경사트리라고 하고 모든 노드가 왼쪽의 자식만 가질 경우 왼쪽 경사 트리라고 함. 오른쪽 경사 트리도 가능함.

2. 이진 트리

   • 각 노드가 최대 2개(0-2)의 자식 노드를 가지는 트리
     → 왼쪽 자식노드/오른쪽 자식노드 : 위치가 다르면 두 트리는 다른 트리가 됨
   • 이진 트리 중 모든 노드가 2개의 자식을 가지거나 자식이 없는 경우 : 정 이진 트리(full binary tree) 또는 엄격한(strict) 이진 트리라고 함
     → 자식이 한개인 경우가 없어야 이에 해당
   • 모든 노드가 2개의 자식을 가지고 leaf 노드가 같은 레벨일 때 : 포화 이진 트리(Perfect Binary Tree) → 높이가 h일 때, 노드 갯수가 2^(k+1) - 1개라는 특징.
     → leaf Node 갯수 2^h
     
     
   • 완전 이진 트리(Complete Binary Tree)
     1. 마지막 레벨을 제외하고 모든 노드가 채워져야 함. 하지만, 마지막 레벨은 다 채워져 있을 수도 있고, 아닐 수도 있음
     2. 노드는 왼쪽에서 오른쪽으로 채워짐
        
        
   • 선형자료구조인 일차원 배열로 표현 가능
     1. 완전 이진 트리는 각 번호를 인덱스로 써서 일차원 배열로 표현이 가능. 빈틈 없음
     2. 중간에 빈 값이 있는 트리는 배열로 표현하면 비어있는 공간에 “null”값이 들어간 일차원 배열로 표현 가능→ i번째 인덱스에 들어있는 노드의 부모는 i/2 인덱스의 위치→ 노드 i의 오른쪽 자식은 i*2+1
     3. 각 노드의 next point 대신 왼쪽과 오른쪽 자식을 가르킬 수 있는 left와 right point를 두어 연결관계를 표현하게 됨
     4. → 노드 i의 왼쪽 자식은 i*2
     5. → 0번째 인덱스를 비워두고 첫 번째 인덱스 부터 Root값이 들어감
        
        
   • 이진 트리의 응용
     1. 힙, 이진 탐색 트리, B-tree(데이터베이스나 파일시스템에서 다룸), AVL 트리(트리 자료구조에 대해 이해가 되면 공부)
        
        
   • 트리 순회
     • 트리 구조에서 각 노드를 한 번씩 방문하는 과정
       1. 전위 탐색 preorder
          • (루트)노드 방문이 먼저 이루어짐
          • 왼쪽 서브 트리를 preorder : 재귀호출로 탐색이 이루어진다는 것을 의미함
          • 오른쪽 서브 트리를 preorder
       2. 중위 탐색 inorder
          • 왼쪽 서브 트리를 inorder
          • (루트)노드 방문
          • 오른쪽 서브 트리를 inorder
       3. 후위 탐색 postorder
          • 왼쪽 서브 트리를 postorder
          • 오른쪽 서브 트리를 postorder
          • (루트)노드 방문
     → Node 방문을 언제 하느냐로 구분 가능

이진 탐색 트리(Binary Search Tree)

• 데이터의 특성에 제약을 줌으로써 탐색 속도를 O(logN)으로 줄여줌
• 이진 트리의 구조
  • 왼쪽 자식노드와 오른쪽 자식 노드를 가질 수 있음
• 일반적인 이진 트리와의 차이점 : 데이터 값에 제약이 생김
• 루트 노드를 기준으로
  • 왼쪽 서브 트리에는 루트 노드보다 작은 값들로만 이루어져야 하며
  • 오른쪽 서브 트리에는 루트 노드보다 큰 값들로만 이루어져야 함
• 중위 탐색을 통해 순서대로 노드를 가져올 수 있음
• 데이터 삽입
  • 중복된 데이터 삽입 X → 삽입의 과정에서 같은 값이 있다면 삽입되지 않고 그대로 종료가 됨
  • 데이터의 삽입이나 삭제가 이루어져도 그 특성이 유지되어야 함 → 데이터가 삽입될 때에는 자신이 들어가야 할 위치부터 찾게 됨 / 추가된 노드는 트리의 leaf에 삽입
• 데이터 삭제
  1. 삭제 데이터 위치 찾기
  2. 삭제할 테이터가 leaf인 경우
     1. null을 부모노드에게 return 시켜 자신을 가르키던 자식 포인터를 null을 가르키게
  3. 한 개의 자식 노드를 가질 경우
     1. 하나있는 자식 노드를 부모 노드로 연결시켜 주면 됌
  4. 두 개의 자식 노드를 가질 경우
     1. 왼쪽 서브 트리의 최댓값과 교체
     2. 오른쪽 서브 트리의 최솟값과 교체

Heap

• 자료구조 힙
• java 메모리 영역

1. 완전 이진 트리
2. 최대 힙(Max Heap)
   1. 부모노드가 항상 자식 노드보다 크거나 같음
   2. 루트 노드 = 트리의 최댓값
3. 최소 힙(Min Heap)
   1. 부모 노드가 항상 자식 노드보다 작거나 같음
   2. 루트 노드 = 트리의 최솟값
4. 이진 탐색 트리와 다르게 값의 중복 허용
5. 이진 탐색 트리는 좌우 노드 간에 크기 제약 있었지만 힙은 없음. 하지만 상하관계에서는 있음
6. 최대/최소값을 빠르게 가져와야 할 상황에서 가장 빠름 → O(1)
7. 삽입/삭제 → O(logN)
8. 우선순위 큐(Priority Queue)
   • 일반 큐와 달리 우선순위가 높은 데이터 순으로 처리 (기준에 따라)
9. 1차원 배열로 표현 가능 → node 탐색의 용이성 때문에 배열의 0번이 아닌 1번 인덱스부터 root 값을 채움
10. Heapify

• 힙의 데이터가 추가 되거나 삭제 되어도, max,min 속성이 유지되어야 함 → 재구조화
• 데이터 삽입
  1. 완전 이진 트리의 형태를 유지 해야하기 때문에 우선 leaf 노드에 삽입
  2. 힙의 조건 충족하는지 확인
  3. 만족하지 않는다면 삽입된 노드와 부모 노드의 값 바꿈 - 반복 후 이후 2번 충족여부 확인
• Max Heap에서 최대값 데이터 삭제
  1. 마지막 노드를 루트 노드로 가져오면서 최대값을 제거
  2. 힙의 조건 충족 여부 확인
  3. 자식 노드와 위치 바꿈 - 반복 후 다시 조건 충족 여부 확인