ट्री शाटन

ट्री शाटन

Class	Sorting algorithm
Data structure	Array
Worst-case performance	O(n²) (unbalanced) O(n log n) (balanced)
Best-case performance	O(n log n)
Average performance	O(n log n)
Worst-case space complexity	Θ(n)

ट्री सॉर्ट एक सॉर्ट एल्गोरिथ्म है जो सॉर्ट किए जाने वाले तत्वों से एक बाइनरी सर्च ट्री बनाता है, और फिर ट्री को ट्रैवर्स करता है (वृक्ष परिभ्रमण |इन-ऑर्डर) ताकि तत्व सॉर्ट किए गए क्रम में सामने आएं। इसका विशिष्ट उपयोग तत्वों को ऑनलाइन क्रमबद्ध करना है: प्रत्येक प्रविष्टि के बाद, अब तक देखे गए तत्वों का सेट क्रमबद्ध क्रम में उपलब्ध होता है।

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

दक्षता

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

स्व-संतुलन द्विआधारी खोज वृक्ष का उपयोग करके सबसे खराब स्थिति वाले व्यवहार में सुधार किया जा सकता है। ऐसे पेड़ का उपयोग करते हुए, एल्गोरिदम में एक है O(n log n) सबसे खराब स्थिति में प्रदर्शन, इस प्रकार तुलनात्मक प्रकार के लिए डिग्री-इष्टतम है। हालाँकि, ट्री सॉर्ट एल्गोरिदम को क्विकॉर्ट या हीप्सॉर्ट जैसे इन-प्लेस एल्गोरिदम के विपरीत, ट्री के लिए अलग मेमोरी आवंटित करने की आवश्यकता होती है। अधिकांश सामान्य प्लेटफ़ॉर्म पर, इसका मतलब है कि मेमोरी प्रबंधन#HEAP का उपयोग किया जाना चाहिए, जो कि क्विकॉर्ट और ढेर बनाएं और छांटें की तुलना में एक महत्वपूर्ण प्रदर्शन हिट है. बाइनरी सर्च ट्री के रूप में बिखरा हुआ पेड़ का उपयोग करते समय, परिणामी एल्गोरिदम (जिसे spplaysort कहा जाता है) में अतिरिक्त गुण होता है कि यह एक अनुकूली सॉर्ट है, जिसका अर्थ है कि इसका चलने का समय इससे तेज है 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²) सबसे खराब स्थिति।

बाहरी संबंध

• Binary Tree Java Applet and Explanation at the Wayback Machine (archived 29 November 2016)
• Tree Sort of a Linked List
• Tree Sort in C++