인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.

DELETE

Case 1:

Case 2:

Case 3:

삭제의 예

수도코드

BST

• 각종 연산의 시간복잡도 O(h)

• 그러나, 최악의 경우 트리의 높이 h=O(n)

• 균형잡힌(balanced) 트리

  • 레드-블랙 트리 등

  • 키의 삽입이나 삭제시 추가로 트리의 균형을 잡아줌으로써 높이를 O(logn)으로 유지