1-1. 트리(tree)
기본적으로 트리(tree)는 배열/링크드리스트와 달리 비선형 자료구조이다.
계층형 자료구조라고도 하며, 계층구조를 구현하기 위한 기초개념들이 있다.
-
노드
트리의 각 계층 및 구조를 이루는(배치되어있는) 데이터/원소들
▶부모노드에서자식노드들이 하위 계층구조를 이룬다(서로 연결).
▶ 같은부모노드를 가지는 자식노드들은 서로형제노드가 된다.
▶자식노드가 없는 노드를리프노드라 한다. -
간선
각 데이터/원소들간 연관관계를 나타내주는 로직
데이터/원소간 연결점이 있으면 간선으로 데이터들을 이어준다. -
레벨
루트노드(최상위 노드, 시작점)를 1로 하고, 하위 계층마다 1씩 증가.
각 노드들의 계층위치와 전체적인 트리의 계층구조를 알 수 있다. -
차수
각 노드들이 가지는 자식 노드들의 수 -
포레스트
트리들의 집합
1-2. 힙(heap)
완전이진트리의 구조를 갖고 있으며, queue를 구현하기 위한 자료구조이다.
배열로 구현하고, 구현의 편의성을 위해 루트노드의 인덱스는 1부터 시작한다.
완전이진트리의 구조이기 때문에, 부모노드와 자식노드간 인덱스 규칙이 있다.
▶ 부모노드의 인덱스 * 2 = 오른쪽 자식노드의 인덱스
▶ 부모노드의 인덱스 * 2 + 1 = 왼쪽 자식노드의 인덱스
max heap / min heap으로 여러 값들 중 최대/최소값을 빨리 찾을 수 있다.
-
max heap
부모노드의 값이 자식노드의 값보다 큰 heap -
min heap
부모노드의 값이 자식노드의 값보다 작은 heap
3. 힙의 노드 삽입
힙의 새 노드 삽입시 일단 가장 마지막 노드에 삽입된다.
그 후 부모노드와 비교하면서 힙의 규칙을 만족할때까지 교환과정을 반복한다.
4. 참조링크
https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
https://devowen.com/213
4. remind
코드에 대한 이해가 우선이다. Not sugar syntax But sugar logic!
