পাইথনে O(n) সময়ে BST এবং O(1) স্থানের মধ্যমা খুঁজুন

ধরুন আমাদের বাইনারি সার্চ ট্রি(BST), আমাদের এটির মধ্যক খুঁজে বের করতে হবে। নোডের জোড় সংখ্যার জন্য আমরা জানি, মধ্যমা =((n/2ম নোড + (n+1)/2ম নোড) /2 বিজোড় সংখ্যার নোডের জন্য, মধ্যমা =(n+1)/2ম নোড।

সুতরাং, যদি ইনপুট মত হয়

তাহলে আউটপুট হবে 7

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

রুট যদি None এর মত হয়, তাহলে
- রিটার্ন 0
node_count :=গাছে নোডের সংখ্যা
count_curr :=0
বর্তমান :=রুট
কারেন্ট শূন্য না হলে, করুন
- যদি current.left null, তারপর
  - count_curr :=count_curr + 1
  - যদি node_count mod 2 0 না হয় এবং count_curr একই (node_count + 1) /2 হয়, তাহলে
    - আগের ডেটা ফেরত দিন
  - অন্যথায় যখন node_count mod 2 0 হয় এবং count_curr (node_count/2) +1 এর মত হয়, তখন
    - রিটার্ন(previous.data + current.data) /2
  - পূর্ববর্তী :=বর্তমান
  - বর্তমান :=বর্তমান। ডান
- অন্যথায়,
  - আগের :=current.left
  - যদিও previous.right নাল নয় এবং previous.right বর্তমানের মতো নয়, করুন
    - আগের :=আগের. ডান
  - পূর্ববর্তী ডান যদি শূন্য হয়, তাহলে
    - previous.right :=বর্তমান
    - বর্তমান :=current.left
  - অন্যথায়,
    - previous.right :=কোনটিই নয়
    - পূর্ববর্তী :=পূর্ববর্তী
    - count_curr :=count_curr + 1
    - যদি node_count mod 2 0 না হয় এবং count_curr একই হয় (node_count + 1) / 2, তাহলে
      - বর্তমান ডেটা ফেরত দিন
    - অন্যথায় যখন node_count mod 2 0 হয় এবং count_curr একই (node_count / 2) + 1 হয়, তখন
      - রিটার্ন (previous.data+current.data) /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)