Destroying and Copying

Section 31.7 Destroying and Copying

Because our IntBST manages dynamic memory, it needs to implement a destructor, copy constructor, and assignment operator to ensure that memory is properly managed when a tree goes out of scope or is copied.

🔗

Subsection 31.7.1 Destructor

The binary search tree is responsible for the all of the memory used by its nodes. Therefore, when the tree is destroyed, it needs to free all of that memory. This is most easily accomplished with a recursive helper function that deletes all nodes in a subtree rooted at a given node. The destructor can then call this helper on the root of the tree.

🔗

We need to visit every node in the tree, which means one of our standard tree traversals will be required. As to which traversal to use, a post-order traversal is the most natural fit. When we reach a node, we will first delete its left and right subtrees so that we don’t lose track of them. Then, we can delete the current node itself.

🔗

First our recursive helper function:

🔗

Listing 31.7.1.

🔗

void clearRecursive(Node* node) {
    if (node == nullptr) {
        return;  // Base case: nothing to delete
    }
    // Recurse on left and right subtrees
    clearRecursive(node->left);
    clearRecursive(node->right);
    // Now delete this node
    delete node;
}

Then we need a member function that calls this helper. We will use it internally for things like the destructor, but it also is a reasonable operation to make available to consumers of the IntBST class. So we will make it a public member function.

🔗

When clear is used from the destructor, the entire tree is going away. So it would be OK to not bother resetting the root. However, when clear() is called in other situations, we may intend to continue using the BST. So clear should make sure the root is set to nullptr so we aren’t pointing at deleted memory.

🔗

Listing 31.7.2.

🔗

class IntBST {
private:
    Node* root = nullptr;
public:
    ~IntBST();      // Destructor
    void clear();   // Public clear function
};

void IntBST::clear() {
    clearRecursive(root);  // Call helper on root
    root = nullptr;        // Tree is now empty
}

// Destructor implementation
IntBST::~IntBST() {
    clear();  // Clear all nodes
}

🔗

Subsection 31.7.2 Copy Constructor and Assignment Operator

To implement a copy constructor and assignment operator for the binary search tree, we need a way to copy all of the nodes from one tree to another. We want to do a deep copy, meaning that we create an entirely new set of nodes with the same values and structure as the source tree.

🔗

Our parameter will be the node in the source tree that we want to copy. Our job will be to make a new node with the same value, recursively copy its left and right subtrees, and then return the address of the new node we created. This time, a pre-order traversal makes the most sense. We need to create the current node first, and then we can recursively create its children and attach them.

🔗

Listing 31.7.3.

🔗

Node* copyRecursive(Node* sourceNode) {
    if (sourceNode == nullptr) {
        return nullptr;  // Base case: nothing to copy
    }
    // Create new node with same value
    Node* newNode = new Node(sourceNode->data);
    // Recursively copy left and right subtrees
    newNode->left = copyRecursive(sourceNode->left);
    newNode->right = copyRecursive(sourceNode->right);
    return newNode;  // Return address of new node
}

Note how we make each recursive call, which will return a pointer, and then store that as the address of the new node’s appropriate child.

🔗

Activity 31.7.1. Binary Search Trees.

This animation is prepared to copy the tree on the left into a new tree on the right. Press the > button to step through the insertion process.

🔗

Instructions.

When the > button is highlighted, an animation is prepared to run. Use the Step button to step through the animation one step at a time.

🔗

When no animation is in progress, you can use the data controls to start a new animation.

🔗

You can click and drag on the animation area to pan around. Use the Ctrl + mouse wheel (or touchpad scroll gesture) while over the animation area to zoom in and out.

🔗

Core Controls.
- << : Skip to the beginning of the animation.
  
  🔗
- < : Step backwards one step in the animation.
  
  🔗
- > : Step forward one step in the animation.
  
  🔗
- >> : Skip to the end of the animation.
  
  🔗
- Auto Step Speed Set to anything other than off to automatically step through the animation at the selected speed.
  
  🔗
- Zoom Set the zoom level. You can also use Ctrl + Mouse Wheel to zoom in and out.
  
  🔗
🔗
🔗
Data Controls.
- Value Use this area to enter a value when inserting, finding, deleting, etc...
  
  🔗
🔗
🔗

🔗

Now we can implement the copy constructor and assignment operator using this helper function. The copy constructor will call the helper on the source tree’s root and set its own root to the result. The assignment operator will first clear its own tree to avoid memory leaks, then call the helper on the source tree’s root, and finally set its own root to the result. (It will also need to do the usual self-assignment check and return *this.)

🔗

Listing 31.7.4.

🔗

class IntBST {
private:
    Node* root = nullptr;
public:
    IntBST(const IntBST& other);            // Copy constructor
    IntBST& operator=(const IntBST& other); // Assignment operator
};

// Copy constructor implementation
IntBST::IntBST(const IntBST& other) {
    root = copyRecursive(other.root);  // Deep copy of other's tree's nodes
}

// Assignment operator implementation
IntBST& IntBST::operator=(const IntBST& other) {
    if (this != &other) {                  // Self-assignment check
        clear();                           // Clear current tree
        root = copyRecursive(other.root);  // Deep copy of other's tree's nodes
    }
    return *this;                          // Return this object
}

🔗

Checkpoint 31.7.1.

What is the Big O for clear() in our BST?

🔗

\(O(n)\)
\(O(log n)\)
\(O( \log n)\) is only when we walk one path from root to a leaf.
\(O(1)\)
That would only be true if we were just resetting the root and not actually deleting any nodes. However, that would cause a memory leak since the nodes would still be in memory but we would have no way to access them to delete them later.
\(O(n \log n)\)
No, try again.

🔗

Checkpoint 31.7.2.

In the copy constructor, what does root = copyRecursive(other.root); set root to?

🔗

The memory address of a new node that is a copy of the other tree’s root node.
The memory address of the other tree’s root node.
The other tree’s root node.
The new node that is a copy of the other tree’s root node.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next