রিব্যালেন্সিং অ্যালগরিদমগুলো নিচেরভাবে পারফর্ম করা যায় −
ডে-স্টাউট-ওয়ারেন অ্যালগরিদম (Day-Stout-Warren Algorithm)
আমরা আসলে রিব্যালেন্স মেথড বাস্তবায়ন করতে পারি ডে-স্টাউট-ওয়ারেন অ্যালগরিদম ব্যবহার করে। এটি নোডের সংখ্যায় লিনিয়ার।
নিচে বেসিক DSW অ্যালগরিদমের একটি প্রেজেন্টেশন পসিউডো কোডে।
- একটি নোড অ্যালোকেট করা হয় "পসিউডো-রুট" হিসেবে এবং ট্রির একচুয়াল রুটকে পসিউডো-রুটের রাইট চাইল্ড হিসেবে বানানো হয়।
- ট্রি-টু-ভাইন ফাংশন কল করা হয় ট্রি কে সর্টেড লিংকড লিস্টে কনভার্ট করতে পসিউডো-রুট আর্গুমেন্ট হিসেবে।
- ভাইন-টু-ট্রি ফাংশন কল করা হয় সর্টেড লিংকড লিস্টকে আবার ট্রিতে কনভার্ট করতে পসিউডো-রুট এবং ট্রির সাইজ (এলিমেন্টের সংখ্যা) আর্গুমেন্ট হিসেবে।
- ট্রির একচুয়াল রুট পসিউডো-রুটের রাইট চাইল্ড হিসেবে বানানো হয়।
- শেষে পসিউডো-রুট ডিসপোজ করা হয়।
"কপি অন রাইট" ট্রি ("Copy On write" Tree)
যদি আমরা লিনিয়ারিজেবিলিটির অভাব সহন করতে পারি (অর্থাৎ আমরা একটি ভ্যালু লিখি কিন্তু যখন সেটি খুঁজতে যাই তৎক্ষণাৎ এটি না পাওয়া যায়; এটি পরে এভেন্টুয়ালি পাওয়া যাবে, কিন্তু ১০০ms-১০s পরে), একটি "কপি অন রাইট" ট্রি অ্যাপ্লাই করা যায়: সকল রাইটস একটি থ্রেড দ্বারা করা হয় (রিব্যালেন্সিংসহ), এবং আমরা পিরিয়ডিক্যালি ট্রিকে কপি করি একটি রিড-অনলি কপিতে যা রিডিং থ্রেড দ্বারা বাস্তবায়িত হতে পারে কোনো কনকারেন্সি কন্ট্রোল ছাড়া, আমাদের এটিকে অ্যাটোমিকলি পাবলিশ করতে হবে।
কনকারেন্ট স্কিপ লিস্ট (Concurrent Skip List)
একটি অন্য অপশন হলো একটি কনকারেন্ট স্কিপ লিস্ট বাস্তবায়ন করা: এটি লগারিদমিক এভারেজ কেস সার্চ/ডিলিট/ইনসার্ট টাইম প্রদান করে এবং আরও সহজে প্যারালেলাইজ করা যায়। জাভার জন্য একটি স্ট্যান্ডার্ড লক-ফ্রি বাস্তবায়ন আছে যদি আপনি সেটি ব্যবহার করতে হয়। আমরা কনকারেন্ট স্কিপ লিস্ট এবং ব্যালেন্সড সার্চ ট্রি সম্পর্কে আরও ইনফরমেশন পেতে পারি এখানে। বিশেষ করে, আমরা সেখানে একটি ক্রোমেটিক ট্রির মেনশন পেতে পারি, যেটি একটি বাইনারি সার্চ ট্রি যেটি কনকারেন্ট রিব্যালেন্সিং-এর জন্য অপ্টিমাইজড।
