I'm trying to write a function to remove a node from a binary tree. I haven't coded the function yet, and I am trying to think about the different conditions I should consider for removing a node. I am guessing that the possible conditions are:
The node has no children
The node has one child
The node has 2 children
In each of these cases what would be the algorithm to perform a delete function?
This is something you would find in any standard textbook about algorithms, but let's suppose you are interested in the unbalanced case (balanced trees usually performs some rebalancing operations called "rotations" after a removal) and you use the "obvious" datastructure (a tree_node structure that holds the value and two pointers to other tree_node):
NULL;O(tree_height) = O(n), but it is not a problem (at least in theory) because this would be neverthless the complexity of finding a node.Does your tree have any additional properties? Is it an AVL?
If not, there are some pretty obvious and straightforward ways to do what you want (which will depend on your data representation, as Vitalij said).
And if it is an AVL for example, there ALSO are some well known method for doing that (wikipedia will tell you more on that topic)
First task is to find whether node exists which will be done during search and rest of your conditions are correct.
Leaf node: set the parent's child (right/left) to NULL.
Has one child: Just set the child of the node to be deleted to its parent's child.
Has two children: Basically have to re-order the whole subtree here by pruning the subtree to by finding new children for the node to be deleted.
Assuming you are dealing with general binary trees, do the following,
Node has no child- ie it is a leaf : Conveniently delete it..
Node has one child - Make the parent of the node to be deleted parent of its child , then delete the node. ie, if A->Parent = B; C->Parent = A; and A has to be deleted, then 1. Make C->Parent = B; 2. Delete A;
Tricky one.... Yes, replacing the node to be deleted by the left most child of the right subtree work, or by the rightmost tree of the left subtree, either will do... because it can be seen like this,
When a node is deleted, it has to be replaced by a node which satisfies some properties... Lets say if our binary tree represents sorted numbers (in increasing order) in inorder traversal, then the deleted node should be replaced by some node from either of its subtrees. That should be larger in value than the whole remaining left subtree, and smaller than the whole remaining right subtree (remaining means the subtree remaining after adjusting for the deleted node successfully). Only two such nodes exist, leftmost leaf of the right subtree, or the rightmost node of left one.
Hence, replacing the deleted node from either one suffices...!!
Delete the given keys one at a time from the binary search tree. Possible equal keys were inserted into the left branch of the existing node. Please note that the insertion strategy also affects how the deletion is performed
BinarySearchTree-Delete
Node Delete(Node root, Key k)
1 if (root == null) // failed search
2 return null;
3 if (k == root.key) // successful search
4 return DeleteThis(root);
5 if (k < root.key) // k in the left branch
6 root.left = Delete(root.left, k);
7 else // k > root.key, i.e., k in the right branch
8 root.right = Delete(root.right, k);
9 return root;
Node DeleteThis(Node root)
1 if root has two children
2 p = Largest(root.left); // replace root with its immediate predecessor p
3 root.key = p.key;
4 root.left = Delete(root.left, p)
5 return root;
6 if root has only left child
7 return root.left
8 if root has only right child
9 return root.right
10 else root has no children
11 return null
Node Largest(Node root)
1 if root has no right child
2 return root
3 return Largest(root.right)
