# Difference between revisions of "Trees/Removal"

### From charlesreid1

m (Replacing charlesreid1.com:3000 with git.charlesreid1.com) |
|||

(2 intermediate revisions by the same user not shown) | |||

Line 28: | Line 28: | ||

==Implementation: Prune Subtree== | ==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/master/trees/LinkedBinTree.java | + | 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: | Here is the contents, which follow the steps given above: | ||

− | * Enumerate the subtree so we can | + | * Enumerate the subtree so we can adjust the size |

* Set the children of the target to null values | * Set the children of the target to null values | ||

* Remove links to the target from its parent | * Remove links to the target from its parent | ||

Line 69: | Line 69: | ||

</pre> | </pre> | ||

− | |||

==Flags== | ==Flags== |

## Latest revision as of 04:23, 9 October 2019

## Contents

## 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); } } }

## Flags

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |