개발 공부 - [검색트리] 이진검색트리 - 3

 * DELETE

- Case 1 : 자식 노드가 없는 경우

: 그냥 삭제 한다. (씸플!)

- Case 2 : 자식 노드가 1개인 경우

: 자신의 자식노드를 원래 자신의 위치로 이동 (내 위치로 자식을 이동 시킨다)

- Case 3 : 자식 노드가 2개인 경우

: Case 1이나 Case 2는 트리 구조 유지가 간단했으나, 복잡해진다.

-> R 자식 L 자식 둘 다 부모 없는 노드가 되기 때문에,

부모 노드 데이터만 지우고 다른 노드에 저장된 데이터만 복사해 온다.

[다른 노드]는 지우고자 하는 부모 노드에 근접한 값을 가져온다.

Pred나 successor 중 하나 가져와서 하면 됨.

그리고 successor 노드를 이동 시켜 준 뒤에 다시 Case 1이나 Case 2 방식으로 이동 시킨다.

시간 복잡도는 O(h)

BST

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

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

- 균형잡힌 (balanced) 트리

    - 레드 - 블랙 트리 등

    - 키의 삽입이나 삭제시 추가로 트리의 균형을 잡아잠우르써 높이를 O(log2n)으로 유지

레드-블랙 트리 참고: https://itstory.tk/entry/%EB%A0%88%EB%93%9C%EB%B8%94%EB%9E%99-%ED%8A%B8%EB%A6%ACRed-black-tree