[자료구조] 이진 탐색 트리의 구현(2) 삽입, 탐색

[자료구조] 이진 탐색 트리의 구현(2) 삽입과 탐색

이번 포스팅에서는 이진 탐색 트리의 삽입과 탐색이 어떻게 구현되는지 알아보겠다.

앞선 포스팅에서 말했듯이 이진 트리의 함수들을 사용하여 이진 탐색 트리의 함수를 만들어보겠다.

코드로써 구현을 하는 것도 중요하지만, 어떠한 식으로 삽입과 탐색이 이루어지는가를

이해하는 것도 상당히 중요하기 때문에, 그 부분에 중점을 두고 이어 나가보도록 하겠다.

point -> 삽입과 탐색의 과정에서 데이터는 key값으로 사용된다. 즉 중복이 있으면 안된다!!

01. 이진 탐색 트리의 삽입과정 (출처 : 윤성우의 열혈 자료구조)

(1) 이진 탐색 트리의 특성상 자신의 왼쪽은 무조건 자신보다 작을 것이며

자신의 오른쪽은 무조건 자신보다 클것이다.

(2) 자신(루트노드)보다 작다면 왼쪽으로 보내고, 크다면 오른쪽으로 보내면된다. 간단한다.

(3) 이런식으로 위치를 찾다가 더 이상 비교대상이 없다면( 끝에 이르렀다면 ) 그 자리에 삽입되게 된다.

02. 이진 탐색 트리의 삽입 구현

03. 이진 탐색 트리의 탐색 구현

이진 탐색 트리의 삽입과 탐색의 과정을 구현해보았다.

1. 가장 중요한 것은 key값을 통해 삽입과 탐색을 진행한다는 것! 즉 중복이 있으면 안된다.

2. 기존의 이진 트리를 구현하는 데 썼던 함수들을 활용하여 구현을 했다는 것!

3. 현재의 노드의 왼쪽은 자신보다 작은 값이 들어가고, 오른쪽은 자신보다 큰 값이 들어가는 특징을 활용한다.

4. 코드로 이해하는 것도 중요하지만, 전체적인 알고리즘을 이해하는 것도 중요하다.

다음 포스팅에서는 이진 탐색 트리의 구현 중 살짝 난이도가 있는 삭제의 과정을 구현해보겠다.