द्विआधारी खोज वृक्ष

Question

के लिए खोज यानी किसी को भी कैसे एक द्विआधारी खोज वृक्ष (अर्थात। बुरी से बुरी हालत, सबसे मामला है, और औसत दर-मामला) के लिए खोज समय यह पता लगाने की पता है?

Answer 1

एक गैर आत्म संतुलन पेड़ (संभव है, लेकिन एक खोज पेड़ के लिए असामान्य) के लिए, सबसे ज्यादा मामले O (n) है, जो पतित द्विआधारी पेड़ (एक लिंक्ड सूची) के लिए है।

इस मामले में, आप खोज करने के लिए है, औसत पर, अपने वांछित तत्व खोजने से पहले आधा सूची।

बेस्ट केस ओ (लॉग एन) पूरी तरह से संतुलित पेड़ के लिए है, क्योंकि आप प्रत्येक पेड़ के स्तर के लिए आधे में खोज स्थान काटते हैं।

औसत मामला उन दोनों के बीच में कहीं है और डेटा :-)

पर पूरी तरह से निर्भर जब से तुम शायद ही कभी अनुक्रम जिसमें डेटा एक पेड़ में डाला जाता है को नियंत्रित करने के लिए मिल, आत्म संतुलन के पेड़ आमतौर पर के बाद से बेहतर हैं , जबकि वे प्रत्येक सम्मिलन या हटाने के लिए थोड़ी सी मात्रा जोड़ते हैं, वे खोज को बहुत तेज करते हैं। असंतुलित पेड़ों की तुलना में उनका सबसे बुरा मामला इतना बेहतर है।

    8 
     _______/ \_______ 
     /    \ 
     4     12 
    __/ \__    __/ \__ 
/  \   /  \ 
    2   6  10  14 
/\  /\  /\  /\ 
1 3  5 7  9 11 13 15 

इस अच्छी तरह से संतुलित ट्री में, आपको लगता है कि आप हर n के स्तर के लिए 2 ⁿ -1 नोड्स मिल देख सकते हैं। इसका मतलब है कि 15 नोड्स के लिए, आप कभी नहीं चार से अधिक नोड्स खोज करने के लिए यह पता लगाने के लिए (जैसे, 13 को खोजने के लिए, आप खोज 8, 12, 14 और 13) है। यही वह जगह है जहां लॉग एन आंकड़ा आता है।

एक पतित असंतुलित पेड़, पहले से ही कहा गया है, एक लिंक्ड सूची है। अपने डेटा को अनुक्रम में आ गया है और आप एक असंतुलित द्विआधारी पेड़ में उसे डाला, तो आप प्राप्त करेंगे:

1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -+ 
              | 
+------------------------------------------+ 
| 
+-> 10 -> 11 -> 12 -> 13 -> 14 -> 15 

उस मामले में 13 ढूंढने के लिए, आप 1, 2, 3, 4, 5 खोज करने के लिए आवश्यकता होगी , 6, 7, 8, 9, 10, 11, 12 और 13, इसलिए ओ (एन)।

Answer 2

"होमवर्क" के रूप में यह एक टैग कर सकते हैं। यहाँ एक अच्छा प्रारंभिक बिंदु है: http://en.wikipedia.org/wiki/Binary_search_tree

सामान्य तौर पर, एक संतुलित द्विआधारी खोज वृक्ष हे (लॉग एन), हे का सबसे अच्छा मामले की बुरी से बुरी हालत देखने है (1) (जब वांछित मान जड़ है) और ओ (लॉग एन) का औसत मामला (पत्तियों में उनके माता-पिता की तुलना में तेजी से अधिक मूल्य होते हैं)।

सबसे खराब स्थिति सबसे दिलचस्प है और आसानी से पहचानने एक द्विआधारी पेड़ के पहले स्तर 1 नोड है कि द्वारा देखा जाता है, दूसरा है 2, तीसरे 4 और इतने पर है। इस प्रकार, गहराई n के एक द्विआधारी पेड़ में नोड्स की संख्या n ठीक 2^है - 1। घातीय समारोह के गणितीय उलटा, लघुगणक है इस प्रकार: हे (लॉग एन)।

एक असंतुलित पेड़ एक लिंक्ड सूची के रूप में के रूप में बुरा हो सकता है और इस तरह का एक आकार हो सकता है:

1 
/\ 
    2 
/\ 
     3 
    /\ 
     4 
    /\ 

इस स्थिति में, बुरी से बुरी हालत उपयोग समय हे (एन) है।

Answer 3

सर्वश्रेष्ठ मामला ओ (1) है। पहला तत्व वह वस्तु हो सकता है जिसे आप ढूंढ रहे हैं। सबसे बुरा मामला ओ (एन) यानी एक तिरछे पेड़ में है और औसत मामला ओ (एलजी एन) है।