BST에서 k 번째로 작은 노드를 찾는 방법은 무엇입니까?

Question

나는 어제 비슷한 질문을했지만, 원래 질문에 게시 된 것과 다른 해결책을 찾았습니다. 새 코드로 다시 게시하고 있습니다. 각 노드의 오른쪽 및 왼쪽 자식 수를 추적하지 않습니다. 이 코드는 경우에 따라 정상적으로 작동하지만 6 번째로 작은 요소를 찾은 경우 실패합니다. 문제는 내가 어떻게 든 나무 아래로 많은 수의 아이들을 태울 필요가 있다는 것이다. 예를 들어, 노드 5의 경우, 노드 4의 계급 이상으로 캐리해야하며이를 수행 할 수 없습니다.

이것은 숙제가 아니기 때문에 인터뷰 준비 중입니다. 이것은 고전적인 질문 중 하나이며 해결할 수 없습니다.

class Node: 
    """docstring for Node""" 
    def __init__(self, data): 
     self.data = data 
     self.left = None 
     self.right = None 
     self.numLeftChildren = 0 
     self.numRightChildren = 0 


class BSTree: 
    def __init__(self): 
     # initializes the root member 
     self.root = None 

    def addNode(self, data): 
     # creates a new node and returns it 
     return Node(data) 

    def insert(self, root, data): 
     # inserts a new data 
     if root == None: 
      # it there isn't any data 
      # adds it and returns 
      return self.addNode(data) 
     else: 
      # enters into the tree 
      if data <= root.data: 
       root.numLeftChildren += 1 
       # if the data is less than the stored one 
       # goes into the left-sub-tree 
       root.left = self.insert(root.left, data) 
      else: 
       # processes the right-sub-tree 
       root.numRightChildren += 1 
       root.right = self.insert(root.right, data) 
      return root 

    def getRankOfNumber(self, root, x, rank): 
     if root == None: 
      return 0 
     if rank == x: 
      return root.data 
     else: 
      if x > rank: 
       return self.getRankOfNumber(root.right, x, rank+1+root.right.numLeftChildren) 
      if x <= rank: 
       return self.getRankOfNumber(root.left, x, root.left.numLeftChildren+1) 


# main 
btree = BSTree() 
root = btree.addNode(13) 
btree.insert(root, 3) 
btree.insert(root, 14) 
btree.insert(root, 1) 
btree.insert(root, 4) 
btree.insert(root, 18) 
btree.insert(root, 2) 
btree.insert(root, 12) 
btree.insert(root, 10) 
btree.insert(root, 5) 
btree.insert(root, 11) 
btree.insert(root, 8) 
btree.insert(root, 7) 
btree.insert(root, 9) 
btree.insert(root, 6) 

print btree.getRankOfNumber(root, 8, rank=root.numLeftChildren+1) 

Answer 1

노드 등급이 있습니다. 왼쪽 또는 오른쪽 자식의 순위를 찾아야합니다. 노드와 그 자식 사이에 몇 개의 노드가 있습니까?

 a 
    /\ 
/ \ 
    b  c 
/\ /\ 
W X Y Z 

다음은 BST의 예입니다. 소문자는 노드입니다. 대문자는 하위 트리입니다. a과 b 사이의 노드 수는 X의 노드 수입니다. a과 c 사이의 노드 수는 Y의 노드 수입니다. 따라서 b 또는 c의 순위를 a의 순위와 X 또는 Y의 크기에서 계산할 수 있습니다.

rank(b) == rank(a) - size(X) - 1 
rank(c) == rank(a) + size(Y) + 1 

당신은 c 공식하지만 잘못된 b 공식을했다.