কম্পিউটার

ডেটা স্ট্রাকচারে ওজন-পক্ষপাতমূলক বামপন্থী গাছ


এখানে আমরা বামপন্থী গাছের আরেকটি ভিন্নতা দেখতে পাব। এখানে আমরা রুট থেকে বাহ্যিক নোডের জন্য একটি সংক্ষিপ্ত পথের দৈর্ঘ্যের পরিবর্তে একটি সাবট্রিতে নোডের সংখ্যা বিবেচনা করব। এখানে আমরা নোড x এর ওজন w(x) সংজ্ঞায়িত করব, রুট x সহ সাবট্রিতে অভ্যন্তরীণ নোডের সংখ্যা। যদি x একটি বাহ্যিক নোড হয়, তাহলে ওজন 0 হয়। x যদি অভ্যন্তরীণ নোড হয়, তাহলে ওজন তার সন্তানদের ওজনের যোগফলের থেকে এক বেশি।

এখানে Weight Biased Leftist Tree (WBLT) -

-এর একটি উদাহরণ দেওয়া হল

ধরুন বাইনারি গাছটি এরকম -

ডেটা স্ট্রাকচারে ওজন-পক্ষপাতমূলক বামপন্থী গাছ

আমরা যদি প্রতিটি নোডের জন্য w(x) মান গণনা করি, তাহলে এটি এরকম হবে −

ডেটা স্ট্রাকচারে ওজন-পক্ষপাতমূলক বামপন্থী গাছ

এখন WBLT এর সংজ্ঞা হল −

এর মত

একটি বাইনারি গাছকে ওজন ভারসাম্যযুক্ত বামপন্থী গাছ বলা হয় যদি এবং শুধুমাত্র যদি, প্রতিটি অভ্যন্তরীণ নোডে বাম সন্তানের w(x) ডান সন্তানের w(x) এর চেয়ে বেশি বা সমান হয়। একটি সর্বোচ্চ (মিনিট) ডাব্লুবিএলটি একটি সর্বোচ্চ (মিনিট) গাছ যা একটি ডব্লিউবিএলটিও।


  1. ডেটা স্ট্রাকচারে B+ গাছ

  2. ডাটা স্ট্রাকচারে বাইনারি ট্রি এডিটি

  3. ডেটা স্ট্রাকচারে BSP গাছ

  4. ডেটা স্ট্রাকচারে গাছের পরিসর