how to create a recursive destructor for this?
#CPP binary search trees.
static cave
hollow cedarBOT
hollow cedarBOT
pallid current
Well I guess you will have something like this ```cpp
#include <memory>
template<class T>
struct Node
{
T Data;
std::unique_ptr<Node> left = nullptr;
std::unique_ptr<Node> right = nullptr;
};
In which case there is no need to use any recursive destructors because unique_ptr will clean up everything automatically for youSo when a parent node goes out of scope it will clean up it's left and right nodes as well
atomic oar
test this with 100k tree nodes? You might see some problems 🙂
pallid current
What?
crude furnace
test this with 100k tree nodes? You might see some problems 🙂
std::unique_ptr has memory overhead only if you provide it with some non-trivial deleter. And has time overhead only during constructor (if it has to copy the provided deleter and/or null-initialize the pointer) and during destructor (to destroy the owned object).
conclusion: 100k nodes w/ smart pointers would be just as fine as 100k nodes with raw pointers, unless you continuously create and destroy std::unique_ptr.
atomic oar
I am not talking about run time cost. The run time cost is trivial. There is a much bigger problem with trees with large depths using this implementation
Letting the destructor of the std:;unique_ptr is perfectly logically fine but there is a hidden caveat
but let say supposedly was depth was large
then you will have a stack overflow. There is a reason why leetcode does not crete binary trees over 2k size with large depths
You can test this yourself. Create a binary tree that not balanced of at least of a depth of just 1k and then see it crash during the destruction. My guess is that if you create a tree of 100k in real production code, its not exactly really balanced or complete. It can easily have large depth.
pallid current
then you will have a stack overflow. There is a reason why leetcode does not cre...
but none of the nodes are allocated on the stack?
Bar maybe the root node
atomic oar
No the calls to the destructor is recursive by default. It generates a stack call. Yes of course freeing the memory is done on the heap but you still need to call the destructor which is a call on the stack. It generates a call that is done recursively.
Herp sutter talks about this at 18:19
pallid current
No the calls to the destructor is recursive by default. It generates a stack ca...
This would only really matter in non-trivial destructors tho
Since any trivial destructors would just be optimised away
atomic oar
yeah in production code, T can easily be non trivial type
wait no
it still a problem
if T is trivial type it still a problme
pallid current
if T is trivial type it still a problme
Yeah true sorry i wasn't thinking about the problem quite right i get what you mean
He just asked about recurssive so I gave recurrsive
atomic oar
@static cave yeah Recursive is not the way to go. Your best bet is delete the destructor, and instead have a manual deleter. Either let the memory automatically leak and restore it the OS(though there could be problems if you dont specify what it should be doing) or if you need clean up then use a iterative solution. Unless this is a homework assignment in which case do anything you want
desert sail
test this with 100k tree nodes? You might see some problems 🙂
test this with a tree 1m tree nodes? no problem. here's the thing, log(N) is small. your stack can handle 20 calls.
violet lintel
this assumes tree is balanced - not necessarily true for a BST
atomic oar
I already created a tree with 1 million nodes. And its pretty complete binary tree. The default maximum size is 1MB stack size. You still need to recurisvely visit every node thats how DFS works. So your space is still O(N)
in fact it stops at the 9960 stack element
desert sail
you need to visit every node either way. but since it's recursive, you will only have, at max, the longest path from root to leaf of stackframes at any point in time. assuming balance, that is log(N)
i've already done this in C with an AVL with recursive destruction with 1 << 20 nodes. there is no stack overflow.
atomic oar
No its O(n) because you are generating a stack call for each visit. It's a DFS traversal.
desert sail
and the stackframe gets popped when the destruction of the current node is complete. herb literally says it's log(N) if balanced and N in an unbalanced tree in the video you linked
DFS traversal means it will reach N nodes. so fucking what? hopefully you'll reach N nodes however you traverse, otherwise you have a leak. it doesn't take O(N) stack
atomic oar
No at 20:44 it says O(n)
desert sail
and prior to that he says log(N)
atomic oar
yeah if your tree was really balanced then its Log(n) but I dont have a blaanced tree