algorithm - AVL ツリーのエクストラ ケース

Question

AVL ツリーには、Left-Left、Left-Right、Right-Left、Right-Right の 4 種類の変換があるようです。ただし、それ以外の状況も考えられるようです。私はこれをレフトバランスとして提出します:

左回転も右回転も、このツリーのバランスを取ることはできません。バランスをとるためにどのアルゴリズムを使用しますか?

Answer 1

ここでは LL と LR の両方を適用できます

        50
       /  \
     40    55
    /  \
  35    45
  / \   / \
34  36 44 46

最初の LR ターン後:

           50
          /  \
        45   55
       /  \
     40    46
    /  \
  35    44
  / \
34  36

2 番目の LR ターン後:

        45
       /  \
     40    50
    / \    / \
  35  44  46  55
 / \
34  36

これは有効な AVL ツリーです。ご了承ください

AVL ツリーでは、任意のノードの 2 つの子サブツリーの高さの差は最大で 1です。

LL ターンを行うこともできます。

     40
    /  \
  35    50
  / \   / \
34  36 45  55
       /\
     44  46

これも有効な AVL ツリーです。

Answer 2

I think you can't get the left-balance case. Because if you built the left-balance one, you may get the left-left or left-right first, then the tree would rotate and keep balance.