पायथन में O(n) समय और O(1) स्थान में BST का माध्यिका ज्ञात कीजिए

मान लीजिए कि हमारे पास बाइनरी सर्च ट्री (BST) है, तो हमें इसका माध्यिका ज्ञात करना होगा। हम नोड्स की सम संख्या के लिए जानते हैं, माध्यिका =((n/2th नोड + (n+1)/2th नोड) /2 विषम संख्या में नोड्स के लिए, माध्यिका =(n+1)/2th नोड।

तो, अगर इनपुट पसंद है

तो आउटपुट 7

. होगा

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

अगर रूट कोई नहीं के समान है, तो
- वापसी 0
node_count :=पेड़ में नोड्स की संख्या
count_curr :=0
वर्तमान:=जड़
जबकि करंट शून्य नहीं है, करें
- अगर current.left null, तो
  - count_curr :=count_curr + 1
  - अगर node_count mod 2 0 नहीं है और count_curr (नोड_काउंट + 1) /2 के समान है, तो
    - पिछला.डेटा लौटाएं
  - अन्यथा जब नोड_काउंट मॉड 2 0 है और count_curr वही है (नोड_काउंट/2) +1, तब
    - वापसी (पिछला.डेटा + करंट.डेटा) /2
  - पिछला:=वर्तमान
  - करंट:=करंट। राइट
- अन्यथा,
  - पिछला:=वर्तमान.बाएं
  - जबकि पिछला.राइट शून्य नहीं है और पिछला.राइट वर्तमान के समान नहीं है, करें
    - पिछला:=पिछला.दाएं
  - अगर पिछला.दायाँ शून्य है, तो
    - पिछला.दायाँ:=वर्तमान
    - वर्तमान:=वर्तमान.बाएं
  - अन्यथा,
    - पिछला.दाएं:=कोई नहीं
    - पिछला:=पिछला
    - count_curr :=count_curr + 1
    - अगर node_count mod 2 0 नहीं है और count_curr (नोड_काउंट + 1) / 2 के समान है, तो
      - वर्तमान.डेटा लौटाएं
    - अन्यथा जब नोड_काउंट मॉड 2 0 है और count_curr वही है (नोड_काउंट / 2) + 1, तब
      - वापसी (पिछला.डेटा+वर्तमान.डेटा)/2
    - पिछला:=वर्तमान
    - करंट:=करंट। राइट

उदाहरण

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

class TreeNode:
   def __init__(self, data):
      self.data = data
      self.left = None
      self.right = None
def number_of_nodes(root):
   node_count = 0
   if (root == None):
      return node_count
   current = root
   while (current != None):
      if (current.left == None):
         node_count+=1
         current = current.right
      else:
         previous = current.left
         while (previous.right != None and previous.right != current):
            previous = previous.right
         if(previous.right == None):
            previous.right = current
            current = current.left
         else:
            previous.right = None
            node_count += 1
            current = current.right
   return node_count
def calculate_median(root):
   if (root == None):
      return 0
   node_count = number_of_nodes(root)
   count_curr = 0
   current = root
   while (current != None):
      if (current.left == None):
         count_curr += 1
         if (node_count % 2 != 0 and count_curr == (node_count + 1)//2):
            return previous.data
         elif (node_count % 2 == 0 and count_curr == (node_count//2)+1):
            return (previous.data + current.data)//2
         previous = current
         current = current.right
      else:
         previous = current.left
         while (previous.right != None and previous.right != current):
            previous = previous.right
         if (previous.right == None):
            previous.right = current
            current = current.left
         else:
            previous.right = None
            previous = previous
            count_curr+= 1
            if (node_count % 2 != 0 and count_curr == (node_count + 1) // 2 ):
               return current.data
            elif (node_count%2 == 0 and count_curr == (node_count // 2) + 1):
               return (previous.data+current.data)//2
            previous = current
            current = current.right
root = TreeNode(7)
root.left = TreeNode(4)
root.right = TreeNode(9)
root.left.left = TreeNode(2)
root.left.right = TreeNode(5)
root.right.left = TreeNode(8)
root.right.right = TreeNode(10)
print(calculate_median(root))

इनपुट

root = TreeNode(7)
root.left = TreeNode(4)
root.right = TreeNode(9)
root.left.left = TreeNode(2)
root.left.right = TreeNode(5)
root.right.left = TreeNode(8)
root.right.right = TreeNode(10)