이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree) 자료구조

이진 트리(Binary Tree) 자료구조

각 노드의 자식 노드(차수)의 개수가 2 이하로 구성된 트리

 

 

이진 트리의 종류

[ 편향 이진 트리 / 포화 이진 트리 / 완전 이진 트리 예시 ]

 

• 편향 이진 트리

노드들이 한쪽으로 편향돼 생성된 이진 트리

 

- 탐색 속도가 저하되고 공간이 많이 낭비된다.

 

• 포화 이진 트리

트리의 높이가 모두 일정하며 리프 노드가 꽉 찬 이진 트리

 

• 완전 이진 트리

마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리

 

 

이진 트리의 순차 표현

• 1차원 배열의 형태로 표현

[ 이진 트리 순차 표현 예시 ]

 

• 트리의 노드와 배열의 인덱스 사이 상관관계 (N = 노드 개수)
  • 루트 노드 : index = 1
  • 부모 노드 : index = index / 2 (제약 조건 : 현재 노드가 루트 노드가 아님)
  • 왼쪽 자식 노드 : index = index * 2 (제약 조건 : index * 2 <= N)
  • 오른쪽 자식 노드 : index = index * 2 + 1 (제약 조건 : index * 2 + 1 <= N)

 

 

---

 

이진 탐색 트리(Binary Search Tree) 자료구조

이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조

 

[ 이진 탐색 트리 예시 ]

 

• 특징

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

 

 

 

 

* <Do It! 알고리즘 코딩테스트 with C++편>, <이것이 취업을 위한 코딩 테스트다 with 파이썬>을 참고하였습니다.