📌Binary Search Tree
이진 검색 트리는 자식 노드가 최대 구 개인 노드들로 구성된 트리이다.
특징
| 이진 트리 종류 | 영어 표기 | 설명 |
|---|---|---|
| 정 이진 트리 | Full binary tree | 각 노드가 0개 혹은 2개의 자식 노드를 갖는다. |
| 포화 이진 트리 | Perfect binary tree | 정 이진 트리이면서 완전 이진 트리인 경우이다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리이다. |
| 완전 이진 트리 | Complete binary tree | 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 한다. |
이진 탐색 트리는 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있다.
프로젝트, 오류, CS 공부, 코테 등을 꾸준히 기록하는 저만의 기술 블로그입니다!