알고리즘 ) Binary Search Tree - 삭제

안녕하세요 :) Zedd입니다.

다들 Binary Search Tree아시죠? 모든 자료구조에는 탐색, 삽입, 삭제라는 연산이 있기 마련인데, 오늘 글에서는 “삭제”를 해보려고 합니다.

BST에서 그나마 까다로운 부분이기도 하죠.

다음글을 보실 때 참고하셔야 할거에요.

Binary Search Tree - 삭제

---

자..이러한 BST가 있어요. BST의 성질을 모두 만족하죠?

이제 우리가 원하는 노드를 “삭제” 해볼겁니다.

그럼 생각 할 수 있는 Case가 나오는데요... 어떤 경우가 있을까요?

1. 자식이 없는 노드를 지울 때

2. 자식이 하나만 있는 노드를 지울 때

3. 자식이 두개 다 있는 노드를 지울 때

이렇게 3가지 Case가 나오게 됩니다. BST는 완전이진트리가 아니고, 

이진트리기 때문에 자식을 하나만 가질 수 있죠?

그럼 하나하나 해볼게요.

1. 자식이 없는 노드를 지울 때.

19는 자식이 없는 리프노드에요. 

이 19를 지운다고 생각해봅시다.

그럼 어떻게 하시겠어요?!?!?!

? 그냥 똑 떼면 되는거 아냐..?

맞습니다..!!!

연결된 링크를 끊고

19라는 값을 가지고 있던 노드를 “지워주기만 하면” 됩니다.

넘나 쉬운것;;;

2. 자식이 하나만 있는 노드를 지울 때.

자식이 “하나”만 있다고 그랬죠? 

위 트리에서는 7을 골라볼게요. 

왼쪽 자식은 없고 오른쪽 자식만 있네요..!

자, 7을 지워봅시다.

Case 1처럼

댕-강

자..이러면 7의 자식이었던...9는요..? 

만약 9에게 자식이 더 있었다면

저 5와 7을 이어주던 링크를 지움으로써, 7만 지워지는 것이 아닌, 7의 자식이었던 애들도 다 지워지게 되는 것이죠.

이러면 될까요?!?!??!?!??!?

네 안됩니다.

그럼 어떻게 하면 될까요?

;;그냥 7만 쏙 빼고..9를 5의 자식으로 만들면 안돼?

맞습니다

5가 9를 가리키게 한 다음,

5와 7을 연결하던 링크를 지워주고,

7이라는 값을 가지던 노드를 지워줍니다.

위 그림은 곧

이걸 나타내는 거죠?

넘나 간단

자, 마지막인 Case 3입니다.

자식을 왼쪽, 오른쪽 모두 가지고 있을 때 입니다.

15가 거기에 해당이 되네요.

왼쪽 자식으로는 13을, 오른쪽 자식으로는 17을 가지고 있습니다.

15를 지우려면 어떻게 해야할까요?

음..15의 자식들한테 자식을 추가해줄게요..

뭔가 이래야 더 이해하기 쉬워서..

아무튼, 지금 15를 지워야 하죠? 

15는 왼쪽 자식, 오른쪽 자식을 둘 다 가지고 있습니다.

이럴 때는 도대체 어케해야하냐????

이럴 때 2가지 방법이 있습니다.

1. 오른쪽자식 중에서 가장 작은 값을 15자리로 옮긴다

2. 왼쪽 자식 중에서 가장 큰 값을 15자리로 옮긴다.

입니다.

보통 1번 방법을 많이 사용하는것 같습니다..

그럼 해볼까요?

 

- 오른쪽자식 중에서 가장 작은 값을 15자리로 옮긴다.

15의 오른쪽 자식중에서...가장 작은값은?

네 17이네요!

이제 이걸 15자리로 옮기라는 말이죠?

걍 반만 볼거니까 반만 가져왔어요.

암튼 15는 우리가 삭제 할 값이었죠??

그 자리에 오른쪽 자식중에서 가장 작은 값이었던 17을 넣어준 것입니다.

그럼 “원래 있던” 17을 지워줘야 겠죠?

어? 그럼 우리는 지금 15라는 값을 가진 노드를 지우는 과정중에서...

17을 지워야 하는 상황이 발생했습니다.

그럼 17의 자식을 보도록 하죠.

어 근데 17은 자식을 “하나”만 가지고 있네요?

우리 자식을 하나만 가지고 있을 때의 삭제는 어떻게 하면 되는지 Case 2에서 배웠는데 말이죠.

이렇게 하고,

댕-강

그럼 최종적으로

이러한 상황이 됩니다.

그럼 우리가 원하는 15가 사라졌죠!!!!!!!!!!!!!

그럼 여기서 눈치를 챌 수 있습니다.

1. 오른쪽자식 중에서 가장 작은 값을 15자리로 옮긴다

왜 가장 작은값인지 아시겠나요?

왜냐면.. BST이기 때문....그게 이유.....이유의 전부..

만약 오른쪽 자식중에서 가장 큰값을 가져오게 된다면...내 오른쪽에는 나보다 큰 값이 있어야 하는데 나보다 큰 값이 없어지는 것이니..

BST가 아니게 되버리죠. 그래서 오른쪽 자식중에서는 “가장 작은 값”을 가져와야 합니다.

왼쪽에서는 가장 큰 값을 가져와야 하는 이유도 위와 동일합니다.

삭제연산의 시간복잡도를 분석하자면, O(트리의 높이 = h)입니다.

왜냐? Case 3에서, 우리는 일단, 음..오른쪽 자식중에서 가장 작은 값을 가져오기로 했으면, 

그 오른쪽 자식중에서 가장 작은 값이 뭔지를!!!! 알아야겠죠? 먼저?

그럼 지금 내 위치에서 오른쪽 자식중에서 가장 작은 값을 가져올거니까 오른쪽으로 간다

=> 가장 작은 값을 찾을거니까 무조건 왼쪽 서브트리에 있을거임.

=> 가장 작은 값은 가장 끝 왼쪽에 존재.

그러니까 최악의 경우 트리의 높이까지 내려가야 하는 경우가 생길 수 있는 것이죠.

+) BST에서 삭제의 핵심은, 결국 자식이 없거나, 하나가 있는 상태로 만든다는 것입니다.

우리는 원래

딱 이 노드를 지울려고 했죠?

근데 오른쪽 자식중에서 가장 작은 17을 15자리에 “옮기고” 나니까

우리가 지울려던 노드(원래 15가 있던 노드)가 아닌, "다른 노드를 지우는 상황을 만든거에요”

그것도 자식이 없거나 하나만 있는 노드로요.

아시겠죠? 이게 핵심입니다.

오랜만에 자료구조 하니까 재밌네요 XD..

혹시 틀린점이나 궁금한점이 있으시다면 댓글이나 PC화면 오른쪽 하단의 채널서비스를 이용해서 질문해주세요 :)