피보나치 더미의 dequeuemin

Question

피보나치 힙에 대해 물어보고 싶었습니다. 나는이 시나리오가있는 경우 : 다음

A 
| 
B 

을, 우리는 두 개 노드 C를 추가하고 D :

A 
| 
C 
| 
D 

이제 우리는 추가 E와 F :

A 
|\ 
B C 
    | 
    D 

이제 우리는 B를 삭제

나는 그것이 다음과 같은 나무를 만드는 것을 보았다 :

E 
|\ 
F A 
    | 
    C 
    | 
    D 

그러나 왜 E와 F가 나무과 연결되어 있는지 이해가되지 않습니다. 내가 읽은 것에서 우리는 동일한 순위 (예를 들어, 한 노드의 트리와 한 노드의 다른 트리)의 트리를 연결합니까?

대단히 감사합니다.

Answer 1

첫 번째 피보나치 힙에 노드 C와 D를 추가하면 그리는 트리가 끝나지 않을 것입니다. 대신,이 힙이있을 것이다 :

A C D 
    | 
    B 

피보나치 힙을 삭제 물건을 유유히 나무의 최상위 목록에 각각 새로 추가 된 값을 추가 만 합체 것을 기억하십시오. 당신이 B를 삭제한다면, 당신은 다음과 같이 최상위 레벨로 승격 것 :

A B C D 

그런 다음 B 제거 할 것

: 이제

A C D 

을, 루트 목록을 스캔 것 같은 순서의 나무들을 하나로 합친다. 의 당신이 순서 A의 노드를 스캔 가정하자, C, D. 첫째, 당신은 다음과 같이 함께 A와 C를 병합합니다 :이 시점에서

A D 
    | 
    C 

가 더 이상 합체가 일어나지 않습니다, 정확히 하나가 이후 각 주문의 나무. 그런 다음 E와 F에 추가하는 경우

,이 같은 최상위 수준에 넣어 것 :

A D E F 
    | 
    C 

그래서 그래, 당신 말이 맞아, 그 노드는에 추가되지해야한다 나무.