Python에서 O(n) 시간과 O(1) 공간에서 BST의 중앙값 찾기

BST(Binary Search Tree)가 있다고 가정하고 중앙값을 찾아야 합니다. 노드 수가 짝수인 경우 중앙값 =((n/2번째 노드 + (n+1)/2번째 노드) /2 노드가 홀수인 경우 중앙값 =(n+1)/2번째 노드

따라서 입력이 다음과 같으면

그러면 출력은 7이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• 루트가 None과 같으면

  • 0 반환

• node_count :=트리의 노드 수

• count_curr :=0

• 현재 :=루트

• 현재가 null이 아닌 동안 수행

  • 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과 같으면

      • 반환(이전.데이터 + 현재.데이터) /2

    • 이전 :=현재

    • 현재 :=current.right

  • 그렇지 않으면

    • 이전 :=현재.왼쪽

    • 이전.right가 null이 아니고 이전.right가 현재와 같지 않은 동안 수행

      • 이전 :=이전.오른쪽

    • 이전.right가 null이면

      • 이전.오른쪽 :=현재

      • 현재 :=현재.왼쪽

    • 그렇지 않으면

      • 이전.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과 같으면

        • 반환(이전.데이터+현재.데이터) /2

      • 이전 :=현재

      • 현재 :=current.right

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

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