Solid Trees Definition
ใน Forest ที่กำหนด: ทำให้บาง Edges เป็น Dashed ส่วนที่เหลือเป็น Solid
Non-leaf Node แต่ละตัวมี Solid Edge เพียง 1 ตัว ไปยัง Child หนึ่งตัว (Child อื่นๆ = Dashed)
Concrete Rule: Right-most Link = Solid, Other Links = Dashed
Virtual Tree Construction
ผลลัพธ์: Tree แยกเป็น Solid Paths Roots ของ Solid Paths เชื่อมด้วย Dashed Edges
→ สร้าง Virtual Tree V มี Node เซตเดียวกับ Original Tree T
แต่ละ Solid Path → แปลงเป็น Balanced Binary Tree ใน Virtual Tree
Virtual Tree Node มี: (Solid) Left Child, (Solid) Right Child, 0+ (Dashed) Middle Children
Parent-Child Relationship ใน Virtual Tree
Parent q ของ Node p ใน Path = In-order Successor ของ p ใน Solid Tree
ถ้า p เป็น Last Node (In-order) ใน Solid Subtree → Parent Path = Parent ของ Root ของ Solid Subtree นั้น
Formally: Parentpath(v) = Node(Inorder(v) + 1)
Left Subtree = Descendants (In-order น้อยกว่า)
Right Subtree = Ancestors (In-order มากกว่า)
→ Parent ของ Left Child = Ancestor ใน Original Tree
→ Parent ของ Right Child = Descendant ใน Original Tree
Order นี้ช่วยให้ Add Cost ได้อย่างมีประสิทธิภาพ
Definitions & Notation
mincost(x) = Cost ของ Node ที่ Key น้อยสุดใน Descendants ของ x ใน Solid Subtree เดียวกัน
เก็บ 2 Fields ในแต่ละ Node:
δmin(x) = cost(x) - mincost(x) δcost(x) = cost(x) - cost(parent(x)) // ถ้า x มี Solid Parent δcost(x) = cost(x) // ถ้า x เป็น Solid Tree Root
สรุป
Solid Trees + Virtual Trees = Foundation สำหรับ Dynamic Tree Data Structures (Link-Cut Trees, Top Trees) ใช้ In-order Numbering เพื่อแปลง Tree Paths เป็น Balanced Binary Trees รองรับ Path Queries/Updates ได้ O(log n)
