목록완전이진트리 (1)

KKanging

[자료구조] 완전 이진트리란?

완전 이진트리란? 완전 이진트리 자식 노드가 왼쪽부터 순서적으로 채워진 이진트리 높이가 균형을 유지 완전 이진트리 표현 배열로 표현한다. 이유는 완전이진트리의 속성인 균형이 유지되기 때문 완전 이진트리 자료구조 0부터 시작해도 되지만 노드의 인덱싱의 조금 더 가시성이 좋기 때문에 1부터 시작해도 된다. 1부터 시작할 경우 배열 인덱스 i의 부모노드: i/2의 바닥함수(내림) 노드 배열 인덱스 i의 왼쪽 자식: 2i의 노드 배열 인덱스 i의 오른쪽 자식: 2i + 1의 노드 완전 이진트리의 레벨 i에서 노드의 수는 2^(i-1)개 완전이진트리의 높이가 h일 경우 최대 노드의 수는 2^h -1개 완전 이진트리에서 노드의 수 n일 경우 트리의 높이는 O(logn) 완전이진트리를 사용한 알고리즘의 수행시간은 트..
cs/자료구조 2023. 7. 14. 12:00
이전 Prev 1 Next 다음