자료구조 08 이진 탐색 트리 | JS

이미지 출처

이진 탐색 트리 | Binary Search Tree | BST

이진 탐색

• 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘
• 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식
• 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

이진 트리

• 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조

이진 탐색 트리

이진 탐색 트리는 다음과 같은 속성이 있는 이진 트리 자료 구조임

• 각 노드에 값이 있다.
• 값들은 전순서가 있다.
• 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
• 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
• 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.

이진 탐색 트리에서의 검색

• 이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다.
• 검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다.
• 불일치하고 검색하고자 하는 값이 루트노드의 값보다 작을 경우 왼쪽 서브트리에서 재귀적으로 검색한다.
• 불일치하고 검색하고자 하는 값이 루트노드의 값과 같거나 큰 경우 오른쪽 서브트리에서 재귀적으로 검색한다.

Github | javascript-algorithms | trekhleb

완전 이진 트리

이미지 출처

• 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있음
• 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있음
• 이진 탐색 트리는 완전 이진 트리가 아닐 수 있음

📚 참고

Github | tech-interview-for-developer
Github | Interview_Question_for_Beginner
Github | javascript-algorithms | trekhleb

Photo by Alain Pham on Unsplash