[C#] 이진 트리

이진 트리의 개념

 - 각 노드가 최대 두개의 자식 노드를 가지고 있는 트리

이진 트리 개념

이진 검색 트리 특징

 - 왼쪽을 타고 가면 현재 값보다 작다

 - 오른쪽을 타고 가면 현재 값보다 크다.

이진 검색 트리 특징

이진 검색 트리 문제

 - 그냥 무식하게 추가하게 되면, 한쪽으로 기울져서 균형이 깨진다. 트리 재배치를 통해 균형을 유지하는 것이 과제(AVL, Red-Black)

이진 검색 트리 문제

 

힙 트리 특징

 - 힙 트리 1법칙 : [부모 노드]가 가진 값은 항상 [자식 노드]가 가진 값보다 크다.

 - 힙 트리 2법칙 : 노드 개수를 알면, 트리 구조는 무조건 확정할 수 있다.

힙 트리 구조

 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있다.

 - 마지막 레벨에 노드가 있을 때는, 항상 왼쪽 부터 순서대로 채워야 한다.

힙 트리 구조(1법칙)

힙 트리 구조(제 2법칙) - 데이터 개수 5개인 경우의 힙 트리 구조

따라서 배열을 이용해서 힙 구조를 바로 표현할 수 있다. 예) int[] heap = new int[5];

 - i번 노드의 왼쪽 자식은 [(2 * i) + 1] 번

 - i번 노드의 오른쪽 자식은 [(2 * i) + 2] 번

 - i번 노드의 부모는 [(i - 1) / 2] 번

 

새로운 값 추가

 1) 힙 트리 1법칙을 통해서 우선 트리의 구조를 맞춰준다.

 2) 부모와 새로운 값(자식)를 비교하여 만약 새로운 값(자식)이 부모 노드보다 크면 자리를 바꿔준다.

 3) 이렇게 계속 비교하고 교체하다가 부모 노드가 새로운 값보다 커지면 새로운 값추가를 끝낸다.

 예) 힙트리 구조(1법칙)사진에서 14밑으로 28라는 노드를 추가합니다. 32는 부모 노드인 14보다 크기 때문에 28가 부모노드로 바뀌고 14가 자식노드로 바뀝니다. 또 28는 부모 노드인 22와 비교하였을 때 더 크기 때문에 또 바뀌게 됩니다. 마지막으로 최상위 노드보다는 작기때문에 여기서 교체를 멈추게 되고 새로운 값 추가가 끝나게 됩니다.

 

최대값 꺼내기

 1) 최대값(최상위 노드)을 먼저 제거한다. 

 2) 힙 트리 2법칙을 통해 제일 마지막에 위치한 데이터를 루트로 옮긴다.

 3) 힙 트리 1법칙을 통해 역으로 부모 노드와 제일 큰 자식노드를 비교하여 부모 노드값이 자식노드 값보다 작으면 자리를 바꿔준다.

 예) 힙 트리 구조(제 2법칙)사진을 예로 들면 A[0]를 제거하고 A[4]를 최상위 노드로 올립니다. 그리고 A[4]와 A[1]을 비교하여 A[4]가 A[1]보다 작으면 자리를 바꿔주게 됩니다.(반복)

 

 

---------------------------------------------------------------------------------------------------------------------------

참고 : [인프런] Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘