2022-01-20 Binary Search Tree

 

- 트리 구조는 편리한 구조를 전시하는 것 외에 효율적인 탐색을 위해 사용하기도 함.

 

많은 트리의 모습 중, 가장 간단하고 많이 사용하는 이진 트리와 이진 탐색 트리를 공부할 거임.

 

 

이진 트리 종류영어 표기설명

정 이진 트리	Full binary tree	각 노드가 0 개 혹은 2 개의 자식 노드를 갖습니다.
포화 이진 트리	Perfect binary tree	정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
완전 이진 트리	Complete binary tree	마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.

 

이진 탐색 트리(Binary Search Tree)는

모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이 루트나 부모보다 큰 값을 가지는 특징이 있음.

 

7을 기준으로 왼쪽은 7보다 작은 서브트리(1,3,5) 오른쪽은 7보다 큰 서브트리(8, 10)

 

이진 탐색 트리는 균형 잡힌 트리가 아닐 때, 입력되는 값의 순서에 따라 한쪽으로 노드들이 몰리게 될 수 있음.

 

균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에

 

이 문제를 해결하기 위해 삽십과 삭제마다 트리의 구조를 재조정하하는 과정을 거치는 알고리즘을 추가할 수 있음.