数据结构中的实体树
对于给定的森林，我们创建一些给定的边缘“虚线”，其余的保持实心。每个非叶节点仅与其一个子节点的一个“实”边关联。所有其他孩子将在虚线的帮助下连接。
更具体地说，在任何给定的树中，最右边的链接（到其子级的链接）应保持牢固，而与其其他子级的所有其他链接均创建为“虚线”。
结果，树将被分解为实体路径的集合。实体路径的根部将通过虚线边缘与其他实体路径连接。构造了一个新的数据结构，称为“虚拟树”。每个链接和切割树T由包含相同节点集的虚拟树V表示。但是原始树的每个实体路径都被修改或转换为虚拟树中的二叉树；二叉树尽可能平衡。因此，虚拟树与（实心）左子代，（实心）右子代和零个或多个（虚线）中间子代相关联。
换句话说，虚拟树由由虚线边缘连接的实心二进制树的层次结构组成。每个节点都与一个指向其父级及其左侧和右侧子级的指针相关联。
我们知道，每个路径都将转换为二叉树。路径中节点（例如p）的父节点（例如q）是实体树中该节点(p)的有序（对称顺序）后继。但是，如果p是实体子树中的最后一个节点（按对称顺序），则其父路径将是包含它的实体子树的根的父节点。
Formally, Parentpath(v) =Node(Inorder(v)+ 1).
请注意，对于任何节点v，左子树中的所有节点将具有较少的有序号，而右子树中的那些节点将具有较高的有序号。这样可以确保将左子树中的所有节点表示为后代，并将右子树中的所有节点表示为祖先。因此，左孩子的父母（在二叉树中）将被视为祖先（在原始树中）。但是，正确的孩子的父母（在二叉树中）被视为后代（在原始树中）。该命令，帮助我们有效地进行增加成本。
我们需要一些定义或符号来进行。
令mincost(x)为同一实体子树中x的所有后代中具有最小键值的节点的成本。
然后，在每个节点中，我们存储两个字段δcost(x)和δmin(x)。我们定义
δmin(x) =cost(x)−mincost(x). And, δcost(x) =cost(x)− cost(parent(x)) if x is associated with a solid parent δcost(x) =cost(x) otherwise (x is treated as a solid tree root)