# ricerca binaria in array ordinato

def ricb(x,lista):
    if lista==[]: return False
    k=len(lista)//2
    if lista[k]==x: return True
    if lista[k]>x: return ricb(x,lista[:k])
    return ricb(x,lista[k+1:])

# >>> lista=[2,4,6,8,10]
# >>> ricb(3,lista)
# False
# >>> ricb(4,lista)
# True

def ric(x,lista):
    return ricb1(x,lista,0,len(lista))

def ricb1(x,lista,i,j):
    if i>j: return False
    k=(i+j)//2
    if lista[k]==x: return True
    if lista[k]>x: return ricb1(x, lista, i, k-1)
    return ricb1(x,lista, k+1, j)
    

>>> ric(3,[2,4,6,8,10])
False
>>> ric(4,[2,4,6,8,10])
True


####################################################
# un albero binario di ricerca ha nodi chiavi intere distinte 
# e ciascun nodo ha al piu' due figli con  la proprieta' che 
# le chiavi del  sottoalbero sinistro 
# sono inferiori alla chiave della radice che 
# e' inferiore alle chiavi nel sottoalbero destro. 

class NodoAB:
    def __init__(self,val):
        self.v=val
        self.sx=None
        self.dx=None

def crea(lista):
    '''data la lista di interi crea un albero binario di ricerca 
    che contiene quegli interi.'''
    r=None
    for x in lista:
        r=add(r,x)
    return r
    
               
def add(r,x):
    if r==None: return NodoA(x)
    if r.v==x: return r
    if r.v>x: 
        r.sx=add(r.sx,x)
    else:
        r.dx= add(r.dx,x)
    return r
    
########################################################
    
def stampa(r,liv=0):
    print('|  '*liv +str(r.v))
    if r.sx: stampa( r.sx,liv+1)
    if r.dx: stampa( r.dx,liv+1)

# >>> stampa(crea([1,2,3,4,5]))    
# 1
# |  2
# |  |  3
# |  |  |  4
# |  |  |  |  5

# >>> stampa(crea([5,4,3,2,1])) 
# 5
# |  4
# |  |  3
# |  |  |  2
# |  |  |  |  1

#>>> stampa(crea([4,2,6,5,7,2,3,1]))
#4
#|  2
#|  |  1
#|  |  3
#|  6
#|  |  5
#|  |  7

######################################################

def alt(r):
    '''restituisce l'altezza dell'albero binario'''
    if r==None or (r.sx==None and r.dx==None): return 0
    return max(alt(r.sx),alt(r.dx))+1
    
def esperimento(n,k):
    '''crea k alberi a partire da lista di n elementi dati 
    in modo casuale e alla fine da l'altezza media degli 
    n alberi'''
    from random import sample,seed
    seed(0)
    media=0
    for i in range(k):
         lista=sample(range(n),n)
         r=crea(lista)
         media+=alt(r)
    return media/k
    
# >>> esperimento(1024,10)
# 20.8
# >>> esperimento(1024,20)
# 20.8
# >>> esperimento(2**15,20) #2**15=32768
# 34.4 
# >>> esperimento(2**20,10) #2**20=1048576
#49.5


####################################################### 

def cerca(r,x):
    ''' cerca l'intero x nell'albero binario di ricerca, restituisce 
    True se l'elemento e' presente, False altrimenti'''
    if r==None: return False
    if r.v==x: return True
    if r.v> x: return cerca(r.sx,x)
    return cerca(r.dx,x)

def cercaMax(r):
    #cerca elemento massimo in insieme non vuoto
    if r==None: 
        print("l'albero e' vuoto")
    elif r.dx==None: 
        print(r.v)
    else: cercaMax(r.dx)
 
# >>> cercaMax(r)
# 5
     
#######################################################