btree의 삽입 복잡성이란 무엇입니까?

Question

새로운 노드가 삽입 될 때 (복잡성이 O (logN) 인 경우), 전체 트리의 균형을 다시 잡아야합니다.

리 밸런싱의 복잡성은 무엇입니까?

Answer 1

나무의 높이입니다. 이진 트리라는 의미에서 재조정되지는 않습니다. 노드를 추가 할 때 분할이 발생하면 위의 노드에 키를 삽입합니다. 그로 인해 분할이 발생하면 루트에 도달 할 때까지 한 레벨 위로 같은 작업을 수행합니다. 따라서 복잡성은 O (logN)입니다.