이진 탐색 트리 (Binary Search Tree, BST)

• 이진 탐색 트리는 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값이, 오른쪽 서브트리에는 큰 값이 저장되는 이진트리이다.
• 중위 순회를 통해 이진 탐색 트리의 모든 노드를 오름차순으로 정렬된 형태로 방문할 수 있다.
• 장점
  • 삽입 삭제가 유연하다.
  • 이진 탐색 트리의 구조 덕분에 검색 연산이 빠르다.
  • 노드를 추가하거나 삭제할 때 트리의 크기가 동적으로 조절된다.
• 단점
  • 트리가 불균형해지면, 최악의 경우 성능이 O(n)으로 떨어질 수 있다.
  • 이진 탐색 트리는 간단하고 효과적인 자료구조지만, 균형을 유지하지 않으면 성능이 저하될 수 있다. 따라서 균형을 유지하는 변형 트리(예: AVL 트리, 레드-블랙 트리 등)를 사용하여 성능을 보장할 수 있다.

 

후임자 (Successor)

• 정의: 특정 노드보다 값이 큰 노드들 중에서 가장 작은 값의 노드이다.
• 방법: 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 값의 노드를 찾는다.

 

선임자 (Predecessor)

• 정의: 특정 노드보다 값이 작은 노드들 중에서 가장 큰 값의 노드이다.
• 방법: 삭제할 노드의 왼쪽 서브 트리에서 가장 큰 값의 노드를 찾는다.

 

검색 (Search)

• 방법: 현재 노드의 값과 검색하려는 값을 비교하여, 값이 작으면 왼쪽 서브 트리로, 값이 크면 오른쪽 서브 트리로 이동한다. 이 과정을 반복하여 값을 찾거나, 서브 트리의 끝에 도달할 때까지 진행한다.
• 시간 복잡도: 최악의 경우 트리의 높이에 비례하므로 O(h)이다. 여기서 h는 트리의 높이이다.

 

삽입 (Insertion)

• 방법: 검색 과정과 유사하게 적절한 위치를 찾은 후, 새 노드를 추가한다. 새 노드는 인터널에 추가될 수 없고 항상 리프에 추가된다.
• 시간 복잡도: 검색과 같은 이유로 O(h)이다.

 

삭제 (Deletion)

• 방법:
  • 자녀가 없는 노드 삭제: 해당 노드를 단순히 제거한다.
  • 자녀가 1개인 노드 삭제: 삭제할 노드의 부모가 삭제할 노드의 자녀를 가리키도록 변경한다.
  • 자녀가 2개인 노드 삭제: 삭제할 노드의 오른쪽 서브 트리에서 가장 작은 노드(후임자) 또는 왼쪽 서브 트리에서 가장 큰 노드(선임자)로 삭제할 노드를 대체한다.
• 시간 복잡도: 삭제 후 트리 구조를 유지하는 작업도 필요하여, O(h)이다.