이진 트리(Binary Tree)

이진 트리(Binary Tree)

어떤 노드의 자식 노드의 수가 최대 2개를 넘지 않는 트리이다.

• 포화(Perfect) 이진트리: 모든 레벨이 꽉 찬 이진트리이다.
• 완전(Complete) 이진트리: 위에서 아래로, 왼쪽에서 오른쪽으로 차례대로 채워진 트리이다.
• 사향 이진트리: 한쪽으로 기울어진 트리로 탐색 시간은 O(N)이다.

 

1. 이진 탐색 트리(Binary Search Tree)

탐색 시간이 평균 O(logN)으로 효율적인 탐색이 가능하다.

• 각 노드의 자식이 2개 이하이다.
• 각 노드의 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 크다.
• 중복된 값의 노드가 없어야 한다.

2020.04.29 - [📝 Computer Science/✏ Algorithm] - [C] 이진 탐색 트리(BST)

[C] 이진 탐색 트리(BST)

 

2. 레드 블랙 트리

• 루트 노드의 색깔은 블랙이다.
• 모든 리프 노드들은 블랙 노드이다: 노드가 가진 두 개의 자식 포인터 중 NIL인 것이 있으면 노드를 하나 만들어 그것을 리프 노드라 부른다.
• 레드 노드의 자식은 블랙 노드이다.
• 루트 노드에서 임의의 리프 노드로 가는 경로에서 만나는 블랙 노드의 수는 모두 같다.

 

레드 블랙 트리

 

3. B 트리

디스크 접근 횟수가 적어 대량의 데이터가 저장된 디스크 환경에서 사용하기에 적합한 이진 트리이다.

• 하나의 노드에 많은 데이터 저장
• 각 노드의 자료는 정렬된 상태이고 자료의 수가 N개면 자식 노드의 수는 N+1개이다.
• 루트 노드는 적어도 2개 이상의 자식 노드를 가져야 하고 나머지 노드는 적어도 N/2개의 자료를 가져야 한다.
• 모든 리프 노드는 같은 깊이를 가진다.

 

B 트리

 

4. 힙(Heap)

배열에 기반한 완전 이진 트리로 반정렬 상태이고 중복된 값을 허용한다.

• 최대 힙(Max Heap): 루트 노드에 있는 값이 제일 크고 각 노드의 값이 해당 자식 노드의 값보다 크거나 같다.
• 최소 힙(Min Heap): 최대 힙과 반대이다.

 

힙