时间戳

首页 > 解决方案 > 这个 add_node 函数会导致内存问题吗？

c++ - 这个 add_node 函数会导致内存问题吗？

问题描述

我编写了一个递归函数来在二叉搜索树中插入一个新节点。函数如下。

void add_node(node *it, int val)
{
    node * temp = new node;
    temp->data=val;
    temp->left=NULL;
    temp->right=NULL;
    if(root==NULL)
    {

        root=temp;
    }
    else if(it->data > val)
    {
        if(it->left==NULL)
        {

            it->left=temp;
            return;
        }
        else
            add_node(it->left, val);
    }

    else
    {
        if(it->right==NULL)
        {

            it->right=temp;
            return;
        }
        else
            add_node(it->right, val);
    }
}

该函数每次递归调用时都会创建一个临时节点。如果 BST 的高度很大，这会导致一些问题（与内存有关）吗？

标签： c++binary-search-tree

解决方案

该函数每次递归调用时都会创建一个临时节点。

该节点分配不是临时的；它彻底泄露了。唯一保留的是最后一个。事实上，任何需要多于一跳的遍历都会泄漏激活堆栈中任何先前递归调用中的节点分配。

有两件事可以解决这个问题。

  1. 在知道要挂起的位置之前不要分配节点。
  2. 相关，不要针对某些外部root. 使用指针引用作为输入参数类型允许您直接在树中引用实际指针（而不仅仅是它们持有的地址）。这包括root指针。

假设一个node看起来像这样的结构（带有删除复制 ctor 和分配的偏执狂）：

struct node
{
    node(int val)
        : value(val)
        , left(nullptr)
        , right(nullptr)
    {
        std::cout << "node::node(" << value << ")\n";
    }

    node(const node&) = delete;
    node& operator=(const node&) = delete;

    int value;
    node *left;
    node *right;
};

我们可以像这样制作一个简单的节点插入：

// note reference-to-pointer as first arg type
void add_node(node *& refp, int value) 
{
    if (refp == nullptr)
    {
        refp = new node(value);
    }
    else if (value < refp->value)
    {
        add_node(refp->left, value);
    }
    else
    {
        add_node(refp->right, value);
    }
}

而已。一旦我们最终知道事情的去向，就进行一次分配。某些外部指针没有特殊情况root，并且更容易阅读和理解。

完整示例

从上面添加node和add_node定义，一个中序打印遍历和一个free_tree清理内容，一个例子如下：

#include <iostream>
#include <random>

struct node
{
    node(int val)
        : value(val)
        , left(nullptr)
        , right(nullptr)
    {
        std::cout << "node::node(" << value << ")\n";
    }

    node(const node&) = delete;
    node& operator=(const node&) = delete;

    int value;
    node *left;
    node *right;
};

void add_node(node *& refp, int value)
{
    if (refp == nullptr)
    {
        refp = new node(value);
    }
    else if (value < refp->value)
    {
        add_node(refp->left, value);
    }
    else
    {
        add_node(refp->right, value);
    }
}

void inorder(const node* root)
{
    if (root)
    {
        inorder(root->left);
        std::cout << root->value << ' ';
        inorder(root->right);
    }
}

void free_tree(node *& root)
{
    if (root)
    {
        free_tree(root->left);
        free_tree(root->right);
        delete root;
        root = nullptr;
    }
}

int main()
{
    node *root = nullptr;

    std::mt19937 rng{ std::random_device{}() };
    std::uniform_int_distribution<> dist(1, 99);

    for (int i = 0; i < 20; ++i)
        add_node(root, dist(rng));

    inorder(root);
    std::cout.put('\n');

    free_tree(root);
}

输出（显然不同）

node::node(79)
node::node(28)
node::node(39)
node::node(82)
node::node(10)
node::node(11)
node::node(22)
node::node(4)
node::node(19)
node::node(85)
node::node(38)
node::node(66)
node::node(45)
node::node(15)
node::node(23)
node::node(73)
node::node(52)
node::node(45)
node::node(73)
node::node(84)
4 10 11 15 19 22 23 28 38 39 45 45 52 66 73 73 79 82 84 85

推荐阅读