পুনঃব্যালেন্সিং অ্যালগরিদমগুলি নিম্নলিখিত উপায়ে সঞ্চালিত হতে পারে -
ডে-স্টাউট-ওয়ারেন অ্যালগরিদম
ডে-স্টাউট-ওয়ারেন অ্যালগরিদম ব্যবহার করে আমরা প্রকৃতপক্ষে রিব্যালেন্স পদ্ধতি প্রয়োগ করতে পারি। এটি নোডের সংখ্যার ক্ষেত্রে রৈখিক।
নিচে ছদ্ম কোডে মৌলিক DSW অ্যালগরিদমের একটি উপস্থাপনা।
- একটি নোড বরাদ্দ করা হয় যাকে "ছদ্ম-মূল" বলা হয় এবং গাছের প্রকৃত মূলটিকে ছদ্ম-মূলের সঠিক সন্তান হিসাবে তৈরি করে।
- গাছকে সাজানো লিঙ্ক তালিকায় রূপান্তর করার জন্য ট্রি-টু-ভাইন ফাংশনকে কল করুন সিউডো-রুট এর আর্গুমেন্ট হিসাবে।
- ছদ্ম-মূল এবং তার যুক্তি হিসাবে গাছের আকার (উপাদানের সংখ্যা) দিয়ে সাজানো লিঙ্কযুক্ত তালিকাকে আবার গাছে রূপান্তর করার জন্য লতা-থেকে-গাছ ফাংশনকে কল করুন।
- গাছের প্রকৃত শিকড় ছদ্ম-মূলের ডান সন্তানের সমান।
- শেষ পর্যন্ত ছদ্ম-মূলটি নিষ্পত্তি করা উচিত।
"কপি অন লিখুন" ট্রি
যদি আমরা রৈখিকতার অভাব সহ্য করতে পারি (অর্থাৎ আমরা একটি মান লিখি কিন্তু যখন আমরা এটি খুঁজে না পাওয়ার সাথে সাথে এটি অনুসন্ধান করি; এটি অবশেষে পাওয়া যাবে, কিন্তু 100ms-10s পরে), একটি "লিখনের উপর অনুলিপি" গাছ প্রয়োগ করা যেতে পারে:সমস্ত লেখা একটি থ্রেড (পুনঃব্যালেন্সিং সহ) দ্বারা সঞ্চালিত হয়, এবং আমরা পর্যায়ক্রমে ট্রিটিকে একটি পঠনযোগ্য অনুলিপিতে অনুলিপি করি যা কোনো সমগতি নিয়ন্ত্রণ ছাড়াই থ্রেড পড়ার মাধ্যমে প্রয়োগ করা যেতে পারে, আমাদের এটিকে পারমাণবিকভাবে প্রকাশ করতে হবে।
সমবর্তী এড়িয়ে যাওয়ার তালিকা
আরেকটি বিকল্প হল সমবর্তী স্কিপ তালিকা বাস্তবায়ন করা:এটি লগারিদমিক গড় কেস অনুসন্ধান/মুছুন/সন্নিবেশ করার সময় প্রদান করে এবং আরও সহজে সমান্তরাল। জাভার জন্য একটি আদর্শ লক-মুক্ত বাস্তবায়ন আছে যদি আপনি এটি বাস্তবায়ন করতে চান। আমরা এখানে সমসাময়িক স্কিপ তালিকা এবং সুষম অনুসন্ধান গাছ সম্পর্কে আরও তথ্য পেতে পারি। বিশেষ করে, আমরা সেখানে একটি ক্রোম্যাটিক ট্রির উল্লেখ পেতে পারি, যা একটি বাইনারি সার্চ ট্রি হিসাবে চিহ্নিত যা সমবর্তী পুনঃব্যালেন্সিংয়ের জন্য অপ্টিমাইজ করা হয়৷
