import random
from typing import Optional, cast

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 _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

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

    '''
    @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)
    '''

    # metodo successore: restituisce il NODO contenente il valore 
    # immediatamente più grande di 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()
        #caso 2
        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) con tutto il suo sottoalbero
    # 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 :
            Tree._change_child (n, n.right)
            if n.parent is None : self._root = n.right
            return
        if n.right is None :
            Tree._change_child (n, n.left)
            if n.parent is None : self._root = n.left
            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

            

# 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))
    print ("minimo = ", t.min())
    print ("massimo = ", t.max())
    #testiamo il metodo successore, cercando il successore del nodo che contiene 100
    # print (Tree._successor(t._search_node(100)).v) 
    print ("Rimuovo 100")
    t.remove(100)
    t.inOrderVisit ()

if __name__ == "__main__" :
    _test()