Splay Tree의 상각 분석
Nov 15 2020
Splay Tree 삽입 / 삭제는 다양한 방법으로 수행 할 수 있습니다. 한 가지 인기있는 방법은 키 를 삽입하고 루트로 확장하는 것 입니다. 그러나 내가 읽은 다른 접근 방식도 있습니다. 아이디어는 왼쪽에 값이 <= 삽입 키이고 오른쪽에 값이> 삽입 키가 되도록 2 개의 트리로 분할 하는 것 입니다. 대체 삭제 방법의 경우에도 마찬가지입니다. 삭제할 키가 루트로 확장 된 다음 왼쪽 및 오른쪽 트리가 병합 됩니다.
하지만 내가 이해하는 방식은
- 삽입이 오름차순 인 경우 트리를 분할하면 항상 오른쪽 트리가 null 이되어이 순서로 키가 삽입 될 때마다 불균형이 증가합니다.
- 삭제도 마찬가지입니다. 트리에서 항상 최대 요소를 삭제하면 병합 작업에서 오른쪽 하위 트리가 비어있게됩니다. 그리고 엄청난 불균형이 있습니다.
내 질문은이 대체 프로세스에서 상각 된 실행 시간도 유지 O(logN)됩니까? 그렇다면 어떻게? 인터넷을 통해 검색을 시도했지만 답변을 찾을 수 없습니다. 모든 종류의 직감이 정말 도움이 될 것입니다 :)
답변
2 AmiTavory Nov 15 2020 at 02:22
예, 상각 된 시간은 O (log (n))로 유지됩니다.
직관은 단일 작업 비용과 불균형 사이의 스플레이 트리의 상호 작용입니다. 수술을보고 "이것은 매우 비싸다"또는 "이로 인해 많은 불균형이 발생합니다"라고 말할 수있는 것은 사실이지만 동시에 두 가지를 고려해야합니다.
첫 번째 예를 사용하면 삽입물이 엄청난 불균형을 유발하지만 각각은 O (1)입니다. 이러한 작업이 끝날 때 트리는 불균형하지만이 시점에서 비용은 O (m)에 불과했습니다. 그 후 첫 번째 다른 작업은 매우 비쌀 수 있지만 불균형도 감소합니다.
일련의 삭제에 대한 직관은 비슷합니다. 직관적으로이 둘 사이의 균형도 맞 춥니 다.