AVL 트리와 Binary Search Trees 사이의 시간 복잡도는 평균적인 경우 동일하며 최악의 시나리오에서는 AVL이 BST를 상회합니다. 이것은 AVL이 BST보다 항상 상호 작용할 수있는 모든 가능한 방법으로 우수하다는 힌트를 제공합니다. 아마도 구현의 균형을 맞추기 위해 약간의 복잡성이 추가 될 것입니다.AVL 트리를 통한 이진 탐색 트리
AVL 대신 BST를 사용해야하는 이유가 있습니까?
먼저 가능한 최상의 성능을 얻는 것이 이 아니고 프로그래밍의 궁극적 인 목표입니다. 따라서 옵션 B가 A보다 항상 빠르고 메모리가 적더라도 더 복잡한 경우 항상 더 나은 옵션이라는 의미는 아닙니다. 더 복잡한 코드는 작성하는 데 시간이 오래 걸리며 이해하기가 어렵고 버그가 포함될 가능성이 더 큽니다. 그래서, 간단하지만 덜 효율적인 옵션 A가 당신에게 충분하다면, 그것이 더 나은 선택이라는 것을 의미합니다.
AVL 트리를 밸런싱없이 간단한 이진 검색 트리 (BST)와 비교하려는 경우 AVL은 더 많은 메모리를 소비하며 (각 노드는 균형 요소를 기억해야 함) 각 동작은 느려질 수 있습니다 균형 요소를 유지하고 때로는 회전을 수행).
말했듯이 밸런싱이없는 BST는 매우 나쁜 (선형) 최악의 경우입니다. 그러나이 최악의 경우가 발생하지 않는다는 사실을 알고 있거나 드문 경우에서 작동이 느린 경우 괜찮 으면 밸런싱이없는 BST가 AVL보다 좋을 수 있습니다.
내가 기다리고 있었던 이유. 고맙습니다. –
내 가정 : BST를 언급 할 때 균형을 유지하지 않는 BST를 의미합니다.
네비 게이트 가능한 데이터 구조가 필요하고 데이터가 최악 (정렬)되지 않고 다소 작을 경우 BST (잔액 제외)가 적합 할 수 있다고 주장 할 수 있습니다.
하지만 드문 경우입니다.
AVL 트리도 BST이지만 자체적으로 다시 조정할 수 있습니다. 이 동작으로 인해 최악의 경우에 더 빨리 수행됩니다. 그것은 재 균형을 유지하기 때문에 최악의 경우 일반 BST가 O (n)을 취할 때 O (log n) 시간을 소비합니다. 그래서, 귀하의 질문에 대한 답변 : 그것은 항상 평범한 BST보다 AVL 트리를 구현하는 것이 좋습니다.
균형 요소 및 순환 노드를 확인하고 업데이트하는 데 추가되는 오버 헤드가 있으므로 AVL 트리의 삽입 및 삭제는 균형이 맞지 않는 BST와 비교할 때 상당히 느릴 수 있습니다.
긴밀한 균형 조정으로 인해 검색은 선형적인 시간을 가져 오지 않으므로 트리를 업데이트하는 것보다 검색이 자주 이루어지는 상황에서 AVL 트리를 사용하는 것이 좋습니다.
AVL 나무는 유행에 뒤 떨어지고 요즘에는 적색 검은 나무로 대체되었습니다. – starblue