IT's me

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

BFS 알고리즘 문제 - 효율적인 해킹(백준)

모든 목록을 순회하면서 해당하는 컴퓨터와 연관된 모든 컴퓨터를

찾아 큐에다 때려박는 방법 대신, 초기화 할때에 연관된 모든 컴퓨터를

해당 벡터에다가 저장하는 방법으로 풀어보았다.

나는 왜 이런 생각을 못했을까.. 하고 열심히 풀었는데 런타임 에러..

한 시간동안 고민끝에 찾아낸 원인은 큐를 접근하려고 만든 wp,rp변수를

초기화하지 않아서 이 변수들이 큐의 범위를 넘어가 버린 것...

문제를 실컷 다 풀어놓고 이런 사소한 것들 때문에 시간을 허비하니 정말 허탈하다..

BFS 알고리즘 - 효율적인 해킹(백준)

01. 초기화, 변수 선언

02. BFS 알고리즘

03. 메인

지금까지 BFS를 너무 단순하게 생각해왔던 것 같다.

상당히 쉬운 알고리즘으로 여겨왔는데, 조금만 어려워지니 정신못차리는..

꾸준히 하루에 한 문제씩이라도 풀어보면서 익숙해져야겠다..