자료구조 - 이진검색트리

Binary Search Tree

---

이진검색트리

• 이진트리 이면서 각 노드에 하나의 키를 저장하고, 루트 노드에 대해 왼쪽 서브트리에 있는 키들은 루트의 키 보다 작거나 같고, 오른쪽 서브트리에 있는 키들은 루트의 키 보다 크거나 같다.

• 트리의 높이는 평균 logn으로 연산에 대한 시간 복잡도도 평균 O(logn)이다.

 

이진검색트리의 연산

• Search: 키를 탐색한다. 시간복잡도는 O(h). h는 트리의 높이를 의미한다.

• Succesor: 노드 x의 Succesor란 x의 키보다 크면서 가장 작은키를 가진 노드를 탐색한다. 이때 모든 키들이 서로 다르다고 가정한다. 시간복잡도는 O(h).
• Predecessor: 노드 x의 Predecessor란 x의 키보다 작으면서 가장 큰 키를 가진 노드를 탐색한다. 이때 모든 키들이 서로 다르다고 가정한다. 시간복잡도는 O(h).
• Insert, Delete연산의 시간 복잡도는 O(h).
• 즉, 각종 연산의 시간복잡도는 O(h)이다. 

 

reference