ट्री शाटन: Difference between revisions

From Vigyanwiki
Line 13: Line 13:
}}
}}


'''ट्री (तरु) शाटन''' एक [[सॉर्ट एल्गोरिथ्म|शाटन एल्गोरिथ्म]] है जो शाटन किए जाने वाले अवयवों से एक [[बाइनरी सर्च ट्री|बाइनरी खोज ट्री]] बनाता है, और फिर ट्री को ([[क्रम में]]) ट्रैवर्स करता है ताकि अवयव शाटन किए गए क्रम में सामने आएं।<ref name="McLuckie Barber p. ">{{cite book | chapter = Binary Tree Sort | last=McLuckie | first=Keith | last2=Barber | first2=Angus | title=माइक्रो कंप्यूटर के लिए क्रमबद्ध दिनचर्या| publisher=Macmillan | publication-place=Basingstoke | date=1986 | isbn=0-333-39587-5 | oclc=12751343 | page=}}</ref> इसका प्रारुपिक उपयोग अवयवों को [[ऑनलाइन]] शाटन करना है: प्रत्येक निवेशन के बाद, अब तक देखे गए अवयवों के सेट शाटन क्रम में उपलब्ध होते है।
'''ट्री शाटन''' एक [[सॉर्ट एल्गोरिथ्म|शाटन एल्गोरिथ्म]] है जो शाटन किए जाने वाले अवयवों से एक [[बाइनरी सर्च ट्री|बाइनरी खोज ट्री]] बनाता है, और फिर ट्री को ([[क्रम में]]) ट्रैवर्स करता है ताकि अवयव शाटन किए गए क्रम में सामने आएं।<ref name="McLuckie Barber p. ">{{cite book | chapter = Binary Tree Sort | last=McLuckie | first=Keith | last2=Barber | first2=Angus | title=माइक्रो कंप्यूटर के लिए क्रमबद्ध दिनचर्या| publisher=Macmillan | publication-place=Basingstoke | date=1986 | isbn=0-333-39587-5 | oclc=12751343 | page=}}</ref> इसका प्रारुपिक उपयोग अवयवों को [[ऑनलाइन]] शाटन करना है: प्रत्येक निवेशन के बाद, अब तक देखे गए अवयवों के सेट शाटन क्रम में उपलब्ध होते है।


ट्री शाटन का उपयोग एक बार के शाटन के रूप में किया जा सकता है, लेकिन यह [[जल्दी से सुलझाएं|द्रुत शाटन]] के तुल्य है क्योंकि दोनों एक केन्द्र बिन्दु के आधार पर अवयवों को पुनरावर्ती रूप से विभाजित करते हैं, और चूंकि द्रुत शाटन अपनी जगह पर है और इसका ओवरहेड (उपरि) कम है, इसलिए ट्री शाटन के द्रुत शाटन की तुलना में कुछ लाभ हैं। जब स्व-संतुलन ट्री का उपयोग किया जाता है तो इसकी सबसे अनुपयुक्त स्थिति बेहतर होती है, लेकिन इससे भी अधिक उपरि होती है।
ट्री शाटन का उपयोग एक बार के शाटन के रूप में किया जा सकता है, लेकिन यह [[जल्दी से सुलझाएं|द्रुत शाटन]] के तुल्य है क्योंकि दोनों एक केन्द्र बिन्दु के आधार पर अवयवों को पुनरावर्ती रूप से विभाजित करते हैं, और चूंकि द्रुत शाटन अपनी जगह पर है और इसका ओवरहेड (उपरि) कम है, इसलिए ट्री शाटन के द्रुत शाटन की तुलना में कुछ लाभ हैं। जब स्व-संतुलन ट्री का उपयोग किया जाता है तो इसकी सबसे अनुपयुक्त स्थिति बेहतर होती है, लेकिन इससे भी अधिक उपरि होती है।
Line 23: Line 23:


== उदाहरण ==
== उदाहरण ==
स्यूडोकोड में निम्नलिखित ट्री शाटन एल्गोरिदम [[कुल ऑर्डर]] स्वीकार करता है और आइटम को आरोही क्रम में आउटपुट करता है:
स्यूडोकोड में निम्नलिखित ट्री शाटन एल्गोरिदम [[तुलनीय आइटम के संग्रह]] को स्वीकार करता है और आइटम को आरोही क्रम में आउटपुट करता है:


{{syntaxhighlight|lang=sql|
{{syntaxhighlight|lang=sql|
Line 58: Line 58:
}}
}}


एक सरल [[कार्यात्मक प्रोग्रामिंग]] रूप में, एल्गोरिदम ([[हास्केल (प्रोग्रामिंग भाषा)]] में) कुछ इस तरह दिखेगा:
एक सरल [[कार्यात्मक प्रोग्रामिंग|फंक्शनल प्रोग्रामिंग]] रूप में, एल्गोरिदम ([[हास्केल (प्रोग्रामिंग भाषा)|हास्केल]] में) कुछ इस प्रकार दिखेगा:


<syntaxhighlight lang="haskell">
<syntaxhighlight lang="haskell">
Line 76: Line 76:
  treesort = flatten . foldr insert Leaf
  treesort = flatten . foldr insert Leaf
</syntaxhighlight>
</syntaxhighlight>
उपरोक्त कार्यान्वयन में, सम्मिलन एल्गोरिदम और पुनर्प्राप्ति एल्गोरिदम दोनों हैं {{math|''O''(''n''²)}} सबसे खराब स्थिति।
उपरोक्त कार्यान्वयन में, निवेशन एल्गोरिदम और पुनःप्राप्ति एल्गोरिदम दोनों हैं {{math|''O''(''n''²)}} सबसे अनुपयुक्त स्थिति है।


== बाहरी संबंध==
== बाहरी संबंध==

Revision as of 09:41, 4 July 2023

ट्री शाटन
Binary tree sort(2).png
ClassSorting algorithm
Data structureArray
Worst-case performanceO(n²) (unbalanced) O(n log n) (balanced)
Best-case performanceO(n log n)[citation needed]
Average performanceO(n log n)
Worst-case space complexityΘ(n)

ट्री शाटन एक शाटन एल्गोरिथ्म है जो शाटन किए जाने वाले अवयवों से एक बाइनरी खोज ट्री बनाता है, और फिर ट्री को (क्रम में) ट्रैवर्स करता है ताकि अवयव शाटन किए गए क्रम में सामने आएं।[1] इसका प्रारुपिक उपयोग अवयवों को ऑनलाइन शाटन करना है: प्रत्येक निवेशन के बाद, अब तक देखे गए अवयवों के सेट शाटन क्रम में उपलब्ध होते है।

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

दक्षता

बाइनरी खोज ट्री में एक आइटम जोड़ना औसतन एक O(log n) प्रक्रम है (बड़े O चिन्हांकन में)। n आइटम जोड़ना एक O(n log n) प्रक्रम है, जिससे ट्री शाटन एक 'फास्ट शाटन' प्रक्रम बन जाता है। असंतुलित बाइनरी ट्री में एक आइटम जोड़ने के लिए सबसे अनुपयुक्त स्थिति में O(n) समय की आवश्यकता होती है: जब ट्री एक श्रृंखलित सूची (अपभ्रष्ट ट्री) जैसा दिखता है। इसके परिणामस्वरूप इस शाटन एल्गोरिदम के लिए O(n²) समय की सबसे अनुपयुक्त स्थिति उत्पन्न होती है। यह सबसे अनुपयुक्त स्थिति तब होती है जब एल्गोरिदम पहले से ही शाटन सेट पर काम करता है, या जो लगभग शाटन, उत्क्रमित या लगभग उत्क्रमित होता है। हालाँकि, प्रत्याशित O(n log n) समय को सरणी में समवकुलन करके प्राप्त किया जा सकता है, लेकिन यह समान आइटम के लिए मदद नहीं करता है।

स्व-संतुलन बाइनरी खोज ट्री का उपयोग करके सबसे अनुपयुक्त स्थिति वाली गतिविधि में सुधार किया जा सकता है। ऐसे ट्री का उपयोग करते हुए, एल्गोरिदम में O(n log n) सबसे अनुपयुक्त स्थिति वाला निष्पादन होता है, इस प्रकार तुलनात्मक शाटन के लिए कोटि-इष्टतम होती है। हालाँकि, ट्री शाटन एल्गोरिदम को द्रुत शाटन या हीप शाटन जैसे स्वस्थाने एल्गोरिदम के विपरीत, ट्री के लिए अलग मेमोरी आवंटित करने की आवश्यकता होती है। अधिकांश सामान्य प्लेटफार्मों पर, इसका अर्थ है कि हीप मेमोरी का उपयोग करना होगा, जो कि द्रुत शाटन और हीप शाटन की तुलना में एक महत्वपूर्ण निष्पादन हिट है।[citation needed] बाइनरी खोज ट्री के रूप में स्प्ले ट्री का उपयोग करते समय, परिणामी एल्गोरिदम (जिसे स्प्लेशाटन कहा जाता है) में अतिरिक्त गुण होता है कि यह एक अनुकूली शाटन है, जिसका अर्थ है कि इसका चलन समय लगभग शाटन किए गए इनपुट के लिए O(n log n) से तेज़ है।

उदाहरण

स्यूडोकोड में निम्नलिखित ट्री शाटन एल्गोरिदम तुलनीय आइटम के संग्रह को स्वीकार करता है और आइटम को आरोही क्रम में आउटपुट करता है:

 STRUCTURE BinaryTree
     BinaryTree:LeftSubTree
     Object:Node
     BinaryTree:RightSubTree
 
 PROCEDURE Insert(BinaryTree:searchTree, Object:item)
     IF searchTree.Node IS NULL THEN
         SET searchTree.Node TO item
     ELSE
         IF item IS LESS THAN searchTree.Node THEN
             Insert(searchTree.LeftSubTree, item)
         ELSE
             Insert(searchTree.RightSubTree, item)
 
 PROCEDURE InOrder(BinaryTree:searchTree)
     IF searchTree.Node IS NULL THEN
         EXIT PROCEDURE
     ELSE
         InOrder(searchTree.LeftSubTree)
         EMIT searchTree.Node
         InOrder(searchTree.RightSubTree)
 
 PROCEDURE TreeSort(Collection:items)
     BinaryTree:searchTree
    
     FOR EACH individualItem IN items
         Insert(searchTree, individualItem)
    
     InOrder(searchTree)

एक सरल फंक्शनल प्रोग्रामिंग रूप में, एल्गोरिदम (हास्केल में) कुछ इस प्रकार दिखेगा:

 data Tree a = Leaf | Node (Tree a) a (Tree a)

 insert :: Ord a => a -> Tree a -> Tree a
 insert x Leaf = Node Leaf x Leaf
 insert x (Node t y s)
     | x <= y = Node (insert x t) y s
     | x > y  = Node t y (insert x s)

 flatten :: Tree a -> [a]
 flatten Leaf = []
 flatten (Node t x s) = flatten t ++ [x] ++ flatten s

 treesort :: Ord a => [a] -> [a]
 treesort = flatten . foldr insert Leaf

उपरोक्त कार्यान्वयन में, निवेशन एल्गोरिदम और पुनःप्राप्ति एल्गोरिदम दोनों हैं O(n²) सबसे अनुपयुक्त स्थिति है।

बाहरी संबंध


संदर्भ

  1. McLuckie, Keith; Barber, Angus (1986). "Binary Tree Sort". माइक्रो कंप्यूटर के लिए क्रमबद्ध दिनचर्या. Basingstoke: Macmillan. ISBN 0-333-39587-5. OCLC 12751343.