In today’s lecture after the test, Joe went over the theory of removing nodes from a binary search tree. There are essentially 3 cases to consider.
The node is a leaf.
This case is the most straightforward. All you need to do is remove the parent’s connection to this node.
The node is an internal only child.
This case is only slightly less straightforward. The node’s parent must change its pointer to its grandchild.
The node is an internal child with a sibling.
This case can be a bit more complicated since it is not immediately clear what node should replace it. To produce minimal disruption to the tree, we should replace the deleted node with the largest value node in the left subtree (or smallest value node in the right subtree). This is an elegant solution for two reasons. 1. These nodes will never have two children so there will be no need to do a long recursive delete loop (if the largest value in the left tree had two children, then its right child would be larger than it. Proof by contradiction!). 2. This node, put in place of the deleted node will always be larger than its left child and smaller than its right child, so the BST property is maintained.
Is my tree lopsided?
The issue I am concerned with is the potential to make a tree uneven depending on the ordering of the insert and/or delete commands given to a Binary Search Tree. As efficient as the tree could be (O(log n)), a binary tree’s worst case scenario ends up just being a glorified linked list (O(n)). So a database maintenance sort of function could be useful for large BSTs. A function that one could run overnight on a large dynamic BST that strives to balance out the tree to make search/insert/delete functions applied to it operate as close to best case scenario time as possible. A function of this sort should be able to halt before completion and still have improved the tree, say in the case of a large database where there isn’t enough downtime to perform this operation fully, but better to optimize it somewhat than none at all. I managed to complete my code for the delete function shortly after class was over (180 lines though!), so I think I should try to implement a tree balancing function without searching the internet for the solution.
http://www.cs.haifa.ac.il/~shlomit/binaryTree16+8.jpg