이진트리(BinaryTree), 힙트리(BinaryheapTree)

Rookiss님의 [c#과 유니티로 만드는 mmorpg 게임 개발 시리즈] part2 : 자료구조와 알고리즘 강의 내용을 정리했습니다.

Rookiss님의 [c++과 언리얼로 만드는 mmorpg 게임 개발 시리즈] part3: 자료구조와 알고리즘 강의 내용을 정리했습니다.

 

특징

- 자식 노드가 최대 2개인 트리

 

이진 트리 종류

이진 검색 트리

- 좌측으로 가면 루트보다 값이 작아지고, 우측으로 가면 루트보다 값이 커지는 형태로 노드를 배치 해서 검색에 용이하다.

- 노드가 좌우 균형 잡혀 있으면 효율적이지만, 한쪽에 기울어지면 효율성이 떨어진다. 트리 재배치를 통해 균형을 유지하는 것이 관건이다. (AVL, Red-black)

 

이진 힙 트리

- 부모 노드 값이 자식 노드보다 커야 한다. (자식 노드의 순서는 상관없다)

- 마지막 레벨에 노드가 있을 때는, 항상 왼쪽부터 순서대로 채워야 한다. => 이렇게 규칙을 지정 하면 노드의 개수를 알면 트리 구조를 알수 있다. => 이로 인해서 트리 정보를 선형자료구조에 넣어 사용할 수있다.

- 새로운 값 추가

마지막 노드 위치에 노드를 추가하고, 부모 노드와 크기를 비교해서 부모 노드가 추가된 노드 값보다 작으면 교체 된다. 같은 방식으로 부모 노드가 자식 노드보다 값이 작아지도록 반복 탐색한다.

- 최대값 꺼내기

루트 노드를 제거하고 마지막 노드를 루트 노드에 위치한다. 새롭게 지정된 루트 노드를 자식중 더 큰 값과 비교해서 루트 노드가 자식보다 작으면 교체 된다. 같은 방식으로 자식 노드와 비교,교체를 반복해서 힙트리 법칙을 유지한다.