「データ構造」ナビゲーション2(12-1-1)AVLツリー、LL回転

今.探索1が終わり、探索2を学びましょう.
第一章

バランスのバイナリナビゲーションツリー:AVLツリーの理解

はい.

バイナリナビゲーションツリーの問題とAVLツリー

バイナリナビゲーションツリーのナビゲーション演算には、ログI.Nの時間的複雑さがあります.積が不均衡であるほど積が大きくなり,nに近い時間的複雑さを示した.

画像を見ると、ノードの数のように高さがアンバランスに見えます!
でも3万を貯めて順番に入れると

見えますか.
まず3万個貯めてもバランスが取れます.
このように,先に示したバイナリプローブツリーは,格納順序によってプローブ性能に大きな差がある.
これがバイナリ探索ツリーの欠点である.
これらの欠点を解決する木を「バランスのとれたバイナリツリー」と呼ぶことができる.
たぶん

AVLツリー

2-3ツリー

2-3-4ツリー

Red Blackツリー

Bツリー

そのうちの1つを選択して、私たちが前に作成したバイナリナビゲーションツリーを改善して、自動的にバランスを取ります!
そのため、AVLツリーを選択します.

自動平衡AVLツリーと平衡因子

AVLツリーは、Adelson-VelskiとLandisによって1960年代に設計され、それらの名前でAVLツリーと命名された.(1960年...年...呉振堂...)
AVLツリーは、ノードを追加したり、ノードを削除したりするときにツリーのバランス状態を把握し、自分で構造を変更してバランスをとるクールなツリーです.
等化の度合いを表すために「等化係数」を用いた.
バランス係数=左側のサブツリーの高さ-右側のサブツリーの高さ
はい.

各ノードの等化係数!
それを知った以上、バランスを直す(バランスツリー構造の再調整のため)タイミングを推測できます!
バランスファクタの節値が大きいほど、ツリーのバランスが悪くなります.
だから!バランスファクタの節値が2より大きい場合、バランスのために木を再調整する必要があります!

1つ目はバランスが必要な状態とL回転

木のバランスが崩れた状態は4種類あります.
だから.各状態間のバランス方法にも差がある.

最初の

これを見てどう表現しますか?
「ストレージ5のノードの左側にはストレージ3のサブノードが存在し、そのサブノードの左側にはストレージ1のサブノードが存在する」
実はこれはとても粗末な表現です!もう一度見ます.
以下の事実が見られる.
「コアは2つのサブノードが左につながっており、等化係数+2です.」
もし今一定の眼力があれば、LLを回すことが何を意味するか知っていますか!?
まだ知らないのなら、目が見えない!!
バラーは左左左に曲がる
つまり.
等化係数が+2の状態は「Left Left状態」であり、これを「LL状態」に縮小する.
また、このような不均衡を解消するために、「LL回転」と呼ばれる再バランスの方法が現れた.
そうだ!
左に2回曲がるという意味ではなく、LL状態でバランスをとるために必要な回転です!
意味は.
LL回転のコアは
等化係数が+2のノードを等化係数が+1のノードの右側サブノードとすることを目的とする.

これらの簡単な木の中には、ChangeRightSubTree(cNode,pNode)しかありません.やればいいのに.
一般化すると、上の一言だけでは足りません.

上図のT 1,2,3,4は高さが同じサブツリーだと仮定します!
では,5と3は記憶ノードの等化係数に影響を及ぼさない.
そのため、LL状態のままです.
T 1,2,3,4をNULLに変えると、前の画像のLL状態になります!
従って、上図はLL状態の一般化と見なすことができる.
現在一般化された状態で、LLを回転させるために考慮すべきことは!T3!
T 1,2,4は悩みもなく親ノードについて行くだけで大丈夫です.
T 3の親ノードがルートノードになります!
したがって、T 3は、その位置を他のノードに譲る必要がある.
上図はガチャガチャと別の5を譲る!
譲歩してT 3はどこに行けばいいですか?
さっそく!!!
5はストレージノードの左側のサブノードです!
今、この論理に従って回転する図を見せます.

だから
cNodeが指す右側のサブツリーをpNodeが指すノードの左側のサブツリーに移動するには、次の文を実行する必要があります.

ChangeLeftSubTree(pNode,GetRightSubTree(cNode));

だから!
LLを回転するには、
次の2つの文は順番に実行します.

ChangeLeftSubTree(pNode,GetRightSubTree(cNode));
ChangeRightSubTree(cNode,pNode);

次の文章では、4番目の状態の2番目の状態を見てみましょう.