보안 전공생의 공부

트리(3) | 히프 본문

공부/자료구조

트리(3) | 히프

수잉 2021. 1. 22. 00:27

출처 : book.naver.com/bookdb/book_detail.nhn?bid=10896666

 

C로 배우는 쉬운 자료구조

단계별 그림과 삽화로 이론을 다지고 C 언어로 구현해 보는 자료구조 입문서 자료를 구조화하는 다양한 방법을 단계별 그림과 삽화를 곁들여 쉽게 설명하고, 자료구조의 핵심 알고리즘을 C 프로

book.naver.com

목차

​

01 트리에 대해

02 이진트리에 대해

03 이진트리의 구현과 순회

04 이진탐색트리, AVL 트리

05 히프

​

05. 히프

◆ 히프 : 완전이진트리에 있는 노드 中 키값이 가장 크거나 가장 작은 노드 찾기 위해 만든 자료구조

​

▶ 최대히프 : 키값 가장 큰 노드 찾기 위한 완전이진트리

- {부모노드의 키값 >= 자식노드의 키값}

- 루트노드 : 키값이 가장 큼

보통 히프는 최대히프를 말함!

​

▶ 최소히프: 키값이 가장 작은 노드 찾기 위한 완전이진트리

- {부모노드의 키값 <= 자식노드의 키값}

- 루트노드: 키값 가장 작음

최대히프

 

최소히프

 

​

◇ 히프의 삽입연산

ⅰ) 완전이진트리조건 만족하도록 자리확장, 임시저장

- 노드 n개인 완전이진트리 → (n+1)번 노드 확장

ⅱ) 부모노드와 크기조건 만족하는 위치 찾기

- 현재위치에서 부모노드와 크기관계 확인

- {현재 부모노드의 키값 >= 삽입원소의 키값} 관계 성립 x → 자리 바꿈

​

◇ 히프의 삭제연산 - 루트노드의 원소만 삭제가능!

ⅰ) 루트노드 원소 삭제 → 노드수 (n-1)개로 줄어듬

ⅱ) 노드의 수가 (n-1)인 완전이진트리로 조정

- 마지막 노드(n번 노드) 삭제

- 삭제된 n번 노드에 있던 원소를 빈 루트노드에 임시저장

ⅲ) 자식노드와 크기조건 만족하는 위치 찾기

- 현재위치에서 자식노드와 크기관계 확인

- {임시저장 원소의 키값 >= 현재 자식노드의 키값} 관계 성립 X → 자리 바꿈

​

​

Q. 다음과 같은 키값을 가지는 원소들을 공백 히프에 차례대로 삽입하여 최대 히프를 생성한 다음, 삭제 연산을 한 번 수행한 후의 결과는?

<공백히프에 차례로 삽입해 최대히프 생성>

<삭제연산>

​

 

'공부 > 자료구조' 카테고리의 다른 글

정렬 (1)  (0) 2021.01.22
그래프 (2)  (0) 2021.01.22
그래프(1)  (0) 2021.01.22
트리(2) | 이진탐색트리, AVL트리  (0) 2021.01.22
트리 (1) | 트리, 이진트리  (0) 2021.01.22
'공부/자료구조' Related Articles more
Comments