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の方法だと思います。これは正しいですか?