रीबैलेंसिंग एल्गोरिदम (Rebalancing Algorithms) को निम्न तरीके से किया जा सकता है −
डे-स्टाउट-वॉरेन एल्गोरिदम (Day-Stout-Warren Algorithm)
हम वास्तव में डे-स्टाउट-वॉरेन एल्गोरिदम का उपयोग करके रीबैलेंस मेथड लागू कर सकते हैं। यह नोड्स की संख्या में रैखिक (Linear) है।
निम्न बेसिक DSW एल्गोरिदम का स्यूडो कोड में प्रस्तुतीकरण है।
- "प्यूडो-रूट" (Pseudo-root) नामक एक नोड आवंटित करें और ट्री के वास्तविक रूट को प्यूडो-रूट का राइट चाइल्ड बनाएं।
- ट्री को सॉर्टेड लिंक्ड लिस्ट (Sorted Linked List) में बदलने के लिए ट्री-टू-वाइन (Tree-to-Vine) फंक्शन को प्यूडो-रूट को आर्गुमेंट के रूप में कॉल करें।
- सॉर्टेड लिंक्ड लिस्ट को ट्री में फिर से बदलने के लिए वाइन-टू-ट्री (Vine-to-Tree) फंक्शन को प्यूडो-रूट और ट्री के आकार (एलिमेंट्स की संख्या) को आर्गुमेंट के रूप में कॉल करें।
- ट्री का वास्तविक रूट प्यूडो-रूट के राइट चाइल्ड के बराबर होना चाहिए।
- अंत में प्यूडो-रूट को डिस्पोज (Dispose) किया जाना चाहिए।
"कॉपी ऑन राइट" ट्री ("Copy On Write" Tree)
यदि हम रैखिकता (Linearizability) की कमी सहन कर सकते हैं (यानी हम एक मान लिखते हैं लेकिन जब हम इसे तुरंत बाद खोजते हैं तो यह नहीं मिलता; यह अंततः मिल जाएगा, लेकिन 100ms-10s के बाद), तो "कॉपी ऑन राइट" ट्री लागू किया जा सकता है: सभी लिखावट एक थ्रेड द्वारा की जाती है (रीबैलेंसिंग के साथ), और हम समय-समय पर ट्री को रीड-ओनली कॉपी में कॉपी करते हैं जिसे रीडिंग थ्रेड्स द्वारा बिना किसी कंकरेंसी कंट्रोल के लागू किया जा सकता है, हमें इसे परमाणु रूप से (Atomically) प्रकाशित करने की आवश्यकता है।
कंकरेंट स्किप लिस्ट (Concurrent Skip List)
एक अन्य विकल्प कंकरेंट स्किप लिस्ट (Concurrent Skip List) लागू करना है: यह लॉगरिदमिक औसत केस खोज/डिलीट/इंसर्ट समय प्रदान करता है और अधिक आसानी से समानांतर (Parallelizable) होता है। यदि आप इसका उपयोग करते हैं तो जावा के लिए एक मानक लॉक-फ्री कार्यान्वयन (Standard Lock-free Implementation) है। हम कंकरेंट स्किप लिस्ट्स और बैलेंस्ड सर्च ट्रीज़ के बारे में अधिक जानकारी यहाँ प्राप्त कर सकते हैं। विशेष रूप से, हम वहां क्रोमैटिक ट्री (Chromatic Tree) का उल्लेख पा सकते हैं, जिसे कंकरेंट रीबैलेंसिंग (Concurrent Rebalancing) के लिए अनुकूलित बाइनरी सर्च ट्री के रूप में दर्शाया गया है।
