7. 자료구조 - 트리, 이진트리, 힙

2018.11.26 (월)

DS - 트리
그래프와는 다르게 여러 노드가 한 노드를 가리키지 않고 한 노드를 참조하는 노드는 하나뿐이다.

1. 노드와 링크로 이루어져있다. 링크는 노드들을 연결시키다.
2. 1개의 루트노드를 가지고 있고, 트리의 마지막 레벨에 있는 노드를 단말노드라고한다.
   같은 레벨에 있는 노드들은 서로를 형제 노드라고한다.
3. 레벨이란 해당노드가 루트에서 떨어져있는 거리를 말한다.
4. 높이란 해당 트리의 최대 레벨을 말한다.
   

• ex : 루트 노드 : 2 , 노드 6의 레벨은 3, 트리의 높이는 4

DS - 이진 트리

• 한 노드에 자식 노드가 최대 2개
• 이때 자식노드를 각각 왼쪽 자식 노드, 오른쪽 자식 노드라고 말한다.
• 너비 우선 검색(BFS)
  • 너비 우선 탐색은 루트에서 시작하여 왼쪽부터 오른쪽으로 차례로 훑어나가는 검색법으로 O(n)시간이 걸린다.
  • 모든 노드를 확인하므로 메모리와 시간이 많이 소모된다.
• 깊이 우선 검색(DFS)
  • 루트에서 우선순위가 가장 높은 자식노드를 방문.
    추가 자식노드가 있다면 더 내려가다 더이상 방문할 노드가 없다면 이전상태로 복귀하고,
    그곳에서 가능한 방문하지 않은 다른 곳을 방문하는 방식.
• 종주법 ( 기준노드의 위치가 변하는걸 볼 수 있다)
  • 프리오더종주 : 기준노드 - 왼쪽노드 - 오른쪽노드 순 종주
  • 인오더종주 : 왼쪽노드 - 기준노드 - 오른쪽노드 순 종주
  • 포스트오더종주 : 왼쪽노드 - 오른쪽노드 - 기준노드 순 종주

DS - (맥스)힙 완전 이진트리의 모습을 가지며, 노드의 각 자식은 노드 자신의 값 이하여야한다.

• 빠르게 최대값을 추출할 시에 사용
• 힙의 삽입 : 삽입된 데이터를 먼저 배열의 마지막에 넣은후, 이 값을 부모노드의 키와 비교해서 더 큰값이면 부모 노드와 자리 변경
• 힙의 삭제 : 배열의 마지막 요소를 최상위 루트에 넣는다. 왼쪽, 오른쪽 자식과 비교하여 가장 큰 것과 루트를 스왑