Binary Search Tree Part 5/5

Binary Search Tree Part 5: the remove key algorithm

Category:

People & Blogs

Tags:

• Binary
• Search
• Tree
• Part
• 5:
• the
• remove
• key
• algorithm

[rahulsaurav189]

I will modify it slightly as below:

else if (root.left==null && root.right==null) //considering it to be a leaf node remove the node itself;

else // considering it to be internal node

 find the max in left subtree,replace with node and remove max at leaf. or find the min in right subtree,replace with node and remove min at leaf .

[rahulsaurav189]

HAVE YOU TESTED IT?I DONT THINK IT WILL WORK,

logic is when root.left is null, remove entire root.right(root.right itself can be a subtree) and deleting all will not solve the purpose.

[DaveJLin]

@denebgarza

I should also add:

5. Or, if the present root passed the first two conditions and doesn't have a left or right child, then it is a leaf node, and by Agilowen's algorithm, a null pointer is returned, thus effectively deleting the present root.

[DaveJLin]

@denebgarza

The logic:

1. When present root matches key, it may be leaf or internal node.

2. If no left child, return right child as answer. This moves the appropriate pointer from previous root (parent of the present root which is under consideration) to right child of present root. Thus, present root is deleted.

3. Or, check if right child exists & apply same logic in point 2 above for left child.

4. Otherwise, it is an internal node and proceed to delete it accordingly.

[denebgarza]

how do you know it's necessarily a leaf once you pass the (key > root) and (key < root) conditions? Doesn't this simply mean you've found the node that matches the key? I don't understand how you can imply that it's a leaf node just because key == root.

[dired1]

Hey, thanks a lot, your videos are awesome.

Writing an exam tomorrow, very good repetition. Though I think i wouldn't understand if I never heard of this topic.