fibonacci - 要素をフィボナッチ ツリーに挿入する方法は?

Question

Q. 要素をフィボナッチ ツリーにどのように挿入しますか。フィボナッチ木は選別された木に似ているので、私は考えていました。右の木か左の木の​​バランスをとる必要があります。しかし、どのように？

Answer 1

Insert(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

役立つことを願っています