Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: CS: heaps and binary trees

  1. Apr 27, 2010 #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: May 4, 2017
  2. jcsd
  3. Apr 28, 2010 #2

    Filip Larsen

    User Avatar
    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.
     
  4. Apr 28, 2010 #3
    deleting from a binary search tree:

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

    Code (Text):

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

    Code (Text):

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

    Code (Text):

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

    Code (Text):

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

    Code (Text):

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

    Code (Text):

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

    final:

    Code (Text):

         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)
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook