1

AVLツリーを実装しようとしていますが、RRまたはRLローテーション（LLとLRで同じ）がいつ必要かを知るのに苦労しています。

それぞれの前提条件は何ですか、そしてそれらはどのように異なりますか。木の写真を（直感的に）見るとわかりますが、実際の状況はどうですか？

これは論理的な問題であり、コードは必要ありません。ありがとうございます。

私が知っているのは、木が重いままになっている、または右に重いままになっていることです。しかし、それをどのように判断しますか？

4

1 に答える 1

1

さまざまな解決策があるかもしれませんが、1つは次のとおりです。

項目を再帰的に追加する場合、各再帰呼び出しで、その呼び出しがノードを左または右のサブツリーに追加したかどうかを追跡する必要があります (たとえば、add 関数がそれを返すようにすることによって)。再帰呼び出しの後、高さ不変をチェックします。挿入後にそのノードで違反が見つかった場合は、不均衡へのパスがわかります。

いくつかの (不完全な) 疑似コード:

add(item, node):
  if item < node.value //should add to left subtree
    if node.left is empty
      //add item here
    else
      addedLeft := add(item, node.left)
      if node.left.height - node.right.height > 1
        if addedLeft
          //you know the path to the subtree causing the imbalance is LL, do a RR (single-right) rotation
        else
          //path is LR, do a LR (double-right) rotation
  ...

再帰呼び出しは、追加されたノードからボトムアップに展開されます。一般的な考え方は、不変条件に違反しているノード (存在する場合) をチェックすることです。そのノードが検出されたら、不均衡の原因となっているサブツリーへのパスを知る必要があります。どうにかしてその問題を解決しなければなりません。これが 1 つの解決策です。

于 2012-07-01T09:50:55.180 に答える