Java 자료구조 - 트리

배열이나 연결리스트 : 데이터를 일렬로 저장하기 때문에 탐색 연산이 순차적으로 수행. 배열은 미리 정렬(Sort)을 해놓으면 이진탐색을 통해 효율적인 탐색이 가능하지만, 삽입이나 삭제 후에도 정렬 상태를 유지해야함. 삽입이나 삭제하는데 O(N) 시간 소요.

서브트리가 중요.

트리의 최대 레벨

일반트리

N개의 노드가 있는 최대 차수가 k인 트리

null 레퍼런스 수 = Nk – (N-1) = N(k-1) + 1

Nk = 총 레퍼런스의 수 (N-1) = 트리에서 부모-자식을 연결하는 레퍼런스 수

• k가 클수록 메모리의 낭비가 심해지는 것은 물론 트리를 탐색하는 과정에서 null 레퍼런스를 확인해야 하므로 시간적으로도 매우 비효율적

학부과정에서의 교과수준에서는 자식 수가 2 초과인 일반트리는 거론하지 않음.

이진트리

이진트리에 대한 개념은 명확하게 알고있자.

포화 이진트리

각 내부노드 모두 2개의 자식노드를 가지는 트리 n층 포화이진트리의 노드 개수는 (2^n-1)개

완전 이진트리 - 힙트리

마지막 레벨을 제외한 각 레벨이 노드들로 꽉 차있고, 마지막 레벨에는 노드들이 왼쪽부터 빠짐없이 채워진 트리 포화 이진트리는 완전 이진트리에 포함된다. (학교 시험 출제)

편향 이진트리

편향(Skewed)이진트리를 배열에 저장하는 경우, 트리의 높이가 커질 수록 메모리 낭비가 심화됨