패스트캠퍼스 챌린지 10일차

[강의] 다음은 패스트 캠퍼스 알고리즘 / 기술면접 완전 정복 올인원 패키지를 통해 학습 및 정리한 내용입니다.

 

2월 2일 오늘의 강의

 

이진 탐색 트리의 탐색 기능 구현

지난번 이진 탐색과 연결 리스트의 기능을 구현하면서 이진 탐색의, O(log N)의 탐색 속도와 연결 리스트의, O(1)의 데이터 삽입 및 삭제의 장점을 결합시켰었다. 오늘은 실제 탐색 기능 구현을 위해 코드를 작성해보는 시간을 가졌다.

 

코드는 기존 클래스에서 메소드로 구현하였다. 해당 메소드를 보면 인자로부터 value 값을 전달받고 current node를 head로 초기화를 해준 뒤 while문을 통해 순회하면서 현재의 노드의 value 값이 있는지 확인한다. 만약 있다면 True를 반환해주고 없다면 False를 반환시켜준다.

 

BST 객체를 생성 및 노드를 추가하였고, BST 내에 없는 값 -1을 탐색해보면 False 값을 확인해볼 수 있다.

 

이진 탐색 트리 삭제

지금까지 이진 탐색 트리 구조를 만들고 데이터 삽입 및 검색 기능까지 구현해보았다. 이어서 삭제 기능을 구현해볼건데 구현 전에 어떠한 패턴이 있는지 살펴보면서 구현해야할 기능을 정리해보자.

 

 

출처 : 잔재미 코딩

 

Child Node가 없는 Leaf Node이다. Leaf Node를 삭제하는 방법은 삭제한 Node의 Parent Node가 삭제할 Node를 가리키지 않게 한다.

 

 

출처 : 잔재미 코딩

 

Child Node가 1개인 Node이다. 해당 노드를 삭제하는 방법은 삭제할 Node의 Parent Node가 Child Node를 가리킨다.

 

 

출처 : 잔재미 코딩

 

Child Node가 2개인 Node이다. 해당 노드를 삭제하는 방법은 두가지가 있는데 첫 번째는 삭제할 Node의 오른쪽 자식의 가장 작은 값을, 삭제할 Node의 Parent Node가 가리키도록 한다. 두 번째는 왼쪽 자식의 가장 큰 값을, 삭제할 Node의 Parent Node가 가리키도록 한다.

 

여기에서 첫 번째 방법을 적용 시키려면 다음과 같이 문제를 잘게 쪼개어 생각해볼 수 있다.

 

헷갈리기 때문에 천천히 생각해보자

 

다음은 이러한 접근 방식을 통해 기능을 구현해볼 예정이다.

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.