2021.05.16
[C++] 이진 탐색 트리(Binary Search Tree)
이진 탐색 트리(Binary Search Tree) 이진 탐색 트리(Binary Search Tree) 널리 사용되는 형태의 이진 트리(Binary Tree) BST의 속성 왼쪽 노드 ≤ 부모 노드 ≤ 오른쪽 노드 의 관계를 가짐. 부모 노드의 값 ≥ 왼쪽 자식 노드의 값 부모 노드의 값 ≤ 오른쪽 자식 노드의 값 부모 노드보다 작거나 같은 모든 원소는 항상 왼쪽에 이고, 부모 노드보다 크거나 같은 원소는 항상 오른쪽에 있게 됨. 원소 검색을 위해 루트 노드부터 차례대로 값을 비교하는 경우, 각 단계마다 검색 범위가 절반으로 줄어듦. BST가 마지막 레벨을 제외한 모든 노드에 2개의 자식 노드가 있을 경우 트리의 높이 : log₂N N : 원소의 개수 BST의 검색 및 삽입 동작의 시간 복잡도 : O(l..
