# CS: heaps and binary trees

I have been given a practice exam from my professor (http://www.cs.pitt.edu/~aronis/cs0445/miscellaneous/cs445-spring-2007-test-3.pdf [Broken]) along with an answer sheet (http://www.cs.pitt.edu/~aronis/cs0445/miscellaneous/cs445-spring-2007-test-3-answers.txt [Broken]) 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!

Last edited by a moderator:

Related Engineering and Comp Sci Homework Help News on Phys.org
Filip Larsen
Gold Member
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.

deleting from a binary search tree:

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

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

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

Code:
   6
5     7
solution: this case is trivial, just delete it off

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

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

Code:
     5
8
6     8
now delete 8 from the subtree mainroot.right.right with one of the cases above

final:

Code:
     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)