트리구조

|특징|선형구조|비선형구조
|--|--|--|
|구조|순차적으로 나열된 형태|데이터가 계층적 혹은 망으로 구성|
|용도|자료를 저장하고, 꺼내기|표현|
|종류|스택, 큐|트리, 그래프|

이진트리

• 각 노드가 최대 두 개의 자식을 가짐.

완전 이진트리

• 노드를 삽일 할 때 최하단 왼쪽 노드부터 차례대로 삽입한 이진 트리

• 완전 이진 트리를 배열로 표현
  

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

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

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

• 각 레벨(k)에 최대로 들어갈 수 있는 노드의 개수는 2^k

• 높이가 h인 노드가 꽉 차 있는 이진 트리의 모든 노드의 개수 = 2^h -1

• 이진 트리의 노드 개수가 N 일 때 최대높이는 log(n+1)-1

Heap

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

그래프

• 연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조