[Algorithm] 직접 구현해 본 트리, 그리고 힙
Algorithm·2025. 11. 19.
이진 트리 / 완전 이진 트리이진트리란 노드에 최대 2개의 자식 노드만 올 수 있는 트리 자료구조이다.이때, 해당 레벨의 왼쪽부터 차례차례 원소가 쌓이게 되면 완전 이진트리라고 한다.예를 들면 좌측은 완전 이진 트리이고, 오른쪽은 완전 이진트리가 아니다. 이런 트리는 배열로 표현할 수 있는데, 위 예시대로 표현 하자면 다음과 같다.-> [null, 8, 6, 3, 4, 2, 5, 7]이때 0번째 인덱스는 편의상 비워두고 1번째 인덱스부터 사용한다. 이제 그려면 규칙성이 하나 보이는데, 현재 인덱스를 기준으로 자식 인덱스를 찾을 수 있는 공식이 보이고, 자식 인덱스 기준 본인의 부모 인덱스를 찾을 수 있는 공식도 보인다.자식 부모노드 구하는 공식* 부모의 왼쪽 자식 노드 구하기 : 현재 Index * 2..