資料結構
網路
關係資料庫管理系統 (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
