# ADS úlohy D - Merge

Nejprve vezmu případ, kdy jsou oba stromy stejně velké ($|A|=|B|$) a dokonale vyvážené ($A$ obsahuje menší prvky).

Mohu najít nejmenší prvek z $B$ (nebo největší z $A$) a pod něj zavěsit oba stromy (kořen $A$ nalevo, kořen $B$ napravo). Tím mi v nejlevějším vrcholu v $B$ vznikne "jen" $+1$ nevyváženost, která nevadí.

Pokud by mi na začátku v poslední hladině v $B$ chyběl ještě jeden vrchol, musel bych po odstranění nejmenšího vrcholu provádět operace jako např. změna syna, rotace... Všechny tyto operace však pro AVL strom dokážu dělat v logaritmickém čase.

Jsou-li stromy různě velké, budu menší strom (vzhledem k počtu hladin) zapojovat do většího.

*Dále již budu předpokládat, že menší strom obsahuje i menší prvky.*

Kořen má zpravidla již dva syny, takže musím nejprve změnit strukturu menšího stromu. Shodně s příkladem výše, obsahuje-li menší strom i menší prvky, přepojím nejpravější (jakožto největší) prvek, udělám z něj kořen, a levým synem bude původní kořen.

V $B$ musím najít vrchol, který je kořenem podstromu se stejnou výškou (rsp. o 1 větší) než, jakou má $A$. Mohu se sice pohybovat jen směrem doleva (neboť kořen $A$ je menší než jakýkoli prvek z $B$), ale určitě takový podstrom najdu, jelikož AVL má omezení na maximální hloubku (levý podstrom může být maximálně o 1 mělčí než pravý).

Kořen $x$ tohoto podstromu (z pohledu vizualizace) posunu dolů a doprava, a na jeho původní místo umístím kořen $A$.

## Algoritmus:

Je-li h(A)<h(B):
1. v = nejpravější vrchol v A
2. Odstraň v a vyvaž A.
3. levý syn v = kořen A
4. Ve stromu B vyber kořen x a zkontroluj největší hloubku podstromu.
5. Dokud hloubka podstromu $\neq$ hloubka A+1: x = levý syn x
6. Pravý syn v = x
7. Levý syn otce x = v
8. Z hloubky A a podstromu x zjistím balance-faktor pro vrchol v.
9. Provedu příslušné rotace a propagaci balance-faktoru.
10. Výstup: Nový AVL strom.

## Správnost:

Výsledkem je BVS: Vyplývá z rozboru.
Tento strom je AVL: Strom X má hloubku nejvýše o 1 víc, než A. Operací zasazení tak hloubka levého podstromu (s původním kořenem x) se nezměnila, ovšem hloubka pravého podstromu se zvýšila o 1. V AVL stromu je maximální povolený rozdíl +1, nyní však takový rozdíl může být +2. Ten se však odstranit dá.

## Složitost:

Hledání nejlevějšího/nejpravějšího vrcholu trvá $\log n$ operací, stejně tak odstranění a vyvažování a hledání největší hloubky (což mi stačí jednou, zbytek vyřeší balance-faktor). Celkem je tak složitost $O(\log |(V(B))|)$.