이진 검색 트리 (BST, Binary Search Tree)

개념

이진 검색 트리는 각 노드가 최대 2개의 자식 노드를 가지는 이진 트리의 일종이다. 왼쪽 자식은 부모 노드보다 작거나 같으며, 오른쪽 자식은 부모 노드보다 크다는 규칙을 따른다. 이를 통해 정렬된 상태를 유지하여 효율저인 검색/삽입/삭제 연산이 가능하다.

특징

• 정렬된 구조 구조상 중위 순회를 할 경우 항상 오름차순으로 정렬된 값을 얻을 수 있다.
• 동적 데이터 관리 삽입/삭제/검색 연산이 트리의 높이에 비례하여 동작한다.
• 트리 구조의 유연성 삽입 순서에 따라 트리 모양이 달라질 수 있다.

장점

• 정렬 유지
• 동적 데이터 관리
• 효율적인 탐색 트리의 균형이 잘 유지될 경우 검색/삽입/삭제 연산 모두 평균적으로 O(log n)의 시간 복잡도를 가진다.
• 확장성 AVL 트리, 레드-블랙 트리 등 다양한 균형 트리로의 확장 및 개선이 가능하다.

단점

• 균형 문제 트리가 한쪽으로 편향되면 높이가 N까지 늘어나, 탐색/삽입/삭제 연산의 시간 복잡도가 최악의 경우 O(n)까지 떨어질 수 있다.
• 구현 복잡성 삭제 연산 등 일부 연산의 구현 난이도가 높을 수 있다.
• 더 많은 메모리 사용 각 노드 별로 포인터를 추가로 저장해야하므로, 배열 등의 선형 자료구조보다 메모리 사용량이 더 많을 수 있다.

BST 구현