최소 힙 트리란?
완전이진트리로 구현된 자료구조
부모 노드가 자식 노드보다 작은 값을 가지는 트리
완전이진트리란?
완전이진트리란?
각 노드가 최대 2개의 자식 노드를 갖는 트리 구조
- 마지막 레벨을 제외한 모든 노드는 채워져 있어야 한다.
- 마지막 레벨 노드는 왼쪽 자식 노드만 갖고 있거나, 왼쪽 오른쪽 자식 노드를 모두 가지고 있어야 한다.
- 노드를 삽입할 때, 최하단의 왼쪽 자식 노드로 삽입해야 한다.
왼쪽에 보이는 이진 트리는 마지막 레벨을 제외한 모든 노드가 채워져 있고, 마지막 레벨 노드는 왼쪽 자식만 갖고 있거나 왼쪽, 오른쪽 자식 노드를 모두 갖고 있기 때문에 완전이진트리이다.
오른쪽에 보이는 이진 트리는 3의 자식 노드가 오른쪽 자식 노드밖에 없기 때문에 완전이진트리가 아니다.
삽입 과정
[8, 10, 3, 14, 6, 7, 1, 4, 13] 순서로 삽입해보자.
8 삽입
트리에 아무 노드도 없기 때문에 8이 삽입된다.
10 삽입
왼쪽 자식 노드가 채워져있지 않기 때문에 8의 왼쪽 자식 노드에 10을 넣어준다.
3 삽입
8의 오른쪽 자식 노드가 비워져 있기 때문에 8의 오른쪽 자식 노드로 3을 넣어준다.
3보다 8이 크기 때문에 둘의 위치를 바꿔준다. (3 <-> 8)
14 삽입
왼쪽부터 채워야 하기 때문에 10의 왼쪽 자식 노드에 14를 넣어준다.
6 삽입
10의 오른쪽 자식 노드가 비어있기 때문에 10의 오른쪽 자식 노드로 6을 넣어준다.
10보다 6이 더 작기 때문의 둘의 위치를 바꿔준다.
7 삽입
8의 왼쪽 자식 노드가 비어있기 때문의 8의 왼쪽 자식 노드로 7을 넣어준다.
7이 8보다 작기 때문에 둘의 위치를 바꿔준다.
1 삽입
7의 오른쪽 자식 노드가 비어있기 때문에 7의 오른쪽 자식 노드로 1을 넣어준다.
1이 7보다 더 작기 때문에 둘의 위치를 바꿔준다.
루트 노드인 3보다 1이 더 작기 때문에 둘의 위치를 바꿔준다.
13 삽입
레벨 2가 모두 채워져있기 때문에 14의 왼쪽 자식 노드로 넣어준다.
14보다 13이 더 작기 때문에 둘의 위치를 바꿔준다.
'CS > 자료구조' 카테고리의 다른 글
| [자료구조] 이진 탐색 트리 (0) | 2025.01.16 |
|---|
