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

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

 

2월 1일 오늘의 강의

 

이진 탐색 트리란?

이진 탐색 트리는 이진 탐색과 연결 리스트를 결합한 자료구조로 효율적으로 탐색 및 비교, 자료를 입력 및 삭제할 수 있다. 기존에 이진 탐색은 시간 복잡도가 O(log n)로 빠른 탐색 기능을 갖고 있지만 데이터 삽입 및 삭제가 불가능한 단점이 있었다. 반면에 연결 리스트의 경우 삽입 및 삭제가 O(1)이지만 탐색하는 시간 복잡도가 O(N)으로 효율이 떨어지는데 이러한 장, 단점을 보완하기 위해 이진 탐색과 연결 리스트를 결합시키게 된다.

 

 

 

특징으로는 각 노드의 자식이 2개 이하로 구성되어야하고 데이터의 값이 비교하는 노드보다 작을 경우 왼쪽 자식으로, 클 경우 오른쪽 자식으로 구성된다. 이때 중복된 노드가 없어야 하는데, 이진 탐색 트리는 검색 목적 자료구조로 중복이 많을 경우 검색 속도가 현저히 느려지기 때문이다. 만약 중복된 노드가 있을 경우 카운트 값을 가지게 해서 처리하는 방법도 있다.

 

이진 탐색 트리 구현 실습

링크드 리스트로 이진 탐색 트리를 구현해보았다. 이를 위해 먼저 노드 클래스를 정의하여 데이터, 좌우측 주소 값으로 멤버 변수를 선언해준다. 그리고 이진 탐색 트리 조건에 맞춰 데이터를 넣어주기 위해 새로운 클래스를 정의해서 데이터가 입력되면 값의 크기에 따라 탐색 비교로 현재 노드보다 데이터가 작을 경우 좌측, 클 경우 우측으로 보내주어 노드를 연결해준다.

 

 

 

코드 내부를 더 살펴보면 현재 노드에서 값이 작을 경우 좌측으로 보내주게 되는데, 좌측에 노드가 있다면 다시 좌측의 노드와 값을 비교해서 클 경우 우측, 작을 경우 좌측에 넘겨주며 새로운 노드가 생성될 때까지 비교 탐색을 이어간다.

 

https://bit.ly/37BpXiC

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

 

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