Trees/Removal

Removing single node from unsorted tree

Removal operation for trees:

• One way to call the remove() method is with no parameters
• This replaces a node with its child
• Raises an exception if a node has two (or more) children

Removing single node from sorted tree

But it also gets more complicated.

• In a sorted binary tree, need to rearrange the tree - traverse the tree to find the preceding node, and replace the node being removed with the preceding node.
• This requires traversing potentially the entire height of the tree, and so costs O(log N).

Removing subtree from unsorted tree

Removing a subtree:

• Removal of an entire subtree should be possible.
• Pass in a position in the tree, the method will remove the node at that position, as well as any child nodes.
• This is done by first setting the left and right children of the target position to null, then finding the parent of the target and setting its child equal to null.
• In a tree these are the only possible nodes that could point to this node.

Removing subtree from sorted tree

Removing a subtree from a sorted tree:

• When removing a subtree in a sorted tree, you're removing a set of contiguous values.
• No need to balance tree, because no possible child nodes needing reordering.

Implementation: Prune Subtree

An implementation of this in the concrete linked binary tree class Binary Trees/LinkedBinTree is in the git.charlesreid1.com Java repo: https://git.charlesreid1.com/cs/java/src/branch/master/trees/oop-correct-tree/LinkedBinTree.java

Here is the contents, which follow the steps given above:

• Enumerate the subtree so we can adjust the size
• Set the children of the target to null values
• Remove links to the target from its parent

	/** Prune the entire subtree rooted at position p. */
	public void pruneSubtree(Position<E> p) { 
		Node<E> node = validate(p);

		// Enumerate the subtree with a preorder iterator
		int count = 0;
		for(Position<E> pos : preorder(p)) {
			count++;
		}

		size -= count;

		node.setLeft(null);
		node.setRight(null);

		// How does an object commit suicide?
		// What if something obscure points at the data?
		// In a tree, we don't have to worry about that.
		if(!isRoot(p)) {
			// Target's children are Xed.
			// Now Target's parents need to be scrubbed of Target.
			Node<E> par = parent(p);
			if(par.getLeft()==p) { 
				par.setLeft(null);
			} else if(par.getRight()==p) { 
				par.setRight(null);
			}
		}

	}