जावा ट्रीमैप के लिए लाल-काले पेड़ आधारित कार्यान्वयन क्यों?

Question

wikipedia's article on AVL trees के तीसरे पैरा कहते हैं: "क्योंकि AVL पेड़ अधिक सख्ती से संतुलित कर रहे हैं, वे देखने गहन अनुप्रयोगों के लिए लाल-काले पेड़ों की तुलना में तेजी है।"

तो, TreeMap को लाल-काले पेड़ों की बजाय एवीएल पेड़ों का उपयोग करके लागू नहीं किया जाना चाहिए (क्योंकि एक हैशिंग आधारित डेटा संरचना के लिए गहन प्रशंसा अधिक दिखाई देगी)?

Answer 1

लाल-काले पेड़ अधिक सामान्य उद्देश्य हैं। वे जोड़ने, हटाने और देखने के लिए अपेक्षाकृत अच्छी तरह से करते हैं लेकिन एवीएल पेड़ों में धीमी गति/निकालने की लागत पर तेज़ी से दिखने लगते हैं। जावा की सामान्य नीति सर्वोत्तम सामान्य उद्देश्य डेटा संरचनाएं प्रदान करना है। यह भी वही कारण है जावा का डिफ़ॉल्ट Array.sort (ऑब्जेक्ट [] ए) कार्यान्वयन Quicksort के बजाय स्थिर, अनुकूली, पुनरावृत्ति विलय प्रकार है।

Answer 2

विकिपीडिया लेख गलत है (या कम से कम, वहाँ दावे को वापस करने के लिए कोई समर्थन प्रशस्ति पत्र है)। यह सच है कि एक एवीएल पेड़ (1.44 एलजी एन) की सबसे खराब स्थिति ऊंचाई लाल-काले बीएसटी (2 एलजी एन) की सबसे बुरी स्थिति की ऊंचाई से बेहतर है, लेकिन यह सबसे खराब मामला है और ऐसा करने के लिए बहुत कुछ नहीं हो सकता है असली दुनिया के प्रदर्शन के साथ।

Answer 3

ऐतिहासिक रूप से, घूर्णन की संख्या बहुत महत्वपूर्ण माना जाता था इसलिए लाल रंग के काले पेड़ एवीएल पर चुने गए थे क्योंकि लाल-काले यादृच्छिक आवेषण के साथ थोड़ा कम घूर्णन करते हैं - प्रति बनाम 6 बनाम औसत घूर्णन।

मसा में, AVL पेड़ शायद एक बेहतर विकल्प हो गया होता। https://refactoringlightly.wordpress.com/2017/10/29/performance-of-avl-red-black-trees-in-java/

यादृच्छिक सम्मिलन के साथ प्रदर्शन इसी तरह की है: आप जावा यहाँ AVL & लाल-काले पेड़ की एक प्रदर्शन की तुलना देख सकते हैं। अनुक्रमिक डेटा के साथ एवीएल पेड़ बहुत बेहतर प्रदर्शन करते हैं - 30% या अधिक।