[자료구조] BST(Binary Search Tree)와 Binary Tree에 대해 설명해주세요

Reference
신입 개발자 기술면접 질문 정리 - 자료구조

💡 이진트리(Binary Tree)는 자식 노드가 최대 두 개인 노드들로 구성된 트리이고, 이진 탐색 트리(BST)는 이진 탐색과 연결 리스트를 결합한 자료구조입니다.

이진 탐색 트리(BST)는 이진 탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제가 가능하다는 장점이 있습니다. 이진 탐색 트리는 왼쪽 트리의 모든 값은 반드시 부모 노드보다 작아야 하고, 오른쪽 트리의 값은 부모 노드보다 커야 하는 특징이 있습니다.

이진 탐색 트리의 탐색 연산은 트리의 높이에 영향을 받아 높이가 h일 때 시간 복잡도는 O(h)이며,트리의 균형이 한쪽으로 치우쳐진 경우 worst case가 되고 O(n)의 시간 복잡도를 가집니다. 이런 worst case를 막기 위해 나온 기법이 RBT(Red-Black Tree)입니다.

(출처: https://en.wikipedia.org/wiki/Binary_search_tree)