바이너리 검색 트리 성능

따라서 키를 찾는 데 O (높이) 시간이 걸리며 주어진 키보다 큰 키를 가진 모든 노드를 찾기까지 얼마나 걸립니까? 일정한 요인은 무엇입니까?바이너리 검색 트리 성능

2012-07-12 synapse

숙제처럼 들립니다. 태그를 붙이십시오. 일정한 요소는 대개 실생활에서 실험적으로 결정됩니다. – dfeuer

제대로 수행되면 키를 찾아 다음 순서로 이동합니다.

따라서 O (logn) + m이됩니다. 여기서 m은 키보다 큰 버그 수입니다.
최악의 경우는 O (logn) + n = O (n)

2012-07-12 07:26:58

트리가 비 직선이고 직선 체인 일 때 키를 찾는 최악의 경우는 O (n) ->입니다. 전체적으로 O (n) + n = O (n) – Rndm

답변