from __future__ import annotations
from typing import cast
import random

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


class ABR :
    def __init__(self):
        self._root:_Node|None = None
    
    # metodo che inserisce uun valore nell'albero.
    # non è possibile inserire valori già presenti
    # restituisce True se l'inserimento è effettuato
    #             False se il valore è già presente
    def insert (self, v:int) -> bool:
        #creare il nuovo nodo
        nuovo:_Node = _Node (v)
        #individuare il nodo padre di nuovo
        precedente: _Node|None = None
        i: _Node|None= 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
        if precedente is None:
            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 in_order_visit (self) :
        ABR._in_order_visit_node (self._root)
        print ()

    @staticmethod
    def _in_order_visit_node (u:_Node|None) :
        # caso base : il nodo non esiste
        if u is None :
            return
        # caso ricorsivo
        ABR._in_order_visit_node (u.left)
        print (u.v, end=" ")
        ABR._in_order_visit_node (u.right)

    def __str__ (self) ->str :
        return ABR._node_to_str (self._root)
    
    @staticmethod
    def _node_to_str (u:_Node|None) -> str:
        # caso base : il nodo non esiste
        if u is None :
            return ""
        # caso ricorsivo
        return f"{ABR._node_to_str (u.left)}{u.v} {ABR._node_to_str (u.right)}"

    
    def search_ric (self, v:int) -> bool:
        return ABR._search_ric_node (self._root, v)

    @staticmethod
    def _search_ric_node (u:_Node|None, v:int) -> bool:
        #casi base
        if u is None :
            return False
        if u.v == v :
            return True
        # caso ricorsivo
        if v>u.v :
            return ABR._search_ric_node (u.right, v)
        else :
            return ABR._search_ric_node (u.left, v)
        
    # scrivere un metodo che calcola l'altezza di un ABR, con
    # la convenzione che un albero vuoto ha altezza 0 e
    # un albero composto solo dalla radice altezza 1
    @property
    def heigth (self) -> int :
        return ABR._height_node(self._root)
    
    @staticmethod
    def _height_node (u:_Node|None) -> int:
        #caso base
        if u is None :
            return 0
        #caso ricorsivo
        return 1 + max(ABR._height_node(u.left), 
                       ABR._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) -> ABR:
        t = cls()
        for _ in range (n) :
            t.insert (random.randint(0, max))
        return t
    
    # scrivere un metodo PRIVATO _min_node che restituisce il riferimento
    # al nodo contenente la chiave più piccola
    def _min_node (self) -> _Node|None :
        if self._root is None:
            return None
        i:_Node = self._root
        while i.left is not None :
            i = i.left
        return i
        '''
        i:_Node|None = self._root
        precedente:_Node|None = None
        while i is not None:
            precedente=i
            i = i.left
        return precedente
        '''

    def min (self) -> int|None:
        n:_Node|None = self._min_node()
        if n is None:
            return None
        else:
            return n.v
        
    # esercizio: implementare max e _max_node in modo ricorsivo.
    def _max_node (self) -> _Node|None :
        if self._root is None :
            return None
        return ABR._max_ric_node (self._root)
    
    @staticmethod
    def _max_ric_node (n:_Node) -> _Node:
        # caso base
        if n.right is None:
            return n
        # caso ricorsivo
        else:
            return ABR._max_ric_node(n.right)

    def max (self) -> int|None:
        n:_Node|None = 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) -> _Node|None :
        if n.right is not None:
            #caso 1: n ha il figlio destro
            t = ABR()
            t._root = n.right
            return t._min_node()
        else:
            #caso 2: n NON ha il figlio destro
            i:_Node|None = 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 nodo old
    @staticmethod
    def _change_child (old:_Node, new:_Node|None) -> 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:
        # prima cosa: bisogna individuare il nodo contenente v
        i = self._root
        while i is not None and v != i.v :
            if v>i.v :
                i = i.right
            else :
                i = i.left
        if i is None : #v non è presente nell'albero
            return 
        # ora i si riferisce al nodo da cancellare
        # caso 1: i non ha figli
        if i.left is None and i.right is None :
            ABR._change_child(i, None)
            if i.parent is None : 
                self._root = None # ho cancellato l'unico nodo dell'albero
            return
        # caso 2: i ha solo un figlio
        if (i.left is None and i.right is  not None) \
             or  (i.left is not None and i.right is None):
            unico_figlio = i.right if i.right is not None else i.left
            ABR._change_child (i, unico_figlio)
            if i.parent is None : 
                self._root = unico_figlio
            return
        #caso 3: n ha due figli
        successore = cast(_Node, ABR._successor (i))
        # nota1: il successore NON può essere None!
        # nota2: il successore NON può avere il figlio sinistro!
        ABR._change_child (successore, successore.right)
        i.v = successore.v




def test():
    tree = ABR()

    for _ in range(10):
        v = random.randint(0,1000)
        if not tree.insert(v):
            print (f"valore {v} duplicato")

    tree.insert (40)

    for _ in range(10):
        v = random.randint(0,1000)
        if not tree.insert(v):
            print (f"valore {v} duplicato")

    print(tree)
    print(tree.heigth)
    tree.remove(40)
    print(tree)
    print(tree.heigth)

# 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 = ABR.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, 10000000, 50)
test()