소프트웨어에 대한 모든 것

바이너리 서치 트리에(Binary Search Tree) 대해서 알아보겠습니다. 기본적인 내용은 다들 알고 계시지만 insert(), search(), delete()를 직접 구현한 분들은 많지 않을 것 같습니다. 학부 때 자료구조나 알고리즘 수업 시간에 구현을 했었을 수도 있지만 막상 당장 지금 구현하라고 하면 키보드에서 손이 멈칫 멈칫 할 것입니다. 바이너리 서치 트리(이하 BST) 구조 노드의 왼쪽 서브트리는 노드의 key 값 보다 작은 값을 갖는 노드로 구성 노드의 오른쪽 서브트리는 노드의 key 값 보다 큰 값을 갖는 노드로 구성 왼쪽과 오른쪽 서브트리도 각각 binary search tree로 구성되어야 함 BST 시간 복잡도 BST는 일반적으로 삽입, 탐색, 삭제는 O(logn)의 시간 복잡..