[CS 노트] : 이진 탐색 트리에 대해서

이진 탐색 트리

BST, 이진 탐색 트리

이진 탐색 트리는 정렬된 트리로 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지고 있는 구조이다. 이진 탐색 트리의 시간 복잡도는 모두 O(logn)이고 worst case인 경우 즉, 한 쪽으로 치우친 트리가 되었을 경우에만 O(n)이 된다.

 

이진 탐색 트리로 조회를 할 경우엔?

조회하는 데이터를 루트 노드와 비교하고 작으면 왼쪽, 크면 오른쪽으로 보낸다. 이것을 반복해서 쭉 내리고 값이 같은 경우를 찾으면 된다. 이 과정이 O(logn)의 시간 복잡도가 걸리게 된다.

 

이진 트리는?

이진 트리는 모든 노드의 자식 노드의 수가 2 이하인 트리를 이진 트리라고 한다.

 

이진 탐색 트리의 worst case

이진 탐색 트리는 균형이 많이 깨지게 되면 worst case가 되는데 이 경우 Linked list와 다를 게 없어진다. 때문에 시간 복잡도가 탐색 시 O(n)이 된다. 해결 방법은 자가 균형 이진 탐색 트리를 사용하면 된다. AVL 트리와 Red-black tree가 있다.

---

기출로 대비하는 개발자 전공면접 [CS 완전정복] 을 참고해서 공부하였습니다.