0

私は学校でデータ構造について学び始めました。二分探索木を実装し、データ構造が占めるメモリを教えなければならない宿題があります。

BST を作成しましたが、すべてが期待どおりに機能していると思いますが、使用されるメモリを計算する方法がわかりません。

これは、データ構造用に作成したコードと挿入用のコードです。

class Node {

    int key, totalValue;
    public Node left;
    public Node right;

    public Node (int key, int totalValue) {
        this.key= key;
        this.totalValue = totalValue;
        this.left = null;
        this.right = null;
    }

    public int getkey() {
        return key;
    }

    public int getTotalValue() {
        return totalValue;
    }
}

class Tree {

    private Node root;

    public Tree() {
        this.root = null;
    }

    public Node getRoot() {
        return this.root;
    }

    public void setRoot(Node node) {
        this.root = node;
    }
}

そして、これは挿入するためのコードです:

private static void addNode(Node node, Node tempNode) {

    if (tempNode.getkey() < node.getkey()) {
        if (node.left == null) {
            node.left = tempNode;
        } else {
            addNode(node.left, tempNode);
        }
    } else if (tempNode.getkey() > node.getkey()){
        if (node.right == null) {
            node.right = tempNode;
        } else {
            addNode(node.right, tempNode);
        }
    }else{
        node.totalValue += tempNode.getTotalValue();
    }
}

ノードごとに 2 int に 8 バイトが必要であることはわかっていますが、各ポインターがどれだけ占有するかはわかりません。

2 番目の質問です。10000 個のキーから 25000 個のエントリを挿入するとします。新しいノードが「位置」を見つけるまで、各挿入は再帰的に使用されます。占有されているメモリを計算するにはどうすればよいですか?

4

2 に答える 2

1

再帰的な方法の背後にある基本的な概念は次のとおりです。

GetMemoryUsed(node)
{

    if(node is leaf)
        return (node.localMemory)

    return(GetMemoryUsed(node.left) + GetMemoryUsed(node.right) + node.localMemory);
}

はnode.localMemory、特定のノードが使用するメモリの量です (子ノードは数えません)。

于 2013-04-11T18:36:01.383 に答える
0

正確な数値を取得する限り、興味のあるツールがいくつかあります。

Java インストルメンテーション

JMap メモリ マップ

于 2013-04-11T18:37:12.933 に答える