삽입 및 스플레이 노드의 삭제 나무

Question

내가 스플레이 나무에 대한 두 질문이 : 노드

내가 사용하고이 책의

1. 삭제를 다음 말한다 : ''키를 삭제하는 경우 k, 제거 된 노드 w의 부모를 보여줍니다. 8의 예 삭제 :

그러나

, 내가 무엇을하고 있는가하는 것은 이것이다 : 삭제 된 노드가 루트가 아닌 경우에, 나는 (루트)를 넓히다, 삭제 및 벌어지는 가장 오른쪽 왼쪽 하위 트리의 노드. 그러나이 경우 삭제 된 노드가 루트이므로 단순히 제거하고 왼쪽 하위 트리의 맨 오른쪽 노드를 즉시 표시합니다. 이처럼 :

는이 방법이 맞습니까? 그것이 완전히 다르다는 것을 주목하십시오 (제 루트는 나의 책이 말하는 것처럼 6이 아닙니다).

2. 스플레이 트리의 값은 어떤 순서로 삽입됩니까?

위의 왼쪽 트리 예제에 삽입 된 값의 순서를 가져올 수 있습니까? 다시 말해,이 트리가 어떻게 만들어 졌는가 (다음 트리를 생성하기 위해 노드가 순서대로 삽입 됨). 이것을 알아낼 수있는 방법이 있습니까?

Answer 1

노드 삭제 중 : 두 알고리즘이 모두 올바르며 시간이 모두 O (log n) 시간이 걸립니다. 노드를 표시하는 것은 O (log n) 비용입니다. 루트 근처에서 새로운 링크를 생성하면 O (log n)가 발생합니다. 스플레이 트리는 액세스 및 재구성 방법에 많은 유연성을 제공합니다.

삽입 시퀀스 재구성 : 삽입 메소드가 일반적인 불균형 삽입 및 돌출 인 것으로 가정하면 루트가 마지막 삽입입니다. 불행히도, 일반적으로 루트에 스플레이 될 수있는 몇 가지 방법이 있습니다. 명백한 O (n! poly (n)) 시간 무차별 알고리즘에 대한 점근 적 개선은 비용 O (4^n 폴리 (n)) 인 메모 작성으로 철저한 검색을 수행하는 것입니다.