ค้นหาค่ามัธยฐานของ BST ในเวลา O (n) และช่องว่าง O (1) ใน Python

สมมติว่าเรามี Binary Search Tree(BST) เราต้องหาค่ามัธยฐานของมัน เราทราบจำนวนโหนดเป็นคู่ ค่ามัธยฐาน =((โหนด n/2 + (n+1)/2 โหนด) /2 สำหรับโหนดจำนวนคี่ ค่ามัธยฐาน =(n+)/2 โหนด

ดังนั้นหากอินพุตเป็นแบบ

แล้วผลลัพธ์จะเป็น 7

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• หากรูทเหมือนกับไม่มีแล้ว

  • คืนค่า 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

    • ถ้า Previous.right เป็นโมฆะ

      • Previous.right :=ปัจจุบัน

      • ปัจจุบัน :=ปัจจุบันซ้าย

    • มิฉะนั้น

      • Previous.right :=ไม่มี

      • ก่อนหน้า :=ก่อนหน้า

      • count_curr :=count_curr + 1

      • หาก node_count mod 2 ไม่ใช่ 0 และ count_curr เหมือนกับ (node_count + 1) / 2 ดังนั้น

        • คืนค่า current.data

      • มิฉะนั้นเมื่อ 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)

ผลลัพธ์

7