|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 木 : [き] 【名詞】 1. tree 2. wood 3. timber ・ 回 : [かい] 【名詞】 1. counter for occurrences ・ 回転 : [かいてん] 1. (n,vs) rotation 2. revolution 3. turning
木の回転(きのかいてん、)は、2分探索木の操作の一種で、要素の順序を崩さずに構造を変更するものである。木の回転は木の中の1つのノードを上にし、別のノードを下にする。木の形状を変化させるのに使い、特に大きい部分木を持ち上げて小さい部分木を下げることで全体の木の高さを低くするのに使う。それによって各種操作の性能を向上させる。 なお、回転の方向によって「右回転」、「左回転」と言うが、どちらが右でどちらが左なのかは必ずしも決まっていない。図示したときにノードがずれる方向を回転の方向とする場合もあれば、どちら側の子ノードが根ノードになるかを回転の方向とする場合もある(前者の逆になる)。本項ではノードがずれる方向を回転の方向とする。 == 概要 == 上の図にある右回転 (Right Rotation) 操作は、根ノードが Q の木構造に対して行う。すると、木構造が時計回りの方向に回転することになる。対称的操作は左回転 (Left Rotation) であり、反時計回りに木構造を回転させる(上の図では根ノードが P の木構造に対して行う)。 先述したとおり2分探索木を対象としているので、ノードにある要素はアルファベット文字ではなく変数を表していると解釈されたい。 抄文引用元・出典: フリー百科事典『 ウィキペディア(Wikipedia)』 ■ウィキペディアで「木の回転」の詳細全文を読む スポンサード リンク
|