ダブルツリーのバランス検索を実現

# BST           
import BST

'''
      :             
      :
         N:      
'''
def BInsert(N):
    #               
    BST.Insert(N)
    #         ,       height
    N = BST.Find(N, root)
    Rebalancce(N)

'''
      :  AVL       
      :
         N:      
'''
def BDelete(N):
    #                  
    p = N.parent
    BSTDelete(N)
    #          
    Rebalance(p)

'''
      :  x,y       
      :
         (x,y):        
         root:      
'''
def BRangeSearch(x, y, root):
    #                ,                
    T =  BSTRangeSearch(x, y, root)
    return T



'''
      :    N   height
      :  N
'''
def AdjustHeight(N):
    N.height = 1 + max(N.left.height, N.right.height)
    return
'''
      :        
      :           
'''
def Rebalance(N):
    p = N.parent
    #        ,   
    if N.left.height > N.right.height + 1:
        RebalanceRight(N)
    #        ,   
    if N.right.height > N.left.height + 1:
        RebalanceLeft(N)
    #        
    AdjustHeight(N)
    if p != None:

        Rebalance(p)

'''
      :LR     LL   
      :
         N:   
'''
def RebalanceRight(N):
    M = N.left
    # LR   
    if M.right.height > M.left.height:
        #   
        RotateLeft(M)
    #   
    RotateRight(N)

'''
      :RL     RR   
      :
         N:   
'''
def RebalanceLeft(N):
    M = N.right
    # RL   
    if M.left.height > M.right.height:
        #   
        RotateRight(M)

    #   
    RotateLeft(N)


'''
      :  
      :
         N:   
'''
def RotateRight(N):
    # N      M  N
    # N  M      
    # M      B  N    
    p = N.parent
    M = N.left
    B = M.right

    # N      M  N
    M.parent = p
    if p != None:
        if N == N.parent.left:
            N.parent.left = M
        else:
            N.parent.right = M
    # N  M      
    M.right = N
    N.parent = M

    # M      B  N      
    if B != None:
        N.left = B
        B.parent = N
    else:
        N.left = None

    #       (N,M         )
    AdjustHeight(N)
    AdjustHeight(M)

'''
      :  
      :
         N:   
'''
def RotateLeft(N):
    # N      M  N
    # N  M      
    # M      B  N      
    p = N.parent
    M = N.right
    B = M.left

    # M  N  
    M.parent = p
    if p != None:
        if N == p.left:
            p.left = M
        else:
            p.right = M
    # N  M      
    N.parent = M
    M.left = N
    # B  N      
    if B != None:
        B.parent = N
        N.left = B
    else:
        N.left = None
    #   M,N     
    AdjustHeight(N)
    AdjustHeight(M)