이진트리 정리

이진트리

개념: 리프 노드를 제외한 모든 노드의 자식 노드가 최대 2개인 트리

종류

1) 편향 이징트리: 모든 노드의 자식 노드가 부모의 왼쪽이나 오른쪽에만 위치함

2) 포화 이진트리: 이진트리가 보유할 수 있는 치대 개수의 노드를 보유

3) 완전 이진트리: 포화 이진트리에서 루트노드부터 리프노드에 이르기까지 번호를 좌우와 상하의 순서로 매겼을 때, 번호 순서대로 2^(h+1) - 1개 이하의 노드가 존재하는 트리

4) 균형 이진트리: 모든 리프들의 번호 간격이 1인 트리

 

표현

포화 이진트리의 번호를 이용하면 1차원 배열을 이용해 쉽게 표현이 가능하지만 편향 이진트리에서는 메모리 낭비가 심하므로 Linked List와 같은 연결 방식으로 주로 표현함