平衡回転
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/03/19 04:33 UTC 版)
AA木は、赤黒木とは異なり、色ではなくレベルの概念を使って実装される。各ノードにはレベルが格納され、常に以下の条件が成り立つようになっている。 葉ノードのレベルは1である。 左の子ノードのレベルは親ノードのレベルより必ず１つ小さい。 右の子ノードのレベルは親ノードのレベルと等しいか１つ小さい。 右の孫ノードのレベルは祖父（祖母）ノードのレベルより必ず小さい。 レベルが1より大きいノードは、必ず2つの子ノードを持つ。 AA木では平衡を保つための操作は skew と split の2つだけである。skew は、挿入・削除によって水平左リンクが生じたときに（赤黒木で言えば、左の赤リンクに相当する）、右回転させる操作である。split は、挿入・削除によって水平右リンクが2つ生じたときに（赤黒木で言えば、赤ノードが2つ連続する状態に相当する）、条件付きで左回転させる操作である。水平リンクとは、子ノードが親ノードと同じレベルであることを意味する。 function skew is input: T, 再平衡化が必要なAA木を表すノード output: 平衡化されたAA木を表すノード if nil(T) then return Nil else if nil(left(T)) then return T else if level(left(T)) == level(T) then 水平左リンクのポインタを入れ替える。 L = left(T) left(T) := right(L) right(L) := T return L else return T end ifend function Skew: function split is input: T, 再平衡化が必要なAA木を表すノード output: 平衡化されたAA木を表すノード if nil(T) then return Nil else if nil(right(T)) or nil(right(right(T))) then return T else if level(T) == level(right(right(T))) then 水平右リンクが2つある場合。真ん中を持ち上げて、それを返す。 R = right(T) right(T) := left(R) left(R) := T level(R) := level(R) + 1 return R else return T end ifend function Split:
※この「平衡回転」の解説は、「AA木」の解説の一部です。
「平衡回転」を含む「AA木」の記事については、「AA木」の概要を参照ください。
- 平衡回転のページへのリンク
