[Data Structure] 이진탐색트리

이진탐색트리란

이진탐색과 연결리스트를 결합한 자료구조이다.

이진탐색의 효율적인 탐색 능력과 삽입, 삭제에 효과적이다.

• 이진탐색 : 탐색에 소요되는 시간 복잡도는 O(log N), 삽입/삭제 불가능
• 연결리스트 : 삽입, 삭제의 시간 복잡도는 O(1), 탐색하는 시간 복잡도 O(N)

즉 이진탐색과 연결리스트의 장점만을 살려 고안해낸 자료구조가 이진탐색트리이다.

 

이진탐색트리의 특징

• 각 노드의 자식은 2개 이하
• 각 노드의 왼쪽 자식은 부모보다 작고 오른쪽 자식은 부모보다 크다.
• 중복되는 노드가 없어야 한다.
• 중위순회 방식

 

시간복잡도

• 균등 트리일 때 : O(logN)
• 편향 트리일 때 : O(N)

편향 트리일 때 시간복잡도가 O(N)이므로 편향 트리가 되지 않도록 개선할 필요가 있다.