প্রদত্ত বনের জন্য, আমরা প্রদত্ত প্রান্তগুলির কিছু "ড্যাশড" তৈরি করি এবং বাকিগুলি শক্ত রাখা হয়। প্রতিটি নন-লিফ নোড তার সন্তানদের একজনের সাথে শুধুমাত্র একটি "কঠিন" প্রান্তের সাথে যুক্ত। অন্য সব শিশু একটি ড্যাশড প্রান্তের সাহায্যে সংযুক্ত হবে।
আরও কংক্রিট হওয়ার জন্য, যে কোনও গাছে, সবচেয়ে ডানদিকের লিঙ্কটি (এটির সন্তানের সাথে) শক্ত রাখা উচিত এবং এর অন্যান্য শিশুদের সাথে অন্যান্য সমস্ত লিঙ্ক "ড্যাশড" তৈরি করা উচিত।
ফলস্বরূপ, গাছটি কঠিন পথের সংগ্রহে ভেঙে যাবে। দৃঢ় পথের শিকড় একটি ড্যাশড প্রান্ত দ্বারা অন্য কোনো কঠিন পথের সাথে যুক্ত হবে। একটি "ভার্চুয়াল ট্রি" নির্দেশিত একটি নতুন ডেটা কাঠামো নির্মিত হয়েছে। প্রতিটি লিঙ্কিং এবং কাটিং ট্রি টি একটি ভার্চুয়াল ট্রি V দ্বারা উপস্থাপিত হয়, নোডগুলির একই সেট ধারণকারী। কিন্তু আসল গাছের প্রতিটি কঠিন পথ ভার্চুয়াল ট্রিতে পরিবর্তিত বা বাইনারি ট্রিতে রূপান্তরিত হয়; বাইনারি গাছ যতটা সম্ভব ভারসাম্যপূর্ণ। সুতরাং, একটি ভার্চুয়াল ট্রি একটি (কঠিন) বাম শিশু, একটি (সলিড) ডান শিশু এবং শূন্য বা তার বেশি (ড্যাশড) মধ্যম শিশুদের সাথে যুক্ত।
অন্য কথায়, একটি ভার্চুয়াল ট্রি ড্যাশড প্রান্ত দ্বারা যুক্ত কঠিন বাইনারি গাছের একটি শ্রেণিবিন্যাস নিয়ে গঠিত। প্রতিটি নোড তার পিতামাতা এবং তার বাম এবং ডান শিশুদের একটি পয়েন্টারের সাথে যুক্ত।
আমরা জানি যে প্রতিটি পথ একটি বাইনারি গাছে রূপান্তরিত হয়। পাথের মধ্যে একটি নোডের প্যারেন্ট (say q) (p বলুন) হল কঠিন গাছে সেই নোডের (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)
