import random
from typing import Optional, cast

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)
        print ()

    @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, end=" ")
        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.
    def _max_node (self) -> Optional [_Node] :
        if self._root is None :
            return None
        return Tree._max_ric_node (self._root)
    
    @staticmethod
    def _max_ric_node (n:_Node) -> _Node:
        # caso base
        if n.right is None :
            return n
        # caso ricorsivo
        return Tree._max_ric_node (n.right)
    
    def max (self) -> Optional [int] :
        n:Optional[_Node] = self._max_node ()
        if n is None : 
            return None
        else :
            return n.v

    # metodo successore: restituisce il NODO contenente il valore 
    # immediatamente più grande a quello associato al nodo
    # passato come parametro
    @staticmethod
    def _successor (n: _Node) -> Optional[_Node] :
        if n.right is not None :
            #caso 1: n ha il figlio destro
            t = Tree()
            t._root = n.right
            return t._min_node()
        i:Optional[_Node] = n.parent
        while i is not None and i.v<n.v :
            i = i.parent
        return i

    # metodo che sostituisce il nodo new (o None) al figlio old
    @staticmethod
    def _change_child (old:_Node, new:Optional[_Node]) -> None:
        if new is not None : new.parent = old.parent
        if old.parent is None : return
        if old.parent.left is old :
            old.parent.left = new
        else :
            old.parent.right = new

    # metodo che rimuove il valore v dall'albero
    def remove (self, v:int) -> None:
        n  = self._search_node(v)
        if n is None : return
        # caso 1: n non ha figli
        if n.left is None and n.right is None :
            Tree._change_child(n, None)
            if n.parent is None : self._root = None # ho cancellato l'unico nodo dell'albero
            return
        #caso 2: n ha un solo figlio
        if (n.left is None and n.right is  not None) \
             or  (n.left is not None and n.right is None):
            unico_figlio = n.right if n.right is not None else n.left
            Tree._change_child (n, unico_figlio)
            if n.parent is None : self._root = unico_figlio
            return
        #caso 3: n ha due figli
        successore = cast (_Node, Tree._successor (n))
        # nota1: il successore NON può essere None!
        # nota2: il successore NON può avere il figlio sinistro!
        Tree._change_child (successore, successore.right)
        n.v = successore.v


    def _search_node (self, v:int) -> Optional[_Node] :
        i = self._root
        while i is not None :
            if v == i.v :
                return i
            elif v>i.v :
                i = i.right
            else :
                i = i.left
        return None

    # 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())
    print ("massimo = ", tree.max())
    print ("Rimuovo 100")
    tree.remove(100)
    tree.inOrderVisit ()

if __name__ == "__main__" :
    _test()