swift ) 이진탐색트리(BST, Binary Search Tree) 정리 및 구현해보기

 

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

'트리' 자료구조를 기반으로 한, 이진 탐색이 가능하도록 구현된 자료구조

기본적인 트리 구조에 아래와 같은 특징들이 추가된다.

 

- 각 노드의 자식의 개수는 왼쪽에 1개 이하, 오른쪽에 1개 이하이다. (왼쪽/오른쪽에 자식이 있거나 / 없거나)

- 왼쪽 자식노드에는 노드보다 작은 값이 들어갈 수 있다.

- 오른쪽 자식노드에는 노드보다 큰 값이 들어갈 수 있다.

 

 

ㅋㅋ 세상에서 제일 못생긴 이진탐색트리..

아무튼 위처럼 생겼다.

 

 

이진탐색트리를 구현할 때는 연결리스트를 이용할 건데

연결리스트의 노드 만들 때 data, nextNode(포인터)의 항목을 갖는 클래스를 만들었었다.

마찬가지로 노드 클래스를 먼저 만들어주고, BST 클래스도 만들어주면 됨.

 

 

뼈대는 구현했으니,

실제로 사용할 수 있는 메서드들을 구현해보려고 한다.

이진탐색트리의 검색, 삽입, 삭제(...)를 구현해볼 것이다.

물론 완벽한 코드는 아닐 것이기 때문에 그 부분은 감안하고 보셔야..

 

 

---

1. 검색

배열이 아닌 연결 리스트 형태의 자료구조이기 때문에

루트노드에서부터 시작해서 하나씩 검색하게 된다.

다만, 리스트에서의 검색은 O(N)만큼의 시간이 걸렸다면

이진탐색트리에서의 검색은 무려 '이진 탐색'이 가능하기 때문에 O(logN)의 시간이 걸리게 된다.

검색할 값이 현재 노드보다 크냐? 작냐?에 따라 다음 노드로의 방향성이 정해지기 때문에 나머지 절반만큼은 무시할 수 있게 되기 때문이다.

위의 트리 그림에서 예를 들자면, '18'이라는 값을 검색하고자 할 때

루트노드의 오른쪽 자손노드들이 싹 무시되고,

다음 노드인 '20' 노드에서의 오른쪽 자손노드들이 싹 무시됨!

스위프트로 메서드를 구현해보면 아래와 같다.

 

 

루트노드부터 시작해서, 노드가 nil이 아닐 때까지 검색을 해보고,

검색하려는 값이 존재한다면 'data' existed in BST 를 출력하고 끝

현재노드가 nil이 될 때까지 검색이 되지 않았다면, BST 내에 해당 값이 존재하지 않는 것이므로 No 'data' in BST를 출력하고 끝

메서드의 리턴값을 bool, int, string 등등 다양하게 줘서 사용할 수 있을 것이다.

 

 

 

 

 

---

2. 삽입 

 

이진탐색트리의 장점!!!

검색+1단계만 더 있으면 되기 때문에 O(logN)의 시간복잡도를 갖는다.

이러한 장점 때문에 이진탐색트리는 데이터를 많이 변경하는 경우에 사용하기 좋다.

스위프트로 구현해보면 아래와 같다.

 

이것도 재귀를 사용하면 더 깔끔할 것 같긴한데.... 

 

 

 

 

---

3. 삭제

이진탐색트리에서 삭제는

다양한 경우에 대해 각각 고려할 점이 있어서 복잡함.........

 

1) 삭제할 노드에 자식노드가 없는 경우

- 그냥 삭제 가능

2) 삭제할 노드에 자식이 하나인 경우

- 노드를 삭제하고, 자식노드를 삭제된 노드가 있던 위치에 삽입

3-1) 삭제할 노드에 자식이 둘인 경우

- 삭제된 노드를 후속자(successor)노드로 대체해야 함

3-2) 자식이 둘인 경우 && 후속자 노드에 오른쪽 자식이 있는 경우

- 삭제된 노드를 후속자 노드로 대체한 후,

후속자 노드의 오른쪽 자식을 후속자 노드가 있던 자리로 이동 (후속자 노드의 부모노드의 왼쪽 자식)

*****

후속자 노드 : 삭제된 노드보다 큰 값 중 최소값을 갖는 노드

-> 삭제된 노드의 오른쪽 자식노드부터 계속해서 왼쪽자식노드로 내려갔을 때의 바닥노드!!

*****

 

우와 진짜 너무 힘들었음...

위의 상황들을 모두 고려하여 메서드를 만들었는데 코드가 이쁘진 않지만 모든 상황에서 잘 작동하는 듯 하다.

당연히 보완해야할 점은 있겠지만 지금은 ㄴㄴ.....

 

 

 

 

 

이진탐색트리 스위프트로 구현해보기..... 완료............................