비선형구조 : 트리

선형 구조 : 자료를 순차적으로 나열한 형태

• 배열
• 연결 리스트
• 스택/큐

비선형 구조 : 하나의 자료 뒤에 다수의 자료가 올 수 있는 형태

• 트리
• 그래프

트리 구성 요소

나무위키

(너무.. 깔끔한 그림;)

트리는 그래프와 비슷한 구성 요소를 갖는데, 그래프의 정점 → 트리의 노드 이다.

또한, 그래프와 살짝 비교될만한게, 트리는 계층구조를 가지고 있다. 그래서 부모노드, 자식노드 이런 용어가 생긴 것.

레벨 vs 높이 vs 깊이

아파트로 비교했을 때,

레벨 : 각 층 여기는 0층, 여기는 3층 이런식으로 (루트 노드부터 노드까지 연결된 간선 수의 합)

높이 : 이 아파트의 최고 높이 (가장 긴 루트 경로의 길이)

깊이 : 해당 층수까지의 높이 = 레벨 (루트 경로의 길이)

 

Heap Tree (우선순위 큐)

• 힙트리는 기본적으로 이진 트리로 구성되어 있다.(자식노드가 최대 2개)
• 힙트리의 부모는 무조건 자식노드보다 크다.(최대힙), 힙트리의 부모는 무조건 자식노드보다 작다.(최소힙)
• 힙트리는 무조건 왼쪽 노드부터 차례대로 채워넣어야 한다.
  = 노드 개수에 따라 트리모양이 무조건 정해진다.
  = 따라서 힙트리는 연결리스트 모양이 아닌 배열을 이용해서도 표현할 수 있다.
  i번째 노드 기준 
  왼쪽 자식 : (2*i)+1번, 오른쪽 자식 : (2*i)+2번, 부모 : (i-1)/2

위키

우선순위 큐 : 큐에 데이터를 집어넣은 대로 뽑아내는 것이 아닌, 최대값 순서 혹은 최소값 순서대로 찾는 알고리즘

→ 힙 트리를 이용해서 데이터를 저장하면 쉽게 찾을 수 있다.

 

priority_queue<int> pq;

이 코드를 사용해서 쉽게 우선순위 큐를 만들고 사용할 수 있다.(vector와 같은 container STL!)

queue와 사용법이 비슷하지만, 위에서 설명했듯이 큐와의 다른점은 정렬을 해준다는 것!

정렬을 해주기때문에, Predicate 부분에 less<>또는 greater<>을 넣어서 내림차순 또는 오름차순으로 정렬할지 정해줘야 한다.