import random
from typing import Optional

class _Node :
    def __init__(self, v:int):
        self.v = v
        self.left:Optional[_Node] = None
        self.right:Optional[_Node] = None
        self.parent:Optional[_Node] = None  #riferimento al nodo padre

class Tree :
    def __init__(self):
        self._root:Optional[_Node] = None

    def insert (self, v:int) -> bool:
        # creazione nuovo nodo
        nuovo:_Node = _Node(v)
        # individuazione del nodo padre del nuovo nodo
        precedente: Optional[_Node] = None
        i: Optional [_Node]= self._root
        while i is not None :
            precedente = i
            # impediamo l'inserimento di un valore già presente
            if v==i.v :
                return False
            if v>i.v :
                i = i.right
            else :
                i = i.left
        # inserisco il nodo nell'albero al punto
        # opportuno
        if precedente is None :
            # inserimento primo nodo (radice)
            self._root = nuovo
        else :
            if v>precedente.v :
                precedente.right = nuovo
            else :
                precedente.left = nuovo
        nuovo.parent = precedente
        return True

    def search (self, v:int) -> bool :
        i = self._root
        while i is not None :
            if v == i.v :
                return True
            elif v>i.v :
                i = i.right
            else :
                i = i.left
        return False

    def inOrderVisit (self) :
        Tree._inOrderVisitNode (self._root)

    @staticmethod
    def _inOrderVisitNode (u:Optional[_Node]) :
        # caso base : il nodo non esiste
        if u is None :
            return
        # caso ricorsivo
        Tree._inOrderVisitNode (u.left)
        print (u.v)
        Tree._inOrderVisitNode (u.right)

    def searchRic (self, v:int) -> bool:
        return Tree._searchRicNode (self._root, v)

    @staticmethod
    def _searchRicNode (u:Optional[_Node], v:int) -> bool:
        #casi base
        if u is None :
            return False
        if u.v == v :
            return True
        # caso ricorsivo
        if v>u.v :
            return Tree._searchRicNode (u.right, v)
        else :
            return Tree._searchRicNode (u.left, v)
        
    def heigth (self) -> int :
        return Tree._height_node(self._root)
    
    @staticmethod
    def _height_node (u:Optional[_Node]) -> int:
        #caso base
        if u is None :
            return 0
        #caso ricorsivo
        return 1 + max(Tree._height_node(u.left), Tree._height_node(u.right))
    
    # scrivere un metodo che restituisce il minimo valore presente nell'ABR
    def min (self) -> Optional[int] :
        if self._root is None :
            return None
        i:_Node = self._root
        while i.left is not None :
            i = i.left
        return i.v
    
    def _min_node (self) -> Optional[_Node] :
        if self._root is None :
            return None
        i:_Node = self._root
        while i.left is not None :
            i = i.left
        return i
    
    # esercizio: implementare max e _max_node in modo ricorsivo.
    


    # scrivere un metodo che crea un ABR con n nodi, le cui chiavi sono comprese
    # tra 0 e max 
    @classmethod
    def crea_random_tree (cls, n:int, max: int) -> "Tree":
        t:Tree = Tree()
        for _ in range (n) :
            t.insert (random.randint(0, max))
        return t
    

# n_max è il numero massimo di nodi dell'albero più grande considerato
# v_max è il valore massimo che può presente negli alberi
# trails è il numero di tentativi su cui faccio la media
def test_altezza_media_abr (n_max:int, v_max:int, trials:int) :
    n = 2
    while n<=n_max :
        somma_h = 0
        for _ in range (trials) :
            t = Tree.crea_random_tree (n, v_max)
            somma_h += t.heigth()
        media_h = somma_h / trials 
        print (f"n = {n}; hMedia = {media_h}")
        n *= 2
    
#test_altezza_media_abr (100000, 1000000, 20)

def _test () :
    tree = Tree()
    tree.insert (10)
    tree.insert (20)
    tree.insert (4)
    tree.insert (100)
    tree.insert (30)
    print (tree.search(20))
    print (tree.search(25))
    print ("Visita in ordine: ")
    tree.inOrderVisit ()

    print ("Elementi casuali: ")
    for _ in range (0,10) : 
        v = random.randint(10, 200)
        print (v)
        tree.insert (v)

    print ("Visita in ordine: ")
    tree.inOrderVisit ()

    print (tree.searchRic(20))
    print (tree.searchRic(5))
    print ("minimo = ", tree.min())

_test()