[강의노트] 사전ADT를 이용한 선형탐색과 이진탐색 - 2

사전ADT를 이용한 선형탐색과 이진탐색 - 2

https://man-25-1.tistory.com/172

[강의노트] 사전ADT를 이용한 선형탐색과 이진탐색 - 1

위의 글에 이어지는 포스팅입니다.

 

이전에는 리스트형태를 순회하는 선형탐색과 이진탐색에 대해서 배웠는데 이번에 배울 것은 이진탐색트리이다.

 

이진탐색트리

이진탐색트리는 부모노드의 key값이 왼쪽 자식노드의 key 값보다는 크고 오른쪽 자식노드의 키값보다는 작거나 같다

이렇게 트리를 생성하게 되면, 트리를 중위순회로 순회했을때 키가 증가하는 순서로 방문할 수 있다.

이진탐색트리 - 탐색

수행과정을 아래그림을 통해 살펴보자. 

루트노드에서 시작해서, 더 작다면 왼쪽으로 크다면 오른쪽으로 가면 된다

 

수도코드를 통해 상세하게 알아보자.

재귀호출로 구현했고 base case는 외부노드에 도달했을때이다.

그것외에는 위의 설명과 같다. ( 쉽고 단순함 )

 

이진탐색트리 - 삽입

이번에는 삽입에 대해서 알아보자. 삽입과정은 조금 어려울 수 있다.

삽입 작업을 수행하기 위해서는 먼저 키 k를 탐색해야한다. 그 후 k가 트리에 존재하지 않는다면

외부노드에 도착하게 되고, 외부노드 w에 k를 삽입한 후 expandExternal(w) 메소드를 통해 w를 내부노드로 확장한다

 

그럼 만약 k가 트리에 존재한다면 어떻게 해야할까 ? 삽입을 하지않고 return 해버리면 된다.

다음의 수도코드를 보자

 

탐색을 진행하고 나온 노드가 내부노드라면 return , 그게 아니라면 외부노드에 삽입해서 내부노드로 확장 !

이렇게 기억하면 될 것 같다

 

이진탐색트리 - 삭제

삭제의 경우는 쉬운 case 와 어려운 case로 구분 된다

먼저 쉬운 케이스를 보면 지우고자 하는 노드의 자식노드 중 하나가 외부노드인 경우다.

이때는 reduceExternal(z) 를 사용하여 w와 z를 삭제하면 된다

' 

어려운 케이스는 삭제되어야 할 노드의 자식이 모두 내부노드일때이다. 그 경우에는 조금 까다로워진다.

  중위순회후계자라는 개념이 나오는데 아래의 그림을 통해 이해하는게 쉽다.

중위순회로 왼쪽 트리를 돌면 1번 노드 -> 2번 노드(w) -> y노드로 가게된다.

즉 y노드는 중위순회에서 w노드 다음 방문하게 되는 노드이다. y노드를 w노드를 삭제하고 w자리에 복사하는 이유는

중위순회에서 w노드 다음 순서기때문에 w노드가 삭제되고나서 w노드의 자리에 가장 알맞은 노드임

 

다시 정리해서 말하자면 이진탐색트리에서 중위순회 순서로 크기가 결정되기때문에, w노드가 지워진다음 w노드의 자리에는 중위순회 다음 순서인 y노드가 복사되는 것이다 

 

수도코드로 나타내면 다음과 같다. 구현하기 쉽지 않을 것 같다

이진탐색트리의 성능

findElement, insertItem, removeElement 모두 다 탐색 과정이 필요하므로, O(h)시간에 수행된다. ( 탐색시간은 높이에 비례하다는 것을 이미  잘 알고있다.)