Tree(트리)

1. 트리

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 좌측부터 순서대로 채워지는 이진 트리
(깊이가 k이고 노드 수가 n인 이진 트리이며, 각 노드들이 갚이 k인 포화 이진 트리에서 1부터 n까지의 번호를 붙인 노드들과 1대1로 일치하는 트리)
포화 이진 트리의 잎(Leaf)을 오른쪽부터 제거하여 얻어진 트리

아래의 조건을 만족하는 이진 트리
- 중복된 노드가 없어야 한다.
- 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
- 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
- 왼쪽 서브트리, 오른쪽 서브트리 또한 이진 탐색 트리이다.
중위 순회(In-Order traversal)를 하면 오름차순으로 정렬된 Key값을 얻을 수 있다.
시간 복잡도
- 탐색, 삽입, 삭제 : O(h) (h : height)
단점 : 한 쪽으로 치우쳐진 형태일 경우 height가 노드의 개수인 N과 동일하게 되어 시간 복잡도가 O(N)이 된다.
참고)
- 이진 탐색 트리란, 이진 탐색(binary search)과 연결 리스트(linked list)를 결합한 자료구조의 일종
- 이진 탐색의 효율적인 탐색 능력을 유지하면서도 빈번한 삽입, 삭제 가능
  - 이진 탐색
    - 탐색 : O(logN)
    - 삽입, 삭제 : 불가능
  - 연결 리스트
    - 탐색 : O(N)
    - 삽입, 삭제 : O(1)

최댓값 또는 최솟값이 root에 위치하여 O(1)의 속도로 검색이 가능한 완전 이진 트리
Max heap, Min heap
Max heap의 경우 부모 노드는 자식보다 무조건 커야 한다. (Min heap은 그 반대)
힙은 트리의 한 종류지만 완전 이진 트리의 특성을 활용하여 배열에 저장하는 것이 더 효율적(인덱스의 규칙 이용)
- 부모 index가 i일 때, 자식 index는 2i(왼쪽), 2i+1(오른쪽)
- 자식 index가 i일 때, 부모 index는 i/2
중복 값 허용
삽입(O(logN))
1. 삽입할 데이터를 완전 이진트리를 만족하는 비어있는 자리에 놓는다.
2. 새로운 노드와 그것의 부모노드를 계속 비교하여 부모가 더 크다는 조건을 만족할 때까지 반복
삭제(최댓값, 최솟값 삭제, O(logN))
1. 루트 노드를 삭제한다
2. 마지막 레벨의 마지막 노드를 루트에 올려 놓는다.
3. 힙의 조건을 만족할때까지 교환을 반복한다.