Optimální vyhledávací stromy II

Vylepšete složitost vašeho algoritmu z předchozí úlohy s pomocí následujícího hintu:

Mějme nějaký optimální vyhledávací strom pro prvky a₁ < … < a_n a jejich četnosti w₁, …, w_n a nechť v jeho kořeni je prvek a_k. Přidáme-li nový prvek a_n+1 větší než všechny ostatní s četností w_n+1, kořen optimálního vyhledávacího stromu se neposune doleva. Přesněji, bude existovat alespoň jeden optimální vyhledávací strom s kořenem a_j pro j ≥ k. Symetrické tvrzení platí pro přidání prvku a₀ na začátek.