Qual è la complessità del tempo del miglior caso per inserire un nuovo nodo in un BST di livello minimo con n nodi?

Question

Sto imparando sulla complessità di algo e sulla complessità del tempo di calcolo del calcolo.La domanda è

Qual è la complessità del tempo del miglior caso per inserire un nuovo nodo in a BST di livello minimo con n nodi?Spiegare.(Suggerimento: puoi disegnare un diagramma come parte del tuo Soluzione.)

Puoi per favore spiegare in dettaglio come risolveresti questa domanda e domande simili?

Il mio tentativo:

Per la complessità del tempo abbiamo 2 domande, quante volte e cosa costa.

Quante volte: Ci sarà un elemento da controllare SO=> O (1) quanto costa? quante volte?

Ora sono bloccato qui (abbastanza presto), suppongo che dal suo albero un albero, ci saranno n / 2 elementi dopo il primo confronto e continua a dividere la metà.

Answer 1

Considerare il seguente BST minimo-altezza (qualsiasi albero binario con nodi 8 ha almeno 4 livelli, quindi ha l'altezza minima).

         8
        / 
       4
     /   \
    2     6
   / \   / \
  1   3 5   7

.

Ora diciamo che inserisci il valore 9, andrà dritto sul lato destro della radice.

Per generalizzare questo esempio: un BST che ha un figlio destro o un figlio sinistro che sono completi alberi - è un'altezza minima BST.Se l'altro lato è vuoto, qualsiasi valore che inserirai quale sarà maggiore \ minore al nodo verrà aggiunto direttamente al bambino destro della radice.In questo caso l'inserto prenderà il tempo O(1).