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

  • Thread starter Thread starter n00neimp0rtnt
  • Start date Start date
  • Tags Tags
    Binary Cs Trees
Join the discussion
Ask a follow-up here, or get your own question answered by working scientists, mathematicians and engineers — people, not an autocomplete.
Real named experts · corrections over time · the nuance an AI answer skips
Sign up Log in
2 replies · 2K views
n00neimp0rtnt
Messages
15
Reaction score
0
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!
 
Last edited by a moderator:
Physics news on Phys.org
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)