AVL 트리 로테이션 효율

Question

AVL 트리 로테이션의 Big O 효율성은 무엇입니까?

예를 들어 - O (logN)를 삽입하여 - O (1)을 검색하여 -?을 삽입 할 때?

를 (이 다시 균형을해야하는 경우)의 균형을 위해 나는 O (logN)를 될 것이라고 생각하지만 난 O의 주장하는 사이트를 발견 (1) - http://users.informatik.uni-halle.de/~jopsi/dinf504/chap4.shtml

(- 나는 그것을 오해하지 않는 한 이 또한 2-3 트리에 대해 동일시겠습니까?) 미리

Answer 1

의 도움을

감사 복잡성은 당신이 말한대로 O (로그 n)입니다. 이 기사에서 각 재조정 작업의 일정 시간, 즉 O (log n) 회를 수행해야하는 동안 각 순환 게재를 의미한다고 생각합니다. 진실이 무엇이든간에 당신은 로그를 말할 때 복잡합니다.