2

avl ツリーを拡張して、含まれるノードの数などの追加のプロパティを各ノードに追加したいと考えています (つまり、サブツリー内)。

この avl Java 実装コードから http://www.blackbam.at/blackbams-blog/2012/05/04/avl-tree-implementation-in-java/ 特定のコードを追加して、各ノードがsize 要素が含まれます。

AvlNode クラスでは、次のように変更しました。

/** Here is the AVL-Node class for Completenesse **/
public class AvlNode {
     public AvlNode left;
     public AvlNode right;
     public AvlNode parent;
     public int key;
     public int balance;
     public int size;

     public AvlNode(int k) {
          left = right = parent = null;
          balance = 0;
          key = k;
          size = 1;
     }
     public String toString() {
         return "" + key;
     }
}

しかし、AvlTree クラスについては、挿入操作と削除操作中にノードのサイズ値を更新するコードを実際にどこに追加すればよいでしょうか。私はそれがrotateleftとrotaterightの方法だと思います。これは正しいですか？

4

1 に答える 1

1

これは、オーグメンテーションで何をしようとしているかに完全に依存します。通常、バランスの取れた二分探索木を拡張する場合、ロジックに追加のコードを挿入して実行する必要があります。

  • 特定のサブツリーの数/内容を変更する挿入、
  • サブツリーから要素を削除する削除、および
  • 異なるサブツリー間でノードを移動するツリーの回転。

CLRS の「Introduction to Algorithms」教科書には、拡張二分探索木に関する章があります。赤/黒のツリーに焦点を当てていますが、同じ一般的なポリシーがローテーションベースのツリー バランシング スキームでも機能するはずです。

お役に立てれば！

于 2013-02-07T00:14:06.007 に答える