操作における最悪時間計算量は、o記法でformula_1(formula_5は木の要素数)、平均では、formula_1または償却されたformula_7、色の変更には定数(実際には非常に速い)と小さい数になり、木の回転は3回以内(挿入は2回)となる。