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 个字节，但我不知道每个指针占用多少。

第二个问题。想象一下，我从 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 回答