자료구조(17) - 이진 트리
- 이진트리
: 모든 노드가 정확하게 두 서브 트리를 가질 수 있는 트리
: 왼쪽 서브트리와 오른쪽 서브트리를 분명하게 구별할 수 있는 트리
: 이진트리에서 2개의 서브 트리가 모두 공백인 리프 노드들은 D, H, F, I이고
E, G는 공백이 아닌 서브 트리를 하나씩 가지고 있다.
: 노드 E는 공백 왼쪽 서브트리와 오른쪽 서브트리 G를 가지고 있으며,
노드 G는 왼쪽 서브트리와 오른쪽 공백 서브트리를 가지고 있다.
: 왼쪽 서브트리와 오른쪽 서브트리를 확실하게 구분한다고 하였다. 공백과 서브트리의 위치가 다른점은
다르기 때문에 둘은 구분지어 진다.
- 편향 이진트리
: 편향 이진트리란 모든 노드가 부모의 왼쪽 자식이기 때문에, 왼편으로 편향돼 있거나
모든 노드가 부모의 오른쪽 자식으로 되어 오른쪽으로 편향되어 있어야 한다.
- 포화 이진트리
: 포화 이진트리란 이진트리가 보유할 수 있는 최대의 노드를 가지고 있는 형태이다.
: 높이가 h인 이진트리에서 있을 수 있는 최대 노드수는 2^h-1 이다.
- 완전 이진트리
: 이진트리내에서 레벨 k에 있는 최대 노드의 갯수는 2^(k-1)이다. ( 단, k = 1, 2, 3, ... )
: 높이가 h인 포화 이진트리에 있는 노드의 수는 2^h-1이다.
: 높이가 h이고, 노드수가 n일때 n<=2^(h+1)-1 인 이진트리가 있다. 이 이진트릐의 노드를 레벨 순수에 따라
노드 번호를 붙일때 포화 이진트리의 번호 1~n까지의 위치와 번호가 일치한다면
이를 완전 이진트리라 한다.
: N개의 노드를 가진 완전 이진트리의 높이는 log(N+1)이다.
- 이진트리의 순차 표현
: 이진트리를 포화 이진트리 번호를 이용하면 순차표현, 즉 1차원 배열로 쉽게 표현할 수 있다.
: 포화이진트리의 번호는 배열의 인덱스가 되고, 표현하려는 이진트리의 해당 인덱스의 값이 저장된다.
: 완전 이진트리는 이처럼 되고,
: 편향 이진트리는 이처럼 인덱스에 배열이 된다.
: 0인덱스는 실제 사용하지 않고, 1인덱스는 루트노드값이 항상 위치한다.
: 공통된 배열로 인해 규칙이 생기는데 각 값의 인덱스는
: 노드 i 의 부모 : i/2 ( 조건, i > 1 )
: 노드 i의 왼쪽 자식 : 2 * i ( 조건 2 * i <= n )
: 노드 i의 오른쪽 자식 : 2 * i + 1 ( 조건 2 * i + 1 <= n )
: 루트노드 1 ( 조건 0< n )
: 이진트리의 순차표현의 장점
: 어떠한 이진트리의 표현에도 적용할 수 있다.
: 이진트리의 순차표현의 단점
: 공간을 표율적으로 사용하지 못할 수 있다.
- 이진트리의 연결표현
: 효율적인 공간 사용을 위해 항상 등장하는 포인터 방식이다.