java - 递归调用占用内存

Question

我在学校开始学习数据结构，我有一个作业，我必须实现一个二叉搜索树并告诉数据结构占用的内存。

我已经创建了 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 个条目。每次插入都将递归使用，直到新节点找到它的“位置”。如何计算占用的内存？

Answer 1

递归方法背后的基本概念是

GetMemoryUsed(node)
{

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

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

其中node.localMemory只是特定节点使用的内存量(不计算子节点)