How Do You Add or Remove Elements from Heaps and Binary Trees?

[n00neimp0rtnt]

I have been given a practice exam from my professor (http://www.cs.pitt.edu/~aronis/cs0445/miscellaneous/cs445-spring-2007-test-3.pdf ) along with an answer sheet (http://www.cs.pitt.edu/~aronis/cs0445/miscellaneous/cs445-spring-2007-test-3-answers.txt ) and there are a good number of questions on heaps and binary trees. Unfortunately, he's a pretty bad professor and never exactly "showed us" how to add/remove to/from a heap or a binary tree. I'm looking for a good "visualization" of how to do this, and googling hasn't gotten me very far. If anyone has a web page or even notes from your own class on adding and removing from these data structures, it would be greatly appreciated.

Thanks!

 

[Filip Larsen]

In "Algorithms", Robert Sedgewick uses around 10 pages to describe and visualize the heap structure and operations. I would recommend that book (or one of his language specific editions) for any CS book shelf.

 

[wisvuze]

deleting from a binary search tree:

case 1: the node you want to delete ( the node with 7 ) has 1 child:

   6
5    7 
        8

solution: disconnect it from the tree by directly linking 7's only child to the node above

   6
5     8

case 2: the node you want to delete has no children (say, 7 again)

   6
5     7

solution: this case is trivial, just delete it off

   6
5

case 3: the node you want to delete has 2 children (7 again):

     5
        7 
     6     8

solution: Find its successor node (next node in a sorted order), copy it up to 7's position

     5
        8 
     6     8

now delete 8 from the subtree mainroot.right.right with one of the cases above

final:

     5
        8 
     6

notice how in the 2 children case (case 3), when deleting the successor node from the respective subtree, you will always end up doing case 1 or 2 again (the "easy" cases)