지수 트리

Exponential tree
지수 트리
유형나무
발명된1995
발명된 사람아르네 안데르손
큰 O 표기법에서의 시간 복잡성
알고리즘. 평균 최악의 경우
공간 O(n)O(n)
검색 O(최소값 로그 n, 로그 n/log w+ 로그 로그 n, 로그 w 로그 n)O(최소값 로그 n, 로그 n/log w+ 로그 로그 n, 로그 w 로그 n)
삽입하다 O(최소값 로그 n, 로그 n/log w+ 로그 로그 n, 로그 w 로그 n)O(최소값 로그 n, 로그 n/log w+ 로그 로그 n, 로그 w 로그 n)
삭제 O(최소값 로그 n, 로그 n/log w+ 로그 로그 n, 로그 w 로그 n)O(최소값 로그 n, 로그 n/log w+ 로그 로그 n, 로그 w 로그 n)

지수 트리는 이진 검색 트리와 거의 동일하지만 트리 치수가 모든 수준에서 동일하지 않다는 것은 예외다.일반 이진 검색 트리에서 각 노드는 치수(d)가 1이고 하위 노드가 2개d 있다.지수 트리에서 치수는 노드의 깊이와 같으며 루트 노드는 d = 1이다. 따라서 두 번째 레벨은 4개의 노드를, 세 번째 레벨은 8개의 노드를, 네 번째 16개의 노드를 포함할 수 있다.

외부 링크

Stub icon

이 알고리즘이나 데이터 구조와 관련된 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.