सर्च ट्री (Search Trees)

सर्च ट्री पदानुक्रमित संरचना में क्रमबद्ध कुंजियों को संग्रहीत करते हैं ताकि खोज, प्रविष्टि और विलोपन एक मूल-से-पत्ती पथ का अनुसरण करें; स्व-संतुलन वाले प्रकार उस पथ को छोटा रखते हैं ताकि लॉगरिदमिक-समय संचालन की गारंटी दी जा सके।

Definition

एक सर्च ट्री एक ट्री-संरचित डेटा संरचना है जो प्रति-नोड ऑर्डरिंग इनवेरिएंट के अनुसार कुंजियों को क्रमबद्ध क्रम में बनाए रखती है, जो कुशल खोज, प्रविष्टि, विलोपन और क्रम-आधारित क्वेरी का समर्थन करती है; एक संतुलित सर्च ट्री अतिरिक्त रूप से अपने आकार को इस प्रकार बाधित करता है कि कुंजियों की संख्या में ऊंचाई लॉगरिदमिक बनी रहे।

Scope

यह विषय पेड़ों पर आधारित क्रमबद्ध डिक्शनरी संरचनाओं को शामिल करता है: बाइनरी सर्च ट्री और इसका ऑर्डरिंग इनवेरिएंट, स्व-संतुलन योजनाएं जो ऊंचाई को सीमित करती हैं (AVL, रेड-ब्लैक, और अन्य), और मल्टीवे बैलेंस्ड ट्री जैसे B-ट्री जो बाहरी भंडारण के लिए डिज़ाइन किए गए हैं। यह उन परिचालनों को संबोधित करता है जो ये संरचनाएं साधारण लुकअप से परे समर्थन करती हैं — पूर्ववर्ती, अनुवर्ती, रेंज क्वेरी और क्रमबद्ध ट्रैवर्सल — और उनकी तुलना हैश तालिकाओं से करती हैं, जो क्रम को संरक्षित नहीं करती हैं।

Core questions

• बाइनरी-सर्च-ट्री ऑर्डरिंग इनवेरिएंट खोज को मूल-से-पत्ती तक कैसे बनाता है?
• एक असंतुलित ट्री रैखिक समय तक क्यों गिर सकता है, और संतुलन इसे कैसे रोकता है?
• कौन से रोटेशन या संरचनात्मक नियम AVL और रेड-ब्लैक ट्री को संतुलित रखते हैं?
• B-ट्री बाइनरी ट्री के बजाय डिस्क और डेटाबेस भंडारण के लिए क्यों उपयुक्त हैं?
• हैश तालिका पर अतिरिक्त लागत के बावजूद क्रम-संरक्षण संचालन कब सार्थक होते हैं?

Key concepts

• बाइनरी सर्च ट्री इनवेरिएंट
• ट्री रोटेशन
• AVL ट्री
• रेड-ब्लैक ट्री
• B-ट्री
• ट्री की ऊंचाई और संतुलन
• इन-ऑर्डर ट्रैवर्सल
• रेंज और अनुवर्ती क्वेरी

Key theories

ऊंचाई संतुलन लॉगरिदमिक संचालन की गारंटी देता है

रोटेशन या संरचनात्मक नियमों के माध्यम से संतुलन इनवेरिएंट को बनाए रखने से, स्व-संतुलन वाले ट्री ऊंचाई को O(log n) रखते हैं, जो इनपुट क्रम की परवाह किए बिना सबसे खराब स्थिति में O(log n) खोज, प्रविष्टि और विलोपन की गारंटी देता है।

बाहरी मेमोरी के लिए मल्टीवे ट्री

B-ट्री डिस्क ब्लॉक आकार से मेल खाने के लिए प्रति नोड कई कुंजियों को संग्रहीत करते हैं, जिससे धीमी बाहरी-मेमोरी एक्सेस की संख्या कम हो जाती है; यह उन्हें डेटाबेस और फ़ाइल सिस्टम के लिए मानक संरचना बनाता है।

Clinical relevance

सर्च ट्री उन प्रणालियों के लिए केंद्रीय हैं जिन्हें क्रमबद्ध पहुंच की आवश्यकता होती है: रेड-ब्लैक ट्री मानक पुस्तकालयों में क्रमबद्ध मानचित्रों और सेटों को लागू करते हैं, B-ट्री और उनके प्रकार संबंधपरक डेटाबेस और फ़ाइल सिस्टम में प्रमुख अनुक्रमणिका संरचना हैं, और संतुलित ट्री रेंज क्वेरी, अंतराल शेड्यूलिंग और ज्यामितीय खोज संरचनाओं का समर्थन करते हैं।

History

AVL ट्री, पहले स्व-संतुलन वाले बाइनरी सर्च ट्री, 1962 में एडेलसन-वेल्स्की और लैंडिस द्वारा प्रस्तुत किए गए थे। बेयर और मैकक्रेइट ने 1972 में बड़े क्रमबद्ध अनुक्रमणिकाओं के लिए B-ट्री प्रस्तुत किए, और रेड-ब्लैक ट्री को 1978 में गुइबास और सेजविक द्वारा एक व्यावहारिक संतुलन योजना के रूप में विकसित किया गया था, जो कई मानक पुस्तकालय कार्यान्वयनों का आधार बन गए।

Key figures

• Georgy Adelson-Velsky
• Evgenii Landis
• Rudolf Bayer
• Robert Sedgewick
• Robert Tarjan

Seminal works

• bayer1972
• cormen2009

Frequently asked questions

सर्च ट्री के बजाय हमेशा हैश तालिका का उपयोग क्यों नहीं किया जाता है?

हैश तालिकाएं तेज़ औसत लुकअप देती हैं लेकिन कोई क्रम नहीं। सर्च ट्री कुंजियों को क्रमबद्ध रखते हैं, जिससे रेंज क्वेरी, क्रमबद्ध पुनरावृति, और पूर्ववर्ती/अनुवर्ती लुकअप O(log n) में सक्षम होते हैं, जो हैश तालिकाएं कुशलता से नहीं कर सकतीं। चुनाव इस बात पर निर्भर करता है कि क्रम मायने रखता है या नहीं।

डेटाबेस बाइनरी सर्च ट्री के बजाय B-ट्री का उपयोग क्यों करते हैं?

B-ट्री प्रत्येक नोड में कई कुंजियों को पैक करते हैं ताकि डिस्क ब्लॉक के आकार से मेल खा सकें, इसलिए एक खोज उसी कुंजी गणना के बाइनरी ट्री की तुलना में बहुत कम धीमी बाहरी-मेमोरी ब्लॉक को छूती है। यह I/O को कम करता है, जो डेटाबेस और फ़ाइल सिस्टम में प्रदर्शन पर हावी होता है।