Algorithm
검색 트리
KimJye
2020. 1. 15. 02:42
이진트리 (BST)
각 노드는 하나씩의 키 값을 갖는다. 각 노드의 키 값은 다르다.
최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식을 갖는다.
임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키 값보다 크고, 오른쪽 자식의 키값보다 작다.
최선 O(logn), 최악 O(n)
레드블랙트리 => O(logn)
B-트리 => O(logn)