이진탐색트리

TIL 카테고리의 글은 그날 배운 것을 정리하는 목적으로 포스팅합니다. 내용이 잘못되었다면 댓글로 피드백 부탁드립니다.

BST

모든 노드에 대해서 왼쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 작고 오른쪽 서브트리에 있는 데이터는 모두 현재 노드의 값보다 큼.

• 값이 중복되는 것은 제외함
• 이진 탐색 트리 데이터의 표현
  • 각 노드는 key, value의 쌍으로 이루어짐.

장점

• 데이터 원소의 추가, 삭제가 용이함.
• 요소 검색이 빠름(이진탐색)

단점

• 공간 요소가 큼

이진탐색(이진 검색 알고리즘)

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다.

이진 탐색 트리는 요소 검색에 매우 효율적인데 이 때 이진탐색을 사용함.

이진탐색의 시간 복잡도는 O(logn)이며, 항상 시간복잡도가 O(logn)은 아님.

그럼 언제 시간복잡도가 O(logn)이 아닐까?

바로 이진 탐색 트리의 높이의 균형이 유지되어있지 않은 경우.

위와 같이 생긴 이진 탐색 트리의 경우는 이진 탐색을 해도 효율적이지 않음. O(logn)이 아님.

이진 탐색은 높이가 비슷하고 왼쪽 오른쪽의 균형이 맞을 때 효율적임.

보다 성능이 좋은 이진 탐색 트리

높이의 균형을 유지하는 이진 탐색 트리

• AVL Tree
• Red-black Tree

위 트리들은 좋은 탐색 성능을 갖추기 위한 구조의 트리이지만 그만큼 삽입과 삭제 연산이 복잡하다.