반응형 BTS1 [CS 노트] : 이진 탐색 트리에 대해서 이진 탐색 트리 BST, 이진 탐색 트리 이진 탐색 트리는 정렬된 트리로 왼쪽 자식 노드는 부모 노드보다 작은 값을, 오른쪽 자식 노드는 부모 노드보다 큰 값을 가지고 있는 구조이다. 이진 탐색 트리의 시간 복잡도는 모두 O(logn)이고 worst case인 경우 즉, 한 쪽으로 치우친 트리가 되었을 경우에만 O(n)이 된다. 이진 탐색 트리로 조회를 할 경우엔? 조회하는 데이터를 루트 노드와 비교하고 작으면 왼쪽, 크면 오른쪽으로 보낸다. 이것을 반복해서 쭉 내리고 값이 같은 경우를 찾으면 된다. 이 과정이 O(logn)의 시간 복잡도가 걸리게 된다. 이진 트리는? 이진 트리는 모든 노드의 자식 노드의 수가 2 이하인 트리를 이진 트리라고 한다. 이진 탐색 트리의 worst case 이진 탐색 트리는.. 2022. 4. 6. 이전 1 다음 반응형