Đối với khu rừng đã cho, chúng tôi tạo ra một số cạnh đã cho "gạch ngang" và phần còn lại của chúng được giữ vững chắc. Mỗi nút không phải của lá chỉ được liên kết với một cạnh “đặc” đối với một trong các nút con của nó. Tất cả các trẻ em khác sẽ được kết nối với sự trợ giúp của một cạnh đứt nét.
Cụ thể hơn, trong bất kỳ cây nhất định nào, liên kết ngoài cùng bên phải (với con của nó) phải được giữ vững chắc và tất cả các liên kết khác với các cây con khác của nó được tạo "đứt nét".
Kết quả là, cây sẽ bị phá vỡ thành một tập hợp các đường đi vững chắc. Rễ của các đường vững chắc sẽ được nối với một số đường vững chắc khác bằng một cạnh đứt nét. Một cấu trúc dữ liệu mới có ký hiệu là “cây ảo” được xây dựng. Mỗi cây liên kết và cây cắt T được biểu diễn bằng một cây ảo V, chứa cùng một tập các nút. Nhưng mỗi đường dẫn rắn của cây ban đầu được sửa đổi hoặc chuyển đổi thành một cây nhị phân trong cây ảo; cây nhị phân càng cân bằng càng tốt. Do đó, một cây ảo được liên kết với một cây con bên trái (liền khối), một cây con bên phải (liền nét) và 0 hoặc nhiều hơn (nét đứt) con ở giữa.
Nói cách khác, cây ảo bao gồm một hệ thống phân cấp của các cây nhị phân đặc được nối với nhau bằng các cạnh đứt nét. Mỗi nút được liên kết với một con trỏ tới cha của nó và tới con trái và phải của nó.
Chúng ta biết rằng mỗi đường dẫn được chuyển đổi thành một cây nhị phân. Nút cha (giả sử q) của một nút (giả sử p) trong đường dẫn là bậc kế thừa theo thứ tự (thứ tự đối xứng) của nút đó (p) trong cây đặc. Tuy nhiên, nếu p là nút cuối cùng (theo thứ tự đối xứng) trong cây con đặc thì đường dẫn cha của nó sẽ là nút cha của gốc của cây con đặc chứa nó.
Formally, Parentpath(v) =Node(Inorder(v)+ 1).
Lưu ý rằng đối với bất kỳ nút nào v, tất cả các nút trong cây con bên trái sẽ có số thứ tự ít hơn và những nút trong cây con bên phải sẽ có số thứ tự cao hơn. Điều này đảm bảo rằng tất cả các nút trong cây con bên trái được biểu thị là con cháu và tất cả các nút trong cây con bên phải được biểu thị là tổ tiên. Do đó, cha mẹ (trong cây nhị phân) của con trái sẽ được coi là tổ tiên (trong cây gốc). Nhưng, cha (trong cây nhị phân) của một con bên phải được coi là con (trong cây gốc). Đơn đặt hàng này, giúp chúng tôi thực hiện việc bổ sung chi phí một cách hiệu quả.
Chúng tôi cần một số định nghĩa hoặc ký hiệu để tiếp tục.
Gọi mincost (x) là chi phí của nút có giá trị khóa nhỏ nhất trong số tất cả các con của x trong cùng một cây con vững chắc.
Sau đó, trong mỗi nút, chúng ta lưu trữ hai trường δcost (x) và δmin (x). Chúng tôi xác định,
δ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)