알고리즘 과정의 최근 테스트에서 주어진 이진 트리의 균형을 맞추기 위해 AVL 트리를 리 밸런싱하는 데 사용되는 메소드를 사용하는 작업이있었습니다. 문제는 해당 트리가 BST가 아닌 경우 무엇입니까? 회전을 사용하는 것이 합리적입니까? 내 말은, 당신은 그것들을 사용할 수 있지만 그것을 고치기 전에 그러한 나무의 균형을 유지할 수있는 방법이없는 것 같습니다 .e.e. 그것을 BST로 만듭니다.비 BST 밸런싱
가능한 경우 상황이 유용 할 수 있습니까? 혼란을 가져 오는 것 외에는이 배후의 진정한 논리를 찾지 못하는 것 같습니다.
이것은 실제로 트리가 무엇을 나타내는가에 달려 있습니다. 트리 로테이션은 이진 검색 트리에 대해 이야기 할 때 자연스러운 생각입니다. 트리가 이진 검색 속성을 유지하면서 트리를 다시 형성하는 방법을 나타 내기 때문입니다. 다른 나무에서는 이것이 불가능할 수도 있습니다. 예를 들어 BST와 다소 유사하지만 더 높은 차원에서 작동하는 k-d tree에서 트리의 노드 수준이 노드에 대한 비교가 작동하는 방식을 결정하기 때문에 회전이 가능하지 않습니다. 그러나 하위 트리를 제거하고 처음부터 다시 작성하여 k-d 트리를 다시 조정할 수 있습니다. 이 아이디어는 일반 BST에서도 사용할 수 있으며 자세한 내용은 scapegoat tree을 참조하십시오.
구문 분석 트리와 같은 다른 트리 구조에서는 트리가 순서가 아닌 계층 구조를 인코딩하기 때문에 회전이라는 아이디어가 전혀 이해가되지 않습니다. 이 경우 트리는 근본적으로 불균형을 띠고 있기 때문에 근본적으로 불균형을 겪을 수 있습니다.
일반적으로 아니요, 특정 상황에서는 더 균형 잡힌 나무에 대해 이야기하는 것이 가능할 수도 있지만 일반적으로 아니요, BST가 아닌 사람에게 나무 회전을 일반화 할 방법이 없습니다.
BST를 사용하는 진정한 의미는 O (logn) 검색에 있으며 각 요소를 바꿉니다. 트리가 바이너리가 아닌 경우 검색 및 교체에 비용이 많이 소요되므로 AVL을 사용하여 최악의 경우 연결된 목록이되는 BST로 균형을 유지할 수 있습니다.
응용 프로그램에는 메모리 관리, 프로세스 스케줄링 등이 포함됩니다. 그리고 더 많은.