차례:
정의-자체 균형 이진 검색 트리 란 무엇입니까?
자체 균형 이진 검색 트리는 일관된 수준의 노드 액세스를 제공하기 위해 자체 조정되는 데이터 구조 유형입니다. 자체 균형 이진 검색 트리에서는 최상위 노드에서 추가 노드로의 연결이 정렬 및 재조정되어 트리가 고르고 각 끝 노드의 검색 궤적 선 길이가 동일합니다.
자체 균형 이진 검색 트리는 균형 트리 또는 높이 균형 이진 검색 트리라고도합니다.
Techopedia는 자체 균형 이진 검색 트리를 설명합니다
이진 검색 트리는 일반적으로 맨 위에 하나의 노드가 있고 각 후속 레벨에서 하나 또는 두 개의 노드가 연결된 데이터 구조를 제공합니다. 이진 검색 트리는 세 가지 작업을 지원합니다. 운영자는 구성 요소를 삽입하거나 구성 요소를 삭제하거나 일부 또는 다른 노드 내용을 조회 할 수 있습니다. 이진 검색 트리의 장점 중 하나는 시스템이 모든 수준에서 트리의 절반을 무시하도록 정렬 할 수있어보다 효율적인 검색 작업 부하를 얻을 수 있다는 것입니다.
자체 균형 이진 검색 트리의 긍정적 인 측면은 노드 액세스가 동일하다는 것입니다. 예를 들어, 자체 때문에 트리의 한 쪽에서 5 단계를 이동하거나 다른 쪽에서 3 단계를 이동하지 않아도됩니다. -노드 구조가 조정되면 검색은 특정 엔드 노드로 특정 단계 (n) 만 이동합니다. 이것은 개별 노드 연결을 제거하고이를 트리의 특정 사지를 단축시키기 위해 이진 연결로 대체함으로써 달성됩니다.
자체 밸런싱 이진 검색 3의 단점은 노드 연결이 "레벨에 구애받지 않는"경우에만 작동합니다. 즉, 트리 분기를 단축하기 위해 개별 노드를 이전 레벨로 다시 조정할 수있는 경우에만 작동합니다 . 예를 들어, 자체 균형 이진 검색 트리가 맨 위에 주어진 숫자와 양쪽에 두 개의 후속 숫자로 구성되어 있고 단일 노드 연결을 가진 세 개의 추가 숫자 체인이 있으면 트리를 조정하면 제 3 노드는 제 4 노드 대신 제 3 노드와 함께 제 3 노드가 하나 대신에 2 개의 연결 노드를 갖도록한다. 그러나 데이터 구조가 특정 상위 / 하위 관계와 관련된 특정 노드 컨텐츠를 식별해야하는 경우 트리 구조 균일성에 맞게 이러한 노드를 조정하면 작동하지 않습니다.
