学步园

>>算法导论P217

def Optimal_BST(p,q,n):
    e=[[0 for col in range(n+1)]for row in range(n+2)] #期望代价
    w=[[0 for col in range(n+1)]for row in range(n+2)] #概率总和
    root=[[0 for col in range(n+1)]for row in range(n+2)] #根节点
    for i in range(1,n+2):
        e[i][i-1]=q[i-1]
        w[i][i-1]=q[i-1]
    for L in range(1,n+1):
        for i in range(n-L+2):
            j=i+L-1
            e[i][j]=float('inf')
            w[i][j]=w[i][j-1]+p[j]+q[j]
            for r in range(i,j+1): #可用Knuth结果改进算法复杂度
                t=e[i][r-1]+e[r+1][j]+w[i][j]
                if t<e[i][j]:
                    e[i][j]=t
                    root[i][j]=r
                    
    Construct_Optimal_BST(root,1,n,n,0)
    return 0
        
    
    
   
def Construct_Optimal_BST(root,i,j,n,count):
    count+=1
    if count>(2*n+1):
        return 
    if i==1 and j==n:
        print('K'+str(root[i][j])+' is the root')
    if i<j:
        if root[i][root[i][j]-1]>0 :
            print('K'+str(root[i][root[i][j]-1])+' is the left child of K'+str(root[i][j]))
        Construct_Optimal_BST(root,i,root[i][j]-1,n,count)
        if root[root[i][j]+1][j]>0 :
            print('K'+str(root[root[i][j]+1][j])+' is the right child of K'+str(root[i][j]))
        Construct_Optimal_BST(root,root[i][j]+1,j,n,count)
    if i==j:
        print('d'+str(i-1)+' is the left child of K'+str(i))
        print('d'+str(i)+' is the right child of K'+str(i))
    if i>j:
        print('d'+str(j)+' is the right child of K'+str(j))
        
    

#test
p=[0,0.15,0.1,0.05,0.1,0.2]
q=[0.05,0.1,0.05,0.05,0.05,0.1]
n=len(p)-1
Optimal_BST(p,q,n)