fibonacci - 如何将元素插入斐波那契树？

Question

问：如何将元素插入斐波那契树。我在想，因为斐波那契树就像排序树。我必须平衡右树或左树。但如何？

Answer 1

插入（Q，e）

/* Insert the element e into the relaxed Fibonacci heap Q */
1.Form a tree with a single node N of type I consisting of element e
2. Add(Q, N)
3. With each node N of type I we associate a field lost which denotes the
number of children of type I lost by N since its lost field was last reset to
zero.
For any node N of type I in Q, define WN as the weight of node N as
follows: WN = 0, if N:lost = 0. Else, WN = 2
N:lost¡1
.
Also for any node N of type I, define wN as the increase in WN due to N
losing its last child. That is, wN = 0 or 1 or 2
N:lost¡2
respectively depending
on whether N:lost = 0 or 1 or greater than one.
Define weight W =
P
WN for all N of type I in Q.
Every relaxed Fibonacci heap has a special variable P, which is equal to
one of the nodes of the tree. Initially, P = R.
(a) R:lost = R0:lost = R1:lost = ::: = Rk¡1:lost = 0.
(b) Let N be any node of type I. Let N:degree = d and let the children
of N of type I be N0, N1, ..., Nd¡1. Then, for any Ni
, Ni
:degree +
Ni
:lost ¸ i.
(c) W · n + wP .
4. Associated with Q we have a list LM = (M1; M2; :::; Mm) of all nodes of
type II in Q other than R0
. Each node Mi was originally the R0
of some
relaxed Fibonacci heap Qi till some meld operation. Let ni denote the
number of nodes in Qi
just before that meld operation.
(a) Mi
:degree · 4dlog nie + 4.
(b) ni + i · n

我希望它有帮助