검색 트리

이진트리 (BST)

각 노드는 하나씩의 키 값을 갖는다. 각 노드의 키 값은 다르다.

최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식을 갖는다.

임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키 값보다 크고, 오른쪽 자식의 키값보다 작다.

최선 O(logn), 최악 O(n)

 

레드블랙트리 => O(logn)

 

B-트리 => O(logn)