자료구조 - 이진 트리(Binary Tree)란 (이진탐색트리와의 차이점) - 수정중

이진트리(Binary Tree)

- 노드의 최대 차수가 2인 트리

편향 이진트리

- 말 그대로 노드들이 한쪽으로 편향되어 생성된 이진트리를 말한다

*문제점 

1. 탐색속도 저하 : 이진탐색 트리일 경우 편향트리로 형성이 되면 E를 탐색하기 위해 모든 노드를 탐색해야 하므로

  연결리스트의 순차탐색과 탐색시간이 동일하다.

2. 공간 낭비 : 연결리스트로 구현할 경우는 문제가 없지만 인덱스로 구현할 경우 노드의 개수가 i 라면

 최대 2^i 의 공간을 필요로 한다.

포화 이진트리

- 높이가 h 일때 최대 노드의 수는 2^(h+1) -1 개이다 이때 이진트리에서 최대 노드의 수를 만족하는 트리를 포화 이진트리라 한다

 (ex - 높이가 3인경우 최대 노드 수 : 2^6 - 1 = 15)

완전 이진 트리

- 높이가 h인 트리에서 노드수가 n일때 레벨 순서번호가 1~n 까지 모두 일치하는 트리

(완전 이진 트리)

(완전 이진트리가 아닌 예)

이진트리의 표현

1. 순차 표현 

- 포화이진트리의 레벨 번호를 이용하여 인덱스상에 표현

- 0번은 편의상 사용하지 않는다.

완전 이진트리의 순차표현 - 공간을 효율적으로 사용(최적)

    편향 이진트리의 순차표현 - 많은 공간이 낭비됨

이진트리와 순차표현에서 인덱스와의 관계

순차표현의 장점

- 인덱스 규칙을 통해 원하는 노드를 찾기 쉽다

- 인덱스를 통해 원하는 노드를 빠르게 찾을 수 있다

- 구현이 간단하다

순차표현의 단점

- 완전이진트리의 경우 배열 공간을 최적으로 사용하지만 편향이진트리의 경우 많은 공간을 필요로함과 동시에 낭비한다.

2. 연결리스트 표현

- 각노드를 3개의 필드 left, data, right(왼쪽자식, 데이터, 오른쪽자식)로 구성한다

이진트리의 순회

이진트리와 이진탐색 트리의 차이점

(참조 - https://www.quora.com/What-is-the-difference-between-a-binary-tree-and-a-binary-search-tree)

- 이진트리란 노드의 최대차수가 2인 트리를 의미하며

   이진탐색트리는 이진트리에서 조건이 추가된 것을 의미한다

   

추가된 조건

1. 루트노드의 왼쪽 자식노드는 루트노드보다 크기가 작다

2. 루트노드의 오른쪽 자식노드는 루트노드보다 크기가 크다.