AA strom: Porovnání verzí

Základní princip všech vyvážených stromů spočívá v tom, že žádná cesta není výrazně kratší než nejdelší cesta stromu. Tuto vlastnost zajišťujeme v binárních stromech několika způsoby. Například můžeme v každém uzlu uchovávat informaci o vyvážení, třeba rozdíl ve výšce mezi pravým a levým podstromem. Dalším častým principem je použití některých uzlů jako pseudo-uzly, které nám umožní využívat binární strom jako n-ární strom. Pseudo-uzel je pomyslné spojení několika regulárních uzlů do jednoho. Takto získaný pseudo-uzel může nabývat arity více než dva a tvoří vrchol n-árního podstromu. Na tomto principu jsou postaveny i červeno-černé stromy. V notaci červeno-černých stromů se používá černá barva uzlů pro zachycení vertikálních spojení a červená horizontálních.<br/>