एक बाइनरी ट्री बनाना

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

बाइनरी ट्री या बाइनरी सर्च ट्री

नीचे दिया गया वास्तविक कोड बाइनरी सर्च ट्री (BST) को लागू करता है, जो कि बाइनरी पेड़ों का अधिक विशिष्ट संस्करण है। बाइनरी ट्री में, प्रत्येक नोड में 2 से अधिक बच्चे नहीं हैं, उनमें से एक को "बाएं सबट्री" कहा जाता है, और दूसरा "राइट सबट्री" है, कोई छंटनी नहीं है। बाइनरी सर्च ट्री में, सभी नोड्स को निम्नलिखित नियम में परिलक्षित क्रम में संग्रहीत किया जाता है:

मान लीजिए कि द्विआधारी खोज ट्री में x एक नोड है, यदि y, x के लिए "बाएं सबट्री" है, तो y.key node x। यदि x के लिए y "राइट सबट्री" है, तो y.key ≥ x.key है।

एक द्विआधारी खोज पेड़ को लागू करना

मेरे द्वारा कार्यान्वित पेड़ के साथ काम करने के लिए वर्ग निम्नानुसार किया जा सकता है:

require "binarytree" tree = BinaryTree.new(40) tree.add(30) tree.add(100) tree.add(20) tree.add(35) tree.add(25) tree.add(34) puts "Tree nodes: #{tree.to_s}" => "20, 25, 30, 34, 35, 40, 100" 

हम इस वर्ग का उपयोग संख्याओं, तारों, या किसी भी देशी रूबी प्रकार के साथ कर सकते हैं जो मिलान का समर्थन करते हैं (अर्थात, <=>)

एक द्विआधारी पेड़ में नोड्स जोड़ना

बाइनरी ट्री में नोड्स जोड़ने का कोड नीचे दिखाया गया है। यह कोड पहले यह देखने के लिए जांचता है कि क्या हमारे पास पहले से ही रूट नोड है, यदि नहीं, तो एक नए मान के साथ रूट नोड बनाएं। यदि हमारे पास पहले से रूट नोड है, तो हम अंतिम नोड तक पहुंचने तक पेड़ के नोड्स (ऊपर बताए गए नियम का उपयोग करके) को स्कैन करते हैं। जैसे ही हम अंतिम नोड पर पहुँचते हैं हम इसे एक नए नोड की ओर इंगित करते हैं।

 def add(new_value) if @root == nil @root = Node.new(new_value) @total_nodes = 1 return end current = @root while(true) if new_value >= current.value if current.right == nil current.right = Node.new(new_value) break else current = current.right end else if current.left == nil current.left = Node.new(new_value) break else current = current.left end end end @total_nodes += 1 end 

लकड़ी चलना

बाइनरी सर्च ट्री के फायदों में से एक यह है कि इसमें संचित मूल्यों को प्राप्त करना बहुत आसान है। इस प्रक्रिया को "एक छंटाई वाले पेड़ पर चलना" कहा जाता है। उदाहरण के लिए, यदि हमारे पास निम्नलिखित मानों के साथ एक पेड़ है: 100, 50, 200 और 150, तो छंटे हुए पेड़ हमें मान देंगे: 50, 100, 150 और 200। पेड़ में चलना एक पुनरावर्ती फ़ंक्शन का उपयोग करके लागू किया जा सकता है। हालांकि, पुनरावर्ती विधि, हालांकि सुरुचिपूर्ण, पेड़ के बड़े होने पर बहुत प्रभावी नहीं है। मेरे द्वारा लागू किया गया कोड पुनरावृत्ति का उपयोग नहीं करता है, बल्कि इसके बजाय नोड्स को ट्रैक करने के लिए एक स्टैक के रूप में एक सरणी का उपयोग करता है। यह समाधान पुनरावृत्ति के रूप में सुरुचिपूर्ण नहीं है, लेकिन पेड़ में हजारों नोड्स होने पर भी यह अच्छी तरह से काम करता है।

 def walk return nil if @root == nil node = @root stack = [] ignore_left = false while(true) #p "processing #{node.value.to_s}" if ignore_left #p "ignoring nodes to the left" ignore_left = false else if node.left != nil #p "moving to the left" stack << node node = node.left next end end yield node if node.right != nil #p "moving to the right" node = node.right next end break if stack.length == 0 #p "popping from the stack" node = stack.pop ignore_left = true end end 

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

 tree.walk { |node| puts "#{node.value}" } 

इस उदाहरण में, ब्लॉक केवल मानों को "प्रदर्शित" करता है, लेकिन हम एक अधिक जटिल उदाहरण देखेंगे जब हम एक बाइनरी ट्री रेंडर करने के लिए कोड पर विचार करते हैं।

बाइनरी ट्री कैसे आकर्षित करें

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

मुख्य एल्गोरिथ्म इस प्रकार है:

• दिए गए निर्देशांक के साथ रूट नोड ड्रा करें
• रूट नोड के बाईं ओर से बाएं सबट्री ड्रा करें
• रूट नोड के दाईं ओर सही सबट्री ड्रा करें

 def draw_node(root, x, y, block) return if root == nil block.call(root, x, y, x, y) draw_left(root.left, x, y, block) if root.left != nil draw_right(root.right, x, y, block) if root.right != nil end 

बाएं सबट्री के निर्देशांक की गणना करने के लिए, हम गणना करते हैं कि कितने बच्चे बाएं सबट्री के दाईं ओर हैं। परिणामी संख्या, हम एक्स अक्ष के साथ नकारात्मक विस्थापन के लिए उपयोग करते हैं। इसके अलावा, हम बाईं और दाईं ओर सबट्री के लिए इस विधि को पुन: कहते हैं।

 def draw_left(node, parent_x, parent_y, block) if node.right != nil count = 1 + children_count(node.right) else count = 0 end x = parent_x - @x_distance - (count*@x_distance) y = parent_y + @y_distance block.call(node.value, x, y, parent_x, parent_y) draw_left(node.left, x, y, block) if node.left != nil draw_right(node.right, x, y, block) if node.right != nil end 

सही उपशीर्षक के लिए, हम एक ही काम करते हैं, लेकिन इसके विपरीत।

 def draw_right(node, parent_x, parent_y, block) if node.left != nil count = 1 + children_count(node.left) else count = 0 end x = parent_x + @x_distance + (count*@x_distance) y = parent_y + @y_distance block.call(node.value,x,y, parent_x, parent_y) draw_left(node.left, x, y, block) if node.left != nil draw_right(node.right, x, y, block) if node.right != nil end 

वॉक विधि की तरह, वास्तव में प्रदान करने का तरीका कुछ भी नहीं खींचता है, लेकिन केवल ऑब्जेक्ट के प्रदर्शन के निर्देशांक को इंगित करता है। निम्न उदाहरण कंसोल में निर्देशांक के साथ एक पेड़ के निर्माण को दर्शाता है:

 require "binarytree" require "binarytreedrawer" tree = BinaryTree.new tree.add(100) tree.add(50) tree.add(150) tree.add(25) tree.add(75) tree.add(125) tree.add(175) drawer = BinaryTreeDrawer.new(tree) drawer.draw(0,0, Proc.new { |value, x, y, px, py| puts "Value #{value} at (#{x}, #{y})" }) => Value 100 at (0, 0) => Value 50 at (-40, 30) => Value 25 at (-60, 60) => Value 75 at (-20, 60) => Value 150 at (40, 30) => Value 125 at (20, 60) => Value 175 at (60, 60) 

एक वेब पेज पर एक बाइनरी ट्री को प्रस्तुत करने का एक वास्तविक उदाहरण

निर्देशांक होने पर, हम किसी भी ग्राफिक्स प्रोग्राम का उपयोग किसी पेड़ को खींचने के लिए कर सकते हैं। इस वेब एप्लिकेशन में मैं ड्राइंग के लिए एक सतह के रूप में HTML 5 कैनवस , और कई जेएस तरीकों का उपयोग करूंगा। निम्नलिखित एक सरल उदाहरण है कि कैसे मैं जेएस कॉल को एक पेड़ बनाने के लिए उत्पन्न करता हूं:

 drawer = BinaryTreeDrawer.new(@tree) drawer.draw(0, 0, Proc.new { |value, x, y, px, py| circles << "draw_circle(centerX + #{x}, offsetY + #{y}, 5);" lines << "draw_line(centerX + #{x}, offsetY + #{y}, centerX + #{px}, offsetY + #{py});" labels << "draw_label(centerX + 7 + #{x}, offsetY+5+#{y}, \"#{value}\");" }) 

ध्यान दें कि यह कोड जावास्क्रिप्ट विधियों के लिए कॉल के साथ बस तीन सरणियाँ (सर्कल, लाइनें, लेबल) बनाता है। इन सरणियों को बाद में एक वेब पेज में डाला जाता है और क्लाइंट साइड पर एक पेड़ बनाया जाता है।

सोर्स कोड और डेमो

यदि आप एक डेमो देखना चाहते हैं, तो आप http://binarytree.heroku.com पर जा सकते हैं और यादृच्छिक डेटा के साथ कुछ बाइनरी ट्री जनरेट कर सकते हैं या अपने स्वयं के डेटासेट के साथ एक बाइनरी ट्री बना सकते हैं।

बाइनरी ट्री के कार्यान्वयन के लिए सभी स्रोत, साथ ही एक डेमो साइट, गिटहब पर पोस्ट की गई है ।