[1028알고리즘 15]트리, 힙

트리

계층형 비선형 자료구조.(큐, 스택 : 선형구조)

Node : 트리에서 데이터를 저장하는 기본요소

Root Node : 트리 맨 위에 있는 노드

Level: 최상위 노드를 Level 0으로 하였을때 하위 B 브렌치로 연결된 노드의 깊이

Parent Node: 어떤 노드의 하위 레벨에 연결된노드

Child Node : 어떤 노드의 상위 레벨에 연결된 노드

Leaf Node(Terminal Node) Child Node가 하나도 없는 노드

Sibling : 동일한 Parent Node를 가진노드    *자매 형제 시빌링

Depth: 트리에서 Node가 가질 수 있는 최대 Level

이진트리, 이진 탐색트리, 균형트리(AVL, red-black), 이진힙(최대힙, 최소힙)

이진트리

노드가 최대 두 개의 자식을 가진다.

하위 노드가 4~5가 될수 없고 무조건 0, 1, 2 개만 가능

완전이진트리

Complete Binary Tree

: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입해야 한다.

> 완전이진 트리만 배열로 표현 가능.

8             [None, 8]

6  3          [None, 8, 6, 3]

4  2  5       [None, 8, 6, 3, 4, 2, 5]

현재 인덱스 * 2 >>왼쪽자식의 인덱스

현재 인덱스 *2+1 >> 오른쪽 자식의 인덱스

현재 인덱스 //2 부모의 인덱스

8의 왼쪽자식은.  1*2  6, 오른쪽자식은 3

완전 이진 트리의 높이 : 각 레벨의 꽉 차있을떄  Level k >> 2^k개,   1+ 2^1+2^2+2^h ...

최대 노드 개수 N>> 2^h - 1

높이는 : h = log2(N+1), O(log(N))

힙

데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진트리

큰 값이 항상 상위레벨, 작은값이 항상 하위레벨  (Max Heap)or 반대(Min Heap)로  구현되야 함.

8

63

421

> 4보다 3이 크지만. 부모가 아니라 상관없음. 부모 자식 관계만보면됨

Max heap 에 원소 추가.

Min heap 에 원소 추가.

1. 원소를 맨 마지막에 넣습니다.

2. 부모노드와 비교합니다. 대소관계가 맞지 않으면 자리를 바꿉니다.

3. 2번을 반복합니다.

Max heap, Min Heap 원소 삭제 ==루트노드를 삭제

1. 루트 노드와 맨 끝에 있는 원소를 교체
2. 맨뒤에 있는원소(원래 루트노드)를 삭제한다.
3. 변경된 노드와 자식노드를 비교한다.  대소관계가 맞지 않으면 자리를 바꿈
4. 자식 노드 둘 보다 부모 도드가 크거나 가장 바닥에 도달하지 않을때까지 3 반복
5. 2에서 제거한 원래 루트 노드를 반환합니다.