Trees/Removal - Revision history

Admin: /* Implementation: Prune Subtree */

2019-10-09T04:23:03Z

Implementation: Prune Subtree

← Older revision		Revision as of 04:23, 9 October 2019
Line 31:		Line 31:

	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 ~~adust~~ the size		* 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

Admin: /* Implementation: Prune Subtree */

2019-10-09T04:22:52Z

Implementation: Prune Subtree

← Older revision		Revision as of 04:22, 9 October 2019
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/branch/master/trees/oop-correct-tree/LinkedBinTree.java~~#L261~~		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:

Admin: /* Implementation: Prune Subtree */

2019-10-09T04:22:31Z

Implementation: Prune Subtree

← Older revision		Revision as of 04:22, 9 October 2019
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#L261		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#L261

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

	</pre>		</pre>


	==Flags==		==Flags==

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:59:03Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:59, 9 October 2019
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://charlesreid1.com~~:3000~~/cs/java/src/master/trees/LinkedBinTree.java#L261		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#L261

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

Admin: /* Flags */

2017-06-12T12:01:45Z

Flags

@@ Line 25: / Line 25: @@
 * 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.
 ==Flags==

Admin: Created page with "==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 * R..."

2017-06-12T11:56:15Z

Created page with "==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 * R..."

New page

==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.

==Flags==

{{TreesFlag}}
[[Category:Trees]]
[[Category:Binary Trees]]