数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装研究
法学研究数据结构中的实线树
对于给定的森林，我们将一些给定的边设为“虚线”，其余边保持为实线。每个非叶节点只与一条指向其子节点的“实线”边相关联。所有其他子节点都将通过虚线连接。
更具体地说，在任何给定的树中，最右边的链接（到其子节点）应保持为实线，而所有其他到其其他子节点的链接都创建为“虚线”。
结果，树将被分解成一系列实线路径。实线路径的根将通过虚线连接到其他实线路径。构建了一个新的数据结构，称为“虚拟树”。每个链接和切割树 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)
浏览量 361
