응애맘마조

주의 : 해당 게시물에서 작성될 내용은 과제를 해결하기 위해 출처의 내용을 그대로 작성한 부분이 많으며 일절 광고나 수익 창출 목적으로 쓰인 것이 아님을 밝힙니다. 이진탐색트리는 이진 탐색과 연결리스트를 결합한 자료구조입니다. 이진 탐색의 효율과 자료 입력과 삭제가 가능합니다. 구성은 자식 노드가 2개로 구성된 트리로 볼 수 있습니다. 특징으로는 각 노드에 중복되지 않는 키가 있고 루트 노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드로 되어있고 반대로 오른쪽은 해당 노드보다 큰 키를 갖고 있습니다. 또한 좌우 서브트리도 모두 이진 탐색으로 되어있어야 합니다. 연산은 트리의 높이가 h일 때, O(h)의 복잡도를 가지게 됩니다. 탐색 과정은 좌측에 작은 키, 우측에 큰 키로 되어있는 것을 ..