import random
from typing import Optional

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

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

    def insert (self, v:int) -> bool:
        # creazione nuovo nodo
        nuovo = _Node(v)
        # individuazione del nodo padre del nuovo nodo
        precedente = None
        i = 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 height (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 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) :
        t  = cls ()
        for _ in range (n) :
            t.insert (random.randint(0,max))
        return t
    
    # 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.
       


# 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.height()
        media_h = somma_h / trials
        print (f"n = {n}; h_media = {media_h}")
        n *= 2

test_altezza_media_abr(100000,1000000,20)

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

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

    print ("Visita in ordine: ")
    t.inOrderVisit ()
    print (t.searchRic(20))
    print (t.searchRic(5))

_test()