# 자식이 몇명인지 세어줌
def countChildren(self):
    count = 0
    if self.left:
        count += 1
    if self.right:
        count += 1
    return count
 
 
 def delect(self, key):
  node, parent = self.lookup(key)
  
  if node:
      nChildren = node.countChildren()
      
      # leaf 노드 삭제(자식이 이무것도 없는 경우)
      if nChildren == 0:
            # 지울 node 가 그 parent의 왼쪽 자식인지 오른쪽 자식인지 판단하여
            # leaf node 였던 자식의 parent= null으로 바꿔 자식을 끊어낸다
            if parent:
                if node == parent.right:
                    parent.right = None
                if node == parent.left:
                    parent.left = None
            # 지워야 할 노드가 root 인 경우(예외처리)
            else:
                self.root = None
      
      #######################################################################
      # single child를 갖은 노드 삭제
      elif nChildren == 1:
           # 하나 있는 자식이 왼쪽인지 오른쪽인지를 판단하여
           # 그 자식을 displace가 가리키도록 함
           if node.left:
                displace = node.left
           else:
                displace = node.right
            
           # node의 parent를 통해 node가 parent의 왼쪽 자식인지 오른쪽 자식인지 판단하여
           # node의 child(displace)을 node 의 자리에 넣음
           # 즉 parent-node-child
           # -> parent-child
           if parent:
                if node == parent.right:
                    parent.right = displace
                else:
                    parent.left = displace
            # node 는 root 인 경우 예외처리
            else:
                self.root = displace
        
        
        ####################################################
        # 이해를 돕기 위해 위의 예를 그대로 사용했습니다 그림과 대조하면서 읽어보세요
        # two child를 갖은 노드 삭제 [soultion 1]
        else:
            # parent = 41
            parent = node
            
            # 노드의 오른쪽에서 가장 작은 노드를 찾아야함
            # successor은 노드의 오른쪽 (65)
            successor = node.right
            
            # 이제 successor중 가장 작은 값(왼쪽노드or 왼쪽노드가 없으면 자기자신)을 찾아야함
            # while문이 종료되었을때, 
            # successor 는 바로 다음 키를 가진 노드를
            # 그리고 parent 는 그 노드의 부모 노드를 가리키게함
            # 계속 왼쪽으로 감
            while successor.left: # successor.left= 50
                parent = successor # parent = 65
                successor = successor.left  # successor= 50
            
            # 삭제하려는 노드인 node 에 successor 의 key 와 data 를 대입
            node.key = successor.key
            node.data = successor.data
            
            # 이제, successor 가 parent 의 왼쪽 자식인지 오른쪽 자식인지를 판단하여
            # 그에 따라 parent.left 또는 parent.right 를
            # successor 가 가지고 있던 (없을 수도 있지만) 자식을 가리키도록 함  
                if successor.key is parent.left.key:
                    parent.left = successor.right
                else:
                    parent.right = successor.right
                    
            return True
                

        else:
            return False

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

class tree:
    def __init__(self, root):
        self.root = root

    def insert(self, value):
        self.current_node = self.root
        while True:
            if value < self.current_node.value:
                if self.current_node.left != None:
                    self.current_node = self.current_node.left
                else:
                    self.current_node.left = Node(value)
                    break
            else:
                if self.current_node.right != None:
                    self.current_node = self.current_node.right
                else:
                    self.current_node.right = Node(value)
                    break
      ############
      # 이곳에 delect 함수 

tree.insert(41);
tree.insert(20);
tree.insert(11);
tree.insert(29);
tree.insert(32);
tree.insert(65);
tree.insert(50);
tree.insert(91);
tree.insert(72);
tree.insert(99);
// 지우는 법
tree.delete(72);