CS: heaps and binary trees

  • #1
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:

Answers and Replies

  • #2
Filip Larsen
Gold Member
1,263
191
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.
 
  • #3
371
1
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)
 

Related Threads on CS: heaps and binary trees

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
1
Views
830
  • Last Post
Replies
0
Views
971
Replies
6
Views
772
Replies
3
Views
4K
Replies
0
Views
8K
Replies
1
Views
715
Replies
1
Views
4K
Replies
0
Views
2K
Top